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