ceph/src/boost/libs/move/test/bench_merge.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 <algorithm> //std::inplace_merge
  13 #include <cstdio>    //std::printf
  14 #include <iostream>  //std::cout
  15
  16 #include <boost/config.hpp>
  17
  18 #include <boost/move/unique_ptr.hpp>
  19 #include <boost/timer/timer.hpp>
  20
  21 #include "order_type.hpp"
  22 #include "random_shuffle.hpp"
  23
  24 using boost::timer::cpu_timer;
  25 using boost::timer::cpu_times;
  26 using boost::timer::nanosecond_type;
  27
  28 //#define BOOST_MOVE_ADAPTIVE_SORT_STATS
  29 void print_stats(const char *str, boost::ulong_long_type element_count)
  30 {
  31    std::printf("%sCmp:%8.04f Cpy:%9.04f\n", str, double(order_perf_type::num_compare)/element_count, double(order_perf_type::num_copy)/element_count );
  32 }
  33
  34 #include <boost/move/algo/adaptive_merge.hpp>
  35 #include <boost/move/algo/detail/merge.hpp>
  36 #include <boost/move/core.hpp>
  37
  38 template<class T, class Compare>
  39 std::size_t generate_elements(T elements[], std::size_t element_count, std::size_t key_reps[], std::size_t key_len, Compare comp)
  40 {
  41    std::srand(0);
  42    for(std::size_t i = 0; i < (key_len ? key_len : element_count); ++i){
  43       key_reps[i]=0;
  44    }
  45    for(std::size_t  i=0; i < element_count; ++i){
  46       std::size_t  key = key_len ? (i % key_len) : i;
  47       elements[i].key=key;
  48    }
  49    ::random_shuffle(elements, elements + element_count);
  50    ::random_shuffle(elements, elements + element_count);
  51    ::random_shuffle(elements, elements + element_count);
  52    for(std::size_t i = 0; i < element_count; ++i){
  53       elements[i].val = key_reps[elements[i].key]++;
  54    }
  55    std::size_t split_count = element_count/2;
  56    std::stable_sort(elements, elements+split_count, comp);
  57    std::stable_sort(elements+split_count, elements+element_count, comp);
  58    return split_count;
  59 }
  60
  61
  62
  63 template<class T, class Compare>
  64 void adaptive_merge_buffered(T *elements, T *mid, T *last, Compare comp, std::size_t BufLen)
  65 {
  66    boost::movelib::unique_ptr<char[]> mem(new char[sizeof(T)*BufLen]);
  67    boost::movelib::adaptive_merge(elements, mid, last, comp, reinterpret_cast<T*>(mem.get()), BufLen);
  68 }
  69
  70 enum AlgoType
  71 {
  72    StdMerge,
  73    AdaptiveMerge,
  74    SqrtHAdaptiveMerge,
  75    SqrtAdaptiveMerge,
  76    Sqrt2AdaptiveMerge,
  77    QuartAdaptiveMerge,
  78    StdInplaceMerge,
  79    MaxMerge
  80 };
  81
  82 const char *AlgoNames [] = { "StdMerge        "
  83                            , "AdaptMerge      "
  84                            , "SqrtHAdaptMerge "
  85                            , "SqrtAdaptMerge  "
  86                            , "Sqrt2AdaptMerge "
  87                            , "QHalfAdaptMerge "
  88                            , "StdInplaceMerge "
  89                            };
  90
  91 BOOST_STATIC_ASSERT((sizeof(AlgoNames)/sizeof(*AlgoNames)) == MaxMerge);
  92
  93 template<class T>
  94 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)
  95 {
  96    std::size_t const split_pos = generate_elements(elements, element_count, key_reps, key_len, order_type_less());
  97
  98    std::printf("%s ", AlgoNames[alg]);
  99    order_perf_type::num_compare=0;
 100    order_perf_type::num_copy=0;
 101    order_perf_type::num_elements = element_count;
 102    cpu_timer timer;
 103    timer.resume();
 104    switch(alg)
 105    {
 106       case StdMerge:
 107          std::inplace_merge(elements, elements+split_pos, elements+element_count, order_type_less());
 108       break;
 109       case AdaptiveMerge:
 110          boost::movelib::adaptive_merge(elements, elements+split_pos, elements+element_count, order_type_less());
 111       break;
 112       case SqrtHAdaptiveMerge:
 113          adaptive_merge_buffered( elements, elements+split_pos, elements+element_count, order_type_less()
 114                             , boost::movelib::detail_adaptive::ceil_sqrt_multiple(element_count)/2+1);
 115       break;
 116       case SqrtAdaptiveMerge:
 117          adaptive_merge_buffered( elements, elements+split_pos, elements+element_count, order_type_less()
 118                             , boost::movelib::detail_adaptive::ceil_sqrt_multiple(element_count));
 119       break;
 120       case Sqrt2AdaptiveMerge:
 121          adaptive_merge_buffered( elements, elements+split_pos, elements+element_count, order_type_less()
 122                             , 2*boost::movelib::detail_adaptive::ceil_sqrt_multiple(element_count));
 123       break;
 124       case QuartAdaptiveMerge:
 125          adaptive_merge_buffered( elements, elements+split_pos, elements+element_count, order_type_less()
 126                             , (element_count-1)/4+1);
 127       break;
 128       case StdInplaceMerge:
 129          boost::movelib::merge_bufferless_ONlogN(elements, elements+split_pos, elements+element_count, order_type_less());
 130       break;
 131    }
 132    timer.stop();
 133
 134    if(order_perf_type::num_elements == element_count){
 135       std::printf(" Tmp Ok ");
 136    } else{
 137       std::printf(" Tmp KO ");
 138    }
 139    nanosecond_type new_clock = timer.elapsed().wall;
 140
 141    //std::cout << "Cmp:" << order_perf_type::num_compare << " Cpy:" << order_perf_type::num_copy;   //for old compilers without ll size argument
 142    std::printf("Cmp:%8.04f Cpy:%9.04f", double(order_perf_type::num_compare)/element_count, double(order_perf_type::num_copy)/element_count );
 143
 144    double time = double(new_clock);
 145
 146    const char *units = "ns";
 147    if(time >= 1000000000.0){
 148       time /= 1000000000.0;
 149       units = " s";
 150    }
 151    else if(time >= 1000000.0){
 152       time /= 1000000.0;
 153       units = "ms";
 154    }
 155    else if(time >= 1000.0){
 156       time /= 1000.0;
 157       units = "us";
 158    }
 159
 160    std::printf(" %6.02f%s (%6.02f)\n"
 161               , time
 162               , units
 163               , prev_clock ? double(new_clock)/double(prev_clock): 1.0);
 164    prev_clock = new_clock;
 165    bool res = is_order_type_ordered(elements, element_count, true);
 166    return res;
 167 }
 168
 169 template<class T>
 170 bool measure_all(std::size_t L, std::size_t NK)
 171 {
 172    boost::movelib::unique_ptr<T[]> pdata(new T[L]);
 173    boost::movelib::unique_ptr<std::size_t[]> pkeys(new std::size_t[NK ? NK : L]);
 174    T *A              = pdata.get();
 175    std::size_t *Keys = pkeys.get();
 176    std::printf("\n - - N: %u, NK: %u - -\n", (unsigned)L, (unsigned)NK);
 177
 178    nanosecond_type prev_clock = 0;
 179    nanosecond_type back_clock;
 180    bool res = true;
 181    res = res && measure_algo(A,Keys,L,NK,StdMerge, prev_clock);
 182    back_clock = prev_clock;
 183    //
 184    prev_clock = back_clock;
 185    res = res && measure_algo(A,Keys,L,NK,QuartAdaptiveMerge, prev_clock);
 186    //
 187    prev_clock = back_clock;
 188    res = res && measure_algo(A,Keys,L,NK,Sqrt2AdaptiveMerge, prev_clock);
 189    //
 190    prev_clock = back_clock;
 191    res = res && measure_algo(A,Keys,L,NK,SqrtAdaptiveMerge, prev_clock);
 192    //
 193    prev_clock = back_clock;
 194    res = res && measure_algo(A,Keys,L,NK,SqrtHAdaptiveMerge, prev_clock);
 195    //
 196    prev_clock = back_clock;
 197    res = res && measure_algo(A,Keys,L,NK,AdaptiveMerge, prev_clock);
 198    //
 199    prev_clock = back_clock;
 200    res = res && measure_algo(A,Keys,L,NK,StdInplaceMerge, prev_clock);
 201    //
 202    if(!res)
 203       throw int(0);
 204    return res;
 205 }
 206
 207 //Undef it to run the long test
 208 #define BENCH_MERGE_SHORT
 209 #define BENCH_SORT_UNIQUE_VALUES
 210
 211 int main()
 212 {
 213    try{
 214    #ifndef BENCH_SORT_UNIQUE_VALUES
 215    measure_all<order_perf_type>(101,1);
 216    measure_all<order_perf_type>(101,7);
 217    measure_all<order_perf_type>(101,31);
 218    #endif
 219    measure_all<order_perf_type>(101,0);
 220
 221    //
 222    #ifndef BENCH_SORT_UNIQUE_VALUES
 223    measure_all<order_perf_type>(1101,1);
 224    measure_all<order_perf_type>(1001,7);
 225    measure_all<order_perf_type>(1001,31);
 226    measure_all<order_perf_type>(1001,127);
 227    measure_all<order_perf_type>(1001,511);
 228    #endif
 229    measure_all<order_perf_type>(1001,0);
 230    //
 231    #ifndef BENCH_MERGE_SHORT
 232    #ifndef BENCH_SORT_UNIQUE_VALUES
 233    measure_all<order_perf_type>(10001,65);
 234    measure_all<order_perf_type>(10001,255);
 235    measure_all<order_perf_type>(10001,1023);
 236    measure_all<order_perf_type>(10001,4095);
 237    #endif
 238    measure_all<order_perf_type>(10001,0);
 239
 240    //
 241    #ifndef BENCH_SORT_UNIQUE_VALUES
 242    measure_all<order_perf_type>(100001,511);
 243    measure_all<order_perf_type>(100001,2047);
 244    measure_all<order_perf_type>(100001,8191);
 245    measure_all<order_perf_type>(100001,32767);
 246    #endif
 247    measure_all<order_perf_type>(100001,0);
 248
 249    //
 250    #ifdef NDEBUG
 251    #ifndef BENCH_SORT_UNIQUE_VALUES
 252    measure_all<order_perf_type>(1000001,1);
 253    measure_all<order_perf_type>(1000001,1024);
 254    measure_all<order_perf_type>(1000001,32768);
 255    measure_all<order_perf_type>(1000001,524287);
 256    #endif
 257    measure_all<order_perf_type>(1000001,0);
 258    measure_all<order_perf_type>(3000001,0);
 259    #endif   //NDEBUG
 260
 261    #endif   //#ifndef BENCH_MERGE_SHORT
 262
 263    //measure_all<order_perf_type>(100000001,0);
 264    }
 265    catch(...)
 266    {
 267       return 1;
 268    }
 269
 270    return 0;
 271 }
 272