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