ceph/src/boost/libs/move/test/bench_sort.cpp

   1 //////////////////////////////////////////////////////////////////////////////
   2 //
   3 // (C) Copyright Ion Gaztanaga 2015-2016.
   4 // Distributed under the Boost Software License, Version 1.0.
   5 // (See accompanying file LICENSE_1_0.txt or copy at
   6 // http://www.boost.org/LICENSE_1_0.txt)
   7 //
   8 // See http://www.boost.org/libs/move for documentation.
   9 //
  10 //////////////////////////////////////////////////////////////////////////////
  11
  12 #include <cstdlib>   //std::srand
  13 #include <algorithm> //std::stable_sort, std::make|sort_heap, std::random_shuffle
  14 #include <cstdio>    //std::printf
  15 #include <iostream>  //std::cout
  16
  17 #include <boost/config.hpp>
  18
  19 #include <boost/move/unique_ptr.hpp>
  20 #include <boost/timer/timer.hpp>
  21
  22 using boost::timer::cpu_timer;
  23 using boost::timer::cpu_times;
  24 using boost::timer::nanosecond_type;
  25
  26 #include "order_type.hpp"
  27 #include "random_shuffle.hpp"
  28
  29 //#define BOOST_MOVE_ADAPTIVE_SORT_STATS
  30 //#define BOOST_MOVE_ADAPTIVE_SORT_INVARIANTS
  31 void print_stats(const char *str, boost::ulong_long_type element_count)
  32 {
  33    std::printf("%sCmp:%7.03f Cpy:%8.03f\n", str, double(order_perf_type::num_compare)/element_count, double(order_perf_type::num_copy)/element_count );
  34 }
  35
  36
  37 #include <boost/move/algo/adaptive_sort.hpp>
  38 #include <boost/move/algo/detail/merge_sort.hpp>
  39 #include <boost/move/core.hpp>
  40
  41 template<class T>
  42 void generate_elements(T elements[], std::size_t element_count, std::size_t key_reps[], std::size_t key_len)
  43 {
  44    std::srand(0);
  45    for(std::size_t i = 0; i < (key_len ? key_len : element_count); ++i){
  46       key_reps[i]=0;
  47    }
  48    for(std::size_t  i=0; i < element_count; ++i){
  49       std::size_t  key = key_len ? (i % key_len) : i;
  50       elements[i].key=key;
  51    }
  52    ::random_shuffle(elements, elements + element_count);
  53    ::random_shuffle(elements, elements + element_count);
  54    ::random_shuffle(elements, elements + element_count);
  55    for(std::size_t i = 0; i < element_count; ++i){
  56       elements[i].val = key_reps[elements[i].key]++;
  57    }
  58 }
  59
  60 template<class T, class Compare>
  61 void adaptive_sort_buffered(T *elements, std::size_t element_count, Compare comp, std::size_t BufLen)
  62 {
  63    boost::movelib::unique_ptr<char[]> mem(new char[sizeof(T)*BufLen]);
  64    boost::movelib::adaptive_sort(elements, elements + element_count, comp, reinterpret_cast<T*>(mem.get()), BufLen);
  65 }
  66
  67 template<class T, class Compare>
  68 void merge_sort_buffered(T *elements, std::size_t element_count, Compare comp)
  69 {
  70    boost::movelib::unique_ptr<char[]> mem(new char[sizeof(T)*((element_count+1)/2)]);
  71    boost::movelib::merge_sort(elements, elements + element_count, comp, reinterpret_cast<T*>(mem.get()));
  72 }
  73
  74 enum AlgoType
  75 {
  76    MergeSort,
  77    StableSort,
  78    AdaptiveSort,
  79    SqrtHAdaptiveSort,
  80    SqrtAdaptiveSort,
  81    Sqrt2AdaptiveSort,
  82    QuartAdaptiveSort,
  83    InplaceStableSort,
  84    SlowStableSort,
  85    HeapSort,
  86    MaxSort
  87 };
  88
  89 const char *AlgoNames [] = { "MergeSort      "
  90                            , "StableSort     "
  91                            , "AdaptSort      "
  92                            , "SqrtHAdaptSort "
  93                            , "SqrtAdaptSort  "
  94                            , "Sqrt2AdaptSort "
  95                            , "QuartAdaptSort "
  96                            , "InplStableSort "
  97                            , "SlowSort       "
  98                            , "HeapSort       "
  99                            };
 100
 101 BOOST_STATIC_ASSERT((sizeof(AlgoNames)/sizeof(*AlgoNames)) == MaxSort);
 102
 103 template<class T>
 104 bool measure_algo(T *elements, std::size_t key_reps[], std::size_t element_count, std::size_t key_len, unsigned alg, nanosecond_type &prev_clock)
 105 {
 106    generate_elements(elements, element_count, key_reps, key_len);
 107
 108    std::printf("%s ", AlgoNames[alg]);
 109    order_perf_type::num_compare=0;
 110    order_perf_type::num_copy=0;
 111    order_perf_type::num_elements = element_count;
 112    cpu_timer timer;
 113    timer.resume();
 114    switch(alg)
 115    {
 116       case MergeSort:
 117          merge_sort_buffered(elements, element_count, order_type_less());
 118       break;
 119       case StableSort:
 120          std::stable_sort(elements,elements+element_count,order_type_less());
 121       break;
 122       case AdaptiveSort:
 123          boost::movelib::adaptive_sort(elements, elements+element_count, order_type_less());
 124       break;
 125       case SqrtHAdaptiveSort:
 126          adaptive_sort_buffered( elements, element_count, order_type_less()
 127                             , boost::movelib::detail_adaptive::ceil_sqrt_multiple(element_count)/2+1);
 128       break;
 129       case SqrtAdaptiveSort:
 130          adaptive_sort_buffered( elements, element_count, order_type_less()
 131                             , boost::movelib::detail_adaptive::ceil_sqrt_multiple(element_count));
 132       break;
 133       case Sqrt2AdaptiveSort:
 134          adaptive_sort_buffered( elements, element_count, order_type_less()
 135                             , 2*boost::movelib::detail_adaptive::ceil_sqrt_multiple(element_count));
 136       break;
 137       case QuartAdaptiveSort:
 138          adaptive_sort_buffered( elements, element_count, order_type_less()
 139                             , (element_count-1)/4+1);
 140       break;
 141       case InplaceStableSort:
 142          boost::movelib::inplace_stable_sort(elements, elements+element_count, order_type_less());
 143       break;
 144       case SlowStableSort:
 145          boost::movelib::detail_adaptive::slow_stable_sort(elements, elements+element_count, order_type_less());
 146       break;
 147       case HeapSort:
 148          std::make_heap(elements, elements+element_count, order_type_less());
 149          std::sort_heap(elements, elements+element_count, order_type_less());
 150       break;
 151    }
 152    timer.stop();
 153
 154    if(order_perf_type::num_elements == element_count){
 155       std::printf(" Tmp Ok ");
 156    } else{
 157       std::printf(" Tmp KO ");
 158    }
 159    nanosecond_type new_clock = timer.elapsed().wall;
 160
 161    //std::cout << "Cmp:" << order_perf_type::num_compare << " Cpy:" << order_perf_type::num_copy;   //for old compilers without ll size argument
 162    std::printf("Cmp:%7.03f Cpy:%8.03f", double(order_perf_type::num_compare)/element_count, double(order_perf_type::num_copy)/element_count );
 163
 164    double time = double(new_clock);
 165
 166    const char *units = "ns";
 167    if(time >= 1000000000.0){
 168       time /= 1000000000.0;
 169       units = " s";
 170    }
 171    else if(time >= 1000000.0){
 172       time /= 1000000.0;
 173       units = "ms";
 174    }
 175    else if(time >= 1000.0){
 176       time /= 1000.0;
 177       units = "us";
 178    }
 179
 180    std::printf(" %6.02f%s (%6.02f)\n"
 181               , time
 182               , units
 183               , prev_clock ? double(new_clock)/double(prev_clock): 1.0);
 184    prev_clock = new_clock;
 185    bool res = is_order_type_ordered(elements, element_count, alg != HeapSort);
 186    return res;
 187 }
 188
 189 template<class T>
 190 bool measure_all(std::size_t L, std::size_t NK)
 191 {
 192    boost::movelib::unique_ptr<T[]> pdata(new T[L]);
 193    boost::movelib::unique_ptr<std::size_t[]> pkeys(new std::size_t[NK ? NK : L]);
 194    T *A              = pdata.get();
 195    std::size_t *Keys = pkeys.get();
 196    std::printf("\n - - N: %u, NK: %u - -\n", (unsigned)L, (unsigned)NK);
 197
 198    nanosecond_type prev_clock = 0;
 199    nanosecond_type back_clock;
 200    bool res = true;
 201    res = res && measure_algo(A,Keys,L,NK,MergeSort, prev_clock);
 202    back_clock = prev_clock;
 203    //
 204    prev_clock = back_clock;
 205    res = res && measure_algo(A,Keys,L,NK,StableSort, prev_clock);
 206    //
 207    prev_clock = back_clock;
 208    res = res && measure_algo(A,Keys,L,NK,HeapSort, prev_clock);
 209    //
 210    prev_clock = back_clock;
 211    res = res && measure_algo(A,Keys,L,NK,QuartAdaptiveSort, prev_clock);
 212    //
 213    prev_clock = back_clock;
 214    res = res && measure_algo(A,Keys,L,NK,Sqrt2AdaptiveSort, prev_clock);
 215    //
 216    prev_clock = back_clock;
 217    res = res && measure_algo(A,Keys,L,NK,SqrtAdaptiveSort, prev_clock);
 218    //
 219    prev_clock = back_clock;
 220    res = res && measure_algo(A,Keys,L,NK,SqrtHAdaptiveSort, prev_clock);
 221    //
 222    prev_clock = back_clock;
 223    res = res && measure_algo(A,Keys,L,NK,AdaptiveSort, prev_clock);
 224    //
 225    prev_clock = back_clock;
 226    res = res && measure_algo(A,Keys,L,NK,InplaceStableSort, prev_clock);
 227    //
 228    //prev_clock = back_clock;
 229    //res = res && measure_algo(A,Keys,L,NK,SlowStableSort, prev_clock);
 230    //
 231    if(!res)
 232       throw int(0);
 233    return res;
 234 }
 235
 236 //Undef it to run the long test
 237 #define BENCH_SORT_SHORT
 238 #define BENCH_SORT_UNIQUE_VALUES
 239
 240 int main()
 241 {
 242    #ifndef BENCH_SORT_UNIQUE_VALUES
 243    measure_all<order_perf_type>(101,1);
 244    measure_all<order_perf_type>(101,7);
 245    measure_all<order_perf_type>(101,31);
 246    #endif
 247    measure_all<order_perf_type>(101,0);
 248
 249    //
 250    #ifndef BENCH_SORT_UNIQUE_VALUES
 251    measure_all<order_perf_type>(1101,1);
 252    measure_all<order_perf_type>(1001,7);
 253    measure_all<order_perf_type>(1001,31);
 254    measure_all<order_perf_type>(1001,127);
 255    measure_all<order_perf_type>(1001,511);
 256    #endif
 257    measure_all<order_perf_type>(1001,0);
 258    //
 259    #ifndef BENCH_SORT_SHORT
 260    #ifndef BENCH_SORT_UNIQUE_VALUES
 261    measure_all<order_perf_type>(10001,65);
 262    measure_all<order_perf_type>(10001,255);
 263    measure_all<order_perf_type>(10001,1023);
 264    measure_all<order_perf_type>(10001,4095);
 265    #endif
 266    measure_all<order_perf_type>(10001,0);
 267
 268    //
 269    #ifndef BENCH_SORT_UNIQUE_VALUES
 270    measure_all<order_perf_type>(100001,511);
 271    measure_all<order_perf_type>(100001,2047);
 272    measure_all<order_perf_type>(100001,8191);
 273    measure_all<order_perf_type>(100001,32767);
 274    #endif
 275    measure_all<order_perf_type>(100001,0);
 276
 277    //
 278    #ifdef NDEBUG
 279    #ifndef BENCH_SORT_UNIQUE_VALUES
 280    measure_all<order_perf_type>(1000001,1);
 281    measure_all<order_perf_type>(1000001,1024);
 282    measure_all<order_perf_type>(1000001,32768);
 283    measure_all<order_perf_type>(1000001,524287);
 284    #endif
 285    measure_all<order_perf_type>(1000001,0);
 286    measure_all<order_perf_type>(1500001,0);
 287    #endif   //NDEBUG
 288
 289    #endif   //#ifndef BENCH_SORT_SHORT
 290
 291    //measure_all<order_perf_type>(100000001,0);
 292
 293    return 0;
 294 }