ceph/src/boost/libs/container/bench/bench_set.hpp

   1 //////////////////////////////////////////////////////////////////////////////
   2 //
   3 // (C) Copyright Ion Gaztanaga 2013-2014. Distributed under the Boost
   4 // Software License, Version 1.0. (See accompanying file
   5 // LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
   6 //
   7 // See http://www.boost.org/libs/container for documentation.
   8 //
   9 //////////////////////////////////////////////////////////////////////////////
  10
  11 #ifndef BOOST_CONTAINER_BENCH_BENCH_SET_HPP
  12 #define BOOST_CONTAINER_BENCH_BENCH_SET_HPP
  13
  14 #include <iostream>
  15 #include <boost/move/detail/nsec_clock.hpp>
  16 #include <algorithm> //sort
  17 #include <exception>
  18 #include <sstream>
  19 #include <iomanip>
  20 #include <boost/container/vector.hpp>
  21 #include <boost/container/string.hpp>
  22 #include <boost/core/no_exceptions_support.hpp>
  23
  24 using boost::move_detail::cpu_timer;
  25 using boost::move_detail::cpu_times;
  26 using boost::move_detail::nanosecond_type;
  27
  28 #define SIMPLE_IT
  29 #ifdef SIMPLE_IT
  30 static const std::size_t NIter = 3;
  31 #else
  32    #ifdef NDEBUG
  33    static const std::size_t NIter = 250;
  34    #else
  35    static const std::size_t NIter = 25;
  36    #endif
  37 #endif
  38
  39 static const std::size_t NElements = 1000;
  40
  41
  42 void compare_times(cpu_times time_numerator, cpu_times time_denominator)
  43 {
  44    std::cout << ((double)time_numerator.wall/(double)time_denominator.wall) << '\n' << std::endl;
  45 }
  46
  47 template< class RandomIt >
  48 void random_shuffle( RandomIt first, RandomIt last )
  49 {
  50    typedef typename boost::container::iterator_traits<RandomIt>::difference_type difference_type;
  51    difference_type n = last - first;
  52    for (difference_type i = n-1; i > 0; --i) {
  53       difference_type j = std::rand() % (i+1);
  54       if(j != i) {
  55          boost::adl_move_swap(first[i], first[j]);
  56       }
  57    }
  58 }
  59
  60 boost::container::vector<int> sorted_unique_range_int;
  61 boost::container::vector<int> sorted_range_int;
  62 boost::container::vector<int> random_unique_range_int;
  63 boost::container::vector<int> random_range_int;
  64
  65 void fill_range_ints()
  66 {
  67    //sorted_unique_range_int
  68    sorted_unique_range_int.resize(NElements);
  69    for(std::size_t i = 0, max = sorted_unique_range_int.size(); i != max; ++i){
  70       sorted_unique_range_int[i] = static_cast<int>(i);
  71    }
  72    //sorted_range_int
  73    sorted_range_int = sorted_unique_range_int;
  74    sorted_range_int.insert(sorted_range_int.end(), sorted_unique_range_int.begin(), sorted_unique_range_int.end());
  75    std::sort(sorted_range_int.begin(), sorted_range_int.end());
  76
  77    //random_range_int
  78    std::srand(0);
  79    random_range_int.assign(sorted_range_int.begin(), sorted_range_int.end());
  80    ::random_shuffle(random_range_int.begin(), random_range_int.end());
  81    //random_unique_range_int
  82    std::srand(0);
  83    random_unique_range_int.assign(sorted_unique_range_int.begin(), sorted_unique_range_int.end());
  84    ::random_shuffle(random_unique_range_int.begin(), random_unique_range_int.end());
  85 }
  86
  87 boost::container::vector<boost::container::string> sorted_unique_range_string;
  88 boost::container::vector<boost::container::string> sorted_range_string;
  89 boost::container::vector<boost::container::string> random_unique_range_string;
  90 boost::container::vector<boost::container::string> random_range_string;
  91
  92 void fill_range_strings()
  93 {
  94    boost::container::string model_s;
  95    model_s.append(sizeof(boost::container::string), '*');
  96
  97    //sorted_unique_range_int
  98    sorted_unique_range_string.resize(NElements);
  99    std::stringstream sstr;
 100
 101    for(std::size_t i = 0, max = sorted_unique_range_string.size(); i != max; ++i){
 102       sstr.str(std::string());
 103       sstr << std::setfill('0') << std::setw(10) << i;
 104       sorted_unique_range_string[i] = model_s;
 105       const std::string &s = sstr.str();
 106       sorted_unique_range_string[i].append(s.begin(), s.end());
 107    }
 108    //sorted_range_string
 109    sorted_range_string = sorted_unique_range_string;
 110    sorted_range_string.insert(sorted_range_string.end(), sorted_unique_range_string.begin(), sorted_unique_range_string.end());
 111    std::sort(sorted_range_string.begin(), sorted_range_string.end());
 112
 113    //random_range_string
 114    std::srand(0);
 115    random_range_string.assign(sorted_range_string.begin(), sorted_range_string.end());
 116    ::random_shuffle(random_range_string.begin(), random_range_string.end());
 117    //random_unique_range_string
 118    std::srand(0);
 119    random_unique_range_string.assign(sorted_unique_range_string.begin(), sorted_unique_range_string.end());
 120    ::random_shuffle(random_unique_range_string.begin(), random_unique_range_string.end());
 121 }
 122
 123 template<class T>
 124 struct range_provider;
 125
 126 template<>
 127 struct range_provider<int>
 128 {
 129    typedef boost::container::vector<int> type;
 130
 131    static type &sorted_unique()
 132    {  return sorted_unique_range_int;  }
 133
 134    static type &sorted()
 135    {  return sorted_range_int;  }
 136
 137    static type &random_unique()
 138    {  return random_unique_range_int;  }
 139
 140    static type &random()
 141    {  return random_range_int;  }
 142 };
 143
 144 template<>
 145 struct range_provider<boost::container::string>
 146 {
 147    typedef boost::container::vector<boost::container::string> type;
 148
 149    static type &sorted_unique()
 150    {  return sorted_unique_range_string;  }
 151
 152    static type &sorted()
 153    {  return sorted_range_string;  }
 154
 155    static type &random_unique()
 156    {  return random_unique_range_string;  }
 157
 158    static type &random()
 159    {  return random_range_string;  }
 160 };
 161
 162 template<typename C>
 163 cpu_times copy_destroy_time(boost::container::vector<typename C::value_type> &unique_range)
 164 {
 165    cpu_timer copy_timer, assign_timer, destroy_timer;
 166
 167    cpu_timer total_time;
 168
 169    for(std::size_t i = 0; i != NIter; ++i){
 170       {
 171          C c(unique_range.begin(), unique_range.end());
 172          total_time.resume();
 173          copy_timer.resume();
 174          C caux(c);
 175          copy_timer.stop();
 176          assign_timer.resume();
 177          c = caux;
 178          assign_timer.stop();
 179          destroy_timer.resume();
 180       }
 181       destroy_timer.stop();
 182       total_time.stop();
 183    }
 184    total_time.stop();
 185
 186    std::cout << " Copy sorted range             " << double(copy_timer.elapsed().wall)/double(1000000000) << "s\n";
 187    std::cout << " Assign sorted range           " << double(assign_timer.elapsed().wall)/double(1000000000) << "s\n";
 188    std::cout << " Destroy                       " << double(destroy_timer.elapsed().wall)/double(1000000000) << "s\n";
 189    std::cout << " Total time =                  " << double(total_time.elapsed().wall)/double(1000000000) << "s\n";
 190    return total_time.elapsed();
 191 }
 192
 193 template<typename C>
 194 cpu_times construct_time( boost::container::vector<typename C::value_type> &unique_range
 195                         , boost::container::vector<typename C::value_type> &range
 196                         , const char *RangeType)
 197 {
 198    cpu_timer sur_timer, sr_timer;
 199
 200    cpu_timer total_time;
 201
 202    for(std::size_t i = 0; i != NIter; ++i){
 203       {
 204          sur_timer.resume();
 205          total_time.resume();
 206          C c(unique_range.begin(), unique_range.end());
 207          sur_timer.stop();
 208          total_time.stop();
 209       }
 210       {
 211          total_time.resume();
 212          sr_timer.resume();
 213          C c(range.begin(), range.end());
 214          sr_timer.stop();
 215          total_time.stop();
 216       }
 217    }
 218
 219    std::cout << " Construct " << RangeType << " unique_range " << double(sur_timer.elapsed().wall)/double(1000000000) << "s\n";
 220    std::cout << " Construct " << RangeType << " range        " << double(sr_timer.elapsed().wall)/double(1000000000) << "s\n";
 221    std::cout << " Total time =                 " << double(total_time.elapsed().wall)/double(1000000000) << "s\n";
 222    return total_time.elapsed();
 223 }
 224
 225 template<typename C>
 226 cpu_times insert_time( boost::container::vector<typename C::value_type> &unique_range
 227                      , boost::container::vector<typename C::value_type> &range
 228                      , const char *RangeType)
 229 {
 230    cpu_timer ur_timer,r_timer;
 231    ur_timer.stop();r_timer.stop();
 232
 233    cpu_timer total_time;
 234    total_time.resume();
 235
 236    for(std::size_t i = 0; i != NIter; ++i){
 237       {
 238          total_time.resume();
 239          ur_timer.resume();
 240          C c;
 241          c.insert(unique_range.begin(), unique_range.end());
 242          ur_timer.stop();
 243          total_time.stop();
 244       }
 245       {
 246          total_time.resume();
 247          r_timer.resume();
 248          C c;
 249          c.insert(range.begin(), range.end());
 250          r_timer.stop();
 251          total_time.stop();
 252       }
 253    }
 254
 255    std::cout << " Insert " << RangeType << " unique_range " << double(ur_timer.elapsed().wall)/double(1000000000) << "s\n";
 256    std::cout << " Insert " << RangeType << " range        " << double(r_timer.elapsed().wall)/double(1000000000) << "s\n";
 257    std::cout << " Total time =              " << double(total_time.elapsed().wall)/double(1000000000) << "s\n";
 258    return total_time.elapsed();
 259 }
 260
 261 template<typename Iterator>
 262 bool check_not_end(boost::container::vector<Iterator> &iterators, Iterator itend, std::size_t number_of_ends = 0)
 263 {
 264    std::size_t end_count = 0;
 265    for(std::size_t i = 0, max = iterators.size(); i != max; ++i){
 266       if(iterators[i] == itend && (++end_count > number_of_ends) )
 267          return false;
 268    }
 269    return true;
 270 }
 271
 272 template<typename Iterator>
 273 bool check_all_not_empty(boost::container::vector< std::pair<Iterator, Iterator > > &iterator_pairs)
 274 {
 275    for(std::size_t i = 0, max = iterator_pairs.size(); i != max; ++i){
 276       if(iterator_pairs[i].first == iterator_pairs[i].second)
 277          return false;
 278    }
 279    return true;
 280 }
 281
 282 template<typename C>
 283 cpu_times search_time(boost::container::vector<typename C::value_type> &unique_range, const char *RangeType)
 284 {
 285    cpu_timer find_timer, lower_timer, upper_timer, equal_range_timer, count_timer;
 286
 287    C c(unique_range.begin(), unique_range.end());
 288
 289    cpu_timer total_time;
 290    total_time.resume();
 291
 292    boost::container::vector<typename C::iterator> v_it(NElements);
 293    boost::container::vector< std::pair<typename C::iterator, typename C::iterator> > v_itp(NElements);
 294
 295    for(std::size_t i = 0; i != NIter; ++i){
 296       //Find
 297       {
 298          find_timer.resume();
 299          for(std::size_t rep = 0; rep != 2; ++rep)
 300          for(std::size_t j = 0, max = unique_range.size(); j != max; ++j){
 301             v_it[j] = c.find(unique_range[j]);
 302          }
 303          find_timer.stop();
 304          if(!check_not_end(v_it, c.end())){
 305             std::cout << "ERROR! find all elements not found" << std::endl;
 306          }
 307       }
 308       //Lower
 309       {
 310          lower_timer.resume();
 311          for(std::size_t rep = 0; rep != 2; ++rep)
 312          for(std::size_t j = 0, max = unique_range.size(); j != max; ++j){
 313             v_it[j] = c.lower_bound(unique_range[j]);
 314          }
 315          lower_timer.stop();
 316          if(!check_not_end(v_it, c.end())){
 317             std::cout << "ERROR! lower_bound all elements not found" << std::endl;
 318          }
 319       }
 320       //Upper
 321       {
 322          upper_timer.resume();
 323          for(std::size_t rep = 0; rep != 2; ++rep)
 324          for(std::size_t j = 0, max = unique_range.size(); j != max; ++j){
 325             v_it[j] = c.upper_bound(unique_range[j]);
 326          }
 327          upper_timer.stop();
 328          if(!check_not_end(v_it, c.end(), 1u)){
 329             std::cout << "ERROR! upper_bound all elements not found" << std::endl;
 330          }
 331       }
 332       //Equal
 333       {
 334          equal_range_timer.resume();
 335          for(std::size_t rep = 0; rep != 2; ++rep)
 336          for(std::size_t j = 0, max = unique_range.size(); j != max; ++j){
 337             v_itp[j] = c.equal_range(unique_range[j]);
 338          }
 339          equal_range_timer.stop();
 340          if(!check_all_not_empty(v_itp)){
 341             std::cout << "ERROR! equal_range all elements not found" << std::endl;
 342          }
 343       }
 344       //Count
 345       {
 346          std::size_t count = 0;
 347          count_timer.resume();
 348          for(std::size_t rep = 0; rep != 2; ++rep)
 349          for(std::size_t j = 0, max = unique_range.size(); j != max; ++j){
 350             count += c.count(unique_range[j]);
 351          }
 352          count_timer.stop();
 353          if(count/2 != c.size()){
 354             std::cout << "ERROR! count all elements not found" << std::endl;
 355          }
 356       }
 357    }
 358    total_time.stop();
 359
 360    std::cout << " Find        " << RangeType << " " << double(find_timer.elapsed().wall)/double(1000000000) << "s\n";
 361    std::cout << " Lower Bound " << RangeType << " " << double(lower_timer.elapsed().wall)/double(1000000000) << "s\n";
 362    std::cout << " Upper Bound " << RangeType << " " << double(upper_timer.elapsed().wall)/double(1000000000) << "s\n";
 363    std::cout << " Equal Range " << RangeType << " " << double(equal_range_timer.elapsed().wall)/double(1000000000) << "s\n";
 364    std::cout << " Count       " << RangeType << " " << double(count_timer.elapsed().wall)/double(1000000000) << "s\n";
 365    std::cout << " Total time =      " << double(total_time.elapsed().wall)/double(1000000000) << "s\n";
 366    return total_time.elapsed();
 367 }
 368
 369 template<typename C>
 370 void extensions_time(boost::container::vector<typename C::value_type> &sorted_unique_range)
 371 {
 372    cpu_timer sur_timer,sur_opt_timer;
 373    sur_timer.stop();sur_opt_timer.stop();
 374
 375    for(std::size_t i = 0; i != NIter; ++i){
 376       {
 377          sur_timer.resume();
 378          C c(sorted_unique_range.begin(), sorted_unique_range.end());
 379          sur_timer.stop();
 380       }
 381       {
 382          sur_opt_timer.resume();
 383          C c(boost::container::ordered_unique_range, sorted_unique_range.begin(), sorted_unique_range.end());
 384          sur_opt_timer.stop();
 385       }
 386
 387    }
 388    std::cout << " Construct sorted_unique_range             " << double(sur_timer.elapsed().wall)/double(1000000000) << "s\n";
 389    std::cout << " Construct sorted_unique_range (extension) " << double(sur_opt_timer.elapsed().wall)/double(1000000000) << "s\n";
 390    std::cout << "Extension/Standard: ";
 391    compare_times(sur_opt_timer.elapsed(), sur_timer.elapsed());
 392 }
 393
 394 template<class BoostClass, class StdClass>
 395 void launch_tests(const char *BoostContName, const char *StdContName)
 396 {
 397    typedef range_provider<typename BoostClass::value_type> get_range_t;
 398
 399    std::cout << std::fixed << std::setw( 11 );
 400    std::cout << "**********************************************" << '\n';
 401    std::cout << "**********************************************" << '\n';
 402    std::cout << '\n';
 403    std::cout << BoostContName << " .VS " <<  StdContName         << '\n';
 404    std::cout << '\n';
 405    std::cout << "**********************************************" << '\n';
 406    std::cout << "**********************************************" << '\n' << std::endl;
 407    {
 408       std::cout << "Copy/Assign/Destroy benchmark:" << BoostContName << std::endl;
 409       cpu_times boost_set_time = copy_destroy_time< BoostClass >(get_range_t::sorted_unique());
 410
 411       std::cout << "Copy/Assign/Destroy benchmark:" << StdContName << std::endl;
 412       cpu_times std_set_time = copy_destroy_time< StdClass >(get_range_t::sorted_unique());
 413
 414       std::cout << BoostContName << "/" << StdContName << ": ";
 415       compare_times(boost_set_time, std_set_time);
 416    }
 417    {
 418       std::cout << "Ordered construct benchmark:" << BoostContName << std::endl;
 419       cpu_times boost_set_time = construct_time< BoostClass >(get_range_t::sorted_unique(), get_range_t::sorted(), "(ord)");
 420
 421       std::cout << "Ordered construct benchmark:" << StdContName << std::endl;
 422       cpu_times std_set_time = construct_time< StdClass >(get_range_t::sorted_unique(), get_range_t::sorted(), "(ord)");;
 423
 424       std::cout << BoostContName << "/" << StdContName << ": ";
 425       compare_times(boost_set_time, std_set_time);
 426    }
 427    {
 428       std::cout << "Random construct benchmark:" << BoostContName << std::endl;
 429       cpu_times boost_set_time = construct_time< BoostClass >(get_range_t::random_unique(), get_range_t::random(), "(rnd)");
 430
 431       std::cout << "Random construct benchmark:" << StdContName << std::endl;
 432       cpu_times std_set_time = construct_time< StdClass >(get_range_t::random_unique(), get_range_t::random(), "(rnd)");;
 433
 434       std::cout << BoostContName << "/" << StdContName << ": ";
 435       compare_times(boost_set_time, std_set_time);
 436    }
 437    {
 438       std::cout << "Ordered Insert benchmark:" << BoostContName << std::endl;
 439       cpu_times boost_set_time = insert_time< BoostClass >(get_range_t::sorted_unique(), get_range_t::sorted(), "(ord)");
 440
 441       std::cout << "Ordered Insert benchmark:" << StdContName << std::endl;
 442       cpu_times std_set_time = insert_time< StdClass >(get_range_t::sorted_unique(), get_range_t::sorted(), "(ord)");
 443
 444       std::cout << BoostContName << "/" << StdContName << ": ";
 445       compare_times(boost_set_time, std_set_time);
 446    }
 447    {
 448       std::cout << "Random Insert benchmark:" << BoostContName << std::endl;
 449       cpu_times boost_set_time = insert_time< BoostClass >(get_range_t::random_unique(), get_range_t::random(), "(rnd)");
 450
 451       std::cout << "Random Insert benchmark:" << StdContName << std::endl;
 452       cpu_times std_set_time = insert_time< StdClass >(get_range_t::random_unique(), get_range_t::random(), "(rnd)");
 453
 454       std::cout << BoostContName << "/" << StdContName << ": ";
 455       compare_times(boost_set_time, std_set_time);
 456    }
 457    {
 458       std::cout << "Ordered Search benchmark:" << BoostContName << std::endl;
 459       cpu_times boost_set_time = search_time< BoostClass >(get_range_t::sorted_unique(), "(ord)");
 460
 461       std::cout << "Ordered Search benchmark:" << StdContName << std::endl;
 462       cpu_times std_set_time = search_time< StdClass >(get_range_t::sorted_unique(), "(ord)");
 463
 464       std::cout << BoostContName << "/" << StdContName << ": ";
 465       compare_times(boost_set_time, std_set_time);
 466    }
 467    {
 468       std::cout << "Random Search benchmark:" << BoostContName << std::endl;
 469       cpu_times boost_set_time = search_time< BoostClass >(get_range_t::random_unique(), "(rnd)");
 470
 471       std::cout << "Random Search benchmark:" << StdContName << std::endl;
 472       cpu_times std_set_time = search_time< StdClass >(get_range_t::random_unique(), "(rnd)");
 473
 474       std::cout << BoostContName << "/" << StdContName << ": ";
 475       compare_times(boost_set_time, std_set_time);
 476    }
 477    {
 478       std::cout << "Extensions benchmark:" << BoostContName << std::endl;
 479       extensions_time< BoostClass >(get_range_t::sorted_unique());
 480    }
 481 }
 482
 483 #endif   //#ifndef BOOST_CONTAINER_BENCH_BENCH_SET_HPP