libs/multi_index/perf/test_perf.cpp

   1 /* Boost.MultiIndex performance test.
   2  *
   3  * Copyright 2003-2013 Joaquin M Lopez Munoz.
   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/multi_index for library home page.
   9  */
  10
  11 #include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
  12
  13 #include <algorithm>
  14 #include <assert.h>
  15 #include <boost/multi_index_container.hpp>
  16 #include <boost/multi_index/identity.hpp>
  17 #include <boost/multi_index/ordered_index.hpp>
  18 #include <boost/multi_index/sequenced_index.hpp>
  19 #include <boost/next_prior.hpp>
  20 #include <climits>
  21 #include <ctime>
  22 #include <iomanip>
  23 #include <iostream>
  24 #include <list>
  25 #include <set>
  26 #include <string>
  27 #include <vector>
  28
  29 using namespace std;
  30 using namespace boost::multi_index;
  31
  32 /* Measurement harness by Andrew Koenig, extracted from companion code to
  33  *   Stroustrup, B.: "Wrapping C++ Member Function Calls", The C++ Report,
  34  *     June 2000, Vol 12/No 6.
  35  * Original code retrievable at: http://www.research.att.com/~bs/wrap_code.cpp
  36  */
  37
  38 // How many clock units does it take to interrogate the clock?
  39 static double clock_overhead()
  40 {
  41     clock_t k = clock(), start, limit;
  42
  43     // Wait for the clock to tick
  44     do start = clock();
  45     while (start == k);
  46
  47     // interrogate the clock until it has advanced at least a second
  48     // (for reasonable accuracy)
  49     limit = start + CLOCKS_PER_SEC;
  50
  51     unsigned long r = 0;
  52     while ((k = clock()) < limit)
  53         ++r;
  54
  55     return double(k - start) / r;
  56 }
  57
  58 // We'd like the odds to be factor:1 that the result is
  59 // within percent% of the median
  60 const int factor = 10;
  61 const int percent = 20;
  62
  63 // Measure a function (object) factor*2 times,
  64 // appending the measurements to the second argument
  65 template<class F>
  66 void measure_aux(F f, vector<double>& mv)
  67 {
  68     static double ovhd = clock_overhead();
  69
  70     // Ensure we don't reallocate in mid-measurement
  71     mv.reserve(mv.size() + factor*2);
  72
  73     // Wait for the clock to tick
  74     clock_t k = clock();
  75     clock_t start;
  76
  77     do start = clock();
  78     while (start == k);
  79
  80     // Do 2*factor measurements
  81     for (int i = 2*factor; i; --i) {
  82         unsigned long count = 0, limit = 1, tcount = 0;
  83
  84         // Original code used CLOCKS_PER_SEC/100
  85         const clock_t clocklimit = start + CLOCKS_PER_SEC/10;
  86         clock_t t;
  87
  88         do {
  89             while (count < limit) {
  90                 f();
  91                 ++count;
  92             }
  93             limit *= 2;
  94             ++tcount;
  95         } while ((t = clock()) < clocklimit);
  96
  97         // Wait for the clock to tick again;
  98         clock_t t2;
  99         do ++tcount;
 100         while ((t2 = clock()) == t);
 101
 102         // Append the measurement to the vector
 103         mv.push_back(((t2 - start) - (tcount * ovhd)) / count);
 104
 105         // Establish a new starting point
 106         start = t2;
 107     }
 108 }
 109
 110 // Returns the number of clock units per iteration
 111 // With odds of factor:1, the measurement is within percent% of
 112 // the value returned, which is also the median of all measurements.
 113 template<class F>
 114 double measure(F f)
 115 {
 116     vector<double> mv;
 117
 118     int n = 0;                        // iteration counter
 119     do {
 120         ++n;
 121
 122         // Try 2*factor measurements
 123         measure_aux(f, mv);
 124         assert(mv.size() == 2*n*factor);
 125
 126         // Compute the median.  We know the size is even, so we cheat.
 127         sort(mv.begin(), mv.end());
 128         double median = (mv[n*factor] + mv[n*factor-1])/2;
 129
 130         // If the extrema are within threshold of the median, we're done
 131         if (mv[n] > (median * (100-percent))/100 &&
 132             mv[mv.size() - n - 1] < (median * (100+percent))/100)
 133             return median;
 134
 135     } while (mv.size() < factor * 200);
 136
 137     // Give up!
 138     clog << "Help!\n\n";
 139     exit(1);
 140 }
 141
 142 /* dereferencing compare predicate */
 143
 144 template <typename Iterator,typename Compare>
 145 struct it_compare
 146 {
 147   bool operator()(const Iterator& x,const Iterator& y)const{return comp(*x,*y);}
 148
 149 private:
 150   Compare comp;
 151 };
 152
 153 /* list_wrapper and multiset_wrapper adapt std::lists and std::multisets
 154  * to make them conform to a set-like insert interface which test
 155  * routines do assume.
 156  */
 157
 158 template <typename List>
 159 struct list_wrapper:List
 160 {
 161   typedef typename List::value_type value_type;
 162   typedef typename List::iterator   iterator;
 163
 164   pair<iterator,bool> insert(const value_type& v)
 165   {
 166     List::push_back(v);
 167     return pair<iterator,bool>(boost::prior(List::end()),true);
 168   }
 169 };
 170
 171 template <typename Multiset>
 172 struct multiset_wrapper:Multiset
 173 {
 174   typedef typename Multiset::value_type value_type;
 175   typedef typename Multiset::iterator   iterator;
 176
 177   pair<iterator,bool> insert(const value_type& v)
 178   {
 179     return pair<iterator,bool>(Multiset::insert(v),true);
 180   }
 181 };
 182
 183 /* space comsumption of manual simulations is determined by checking
 184  * the node sizes of the containers involved. This cannot be done in a
 185  * portable manner, so node_size has to be written on a per stdlibrary
 186  * basis. Add your own versions if necessary.
 187  */
 188
 189 #if defined(BOOST_DINKUMWARE_STDLIB)
 190
 191 template<typename Container>
 192 size_t node_size(const Container&)
 193 {
 194   return sizeof(*Container().begin()._Mynode());
 195 }
 196
 197 #elif defined(__GLIBCPP__) || defined(__GLIBCXX__)
 198
 199 template<typename Container>
 200 size_t node_size(const Container&)
 201 {
 202   typedef typename Container::iterator::_Link_type node_ptr;
 203   node_ptr p=0;
 204   return sizeof(*p);
 205 }
 206
 207 template<typename Value,typename Allocator>
 208 size_t node_size(const list<Value,Allocator>&)
 209 {
 210   return sizeof(typename list<Value,Allocator>::iterator::_Node);
 211 }
 212
 213 template<typename List>
 214 size_t node_size(const list_wrapper<List>&)
 215 {
 216   return sizeof(typename List::iterator::_Node);
 217 }
 218
 219 #else
 220
 221 /* default version returns 0 by convention */
 222
 223 template<typename Container>
 224 size_t node_size(const Container&)
 225 {
 226   return 0;
 227 }
 228
 229 #endif
 230
 231 /* mono_container runs the tested routine on multi_index and manual
 232  * simulations comprised of one standard container.
 233  * bi_container and tri_container run the equivalent routine for manual
 234  * compositions of two and three standard containers, respectively.
 235  */
 236
 237 template <typename Container>
 238 struct mono_container
 239 {
 240   mono_container(int n_):n(n_){}
 241
 242   void operator()()
 243   {
 244     typedef typename Container::iterator iterator;
 245
 246     Container c;
 247
 248     for(int i=0;i<n;++i)c.insert(i);
 249     for(iterator it=c.begin();it!=c.end();)c.erase(it++);
 250   }
 251
 252   static size_t multi_index_node_size()
 253   {
 254     return sizeof(*Container().begin().get_node());
 255   }
 256
 257   static size_t node_size()
 258   {
 259     return ::node_size(Container());
 260   }
 261
 262 private:
 263   int n;
 264 };
 265
 266 template <typename Container1,typename Container2>
 267 struct bi_container
 268 {
 269   bi_container(int n_):n(n_){}
 270
 271   void operator()()
 272   {
 273     typedef typename Container1::iterator iterator1;
 274     typedef typename Container2::iterator iterator2;
 275
 276     Container1 c1;
 277     Container2 c2;
 278
 279     for(int i=0;i<n;++i){
 280       iterator1 it1=c1.insert(i).first;
 281       c2.insert(it1);
 282     }
 283     for(iterator2 it2=c2.begin();it2!=c2.end();)
 284     {
 285       c1.erase(*it2);
 286       c2.erase(it2++);
 287     }
 288   }
 289
 290   static size_t node_size()
 291   {
 292     return ::node_size(Container1())+::node_size(Container2());
 293   }
 294
 295 private:
 296   int n;
 297 };
 298
 299 template <typename Container1,typename Container2,typename Container3>
 300 struct tri_container
 301 {
 302   tri_container(int n_):n(n_){}
 303
 304   void operator()()
 305   {
 306     typedef typename Container1::iterator iterator1;
 307     typedef typename Container2::iterator iterator2;
 308     typedef typename Container3::iterator iterator3;
 309
 310     Container1 c1;
 311     Container2 c2;
 312     Container3 c3;
 313
 314     for(int i=0;i<n;++i){
 315       iterator1 it1=c1.insert(i).first;
 316       iterator2 it2=c2.insert(it1).first;
 317       c3.insert(it2);
 318     }
 319     for(iterator3 it3=c3.begin();it3!=c3.end();)
 320     {
 321       c1.erase(**it3);
 322       c2.erase(*it3);
 323       c3.erase(it3++);
 324     }
 325   }
 326
 327   static size_t node_size()
 328   {
 329     return ::node_size(Container1())+
 330            ::node_size(Container2())+::node_size(Container3());
 331   }
 332
 333 private:
 334   int n;
 335 };
 336
 337 /* measure and compare two routines for several numbers of elements
 338  * and also estimates relative memory consumption.
 339  */
 340
 341 template <typename IndexedTest,typename ManualTest>
 342 void run_tests(const char* title)
 343 {
 344   cout<<fixed<<setprecision(2);
 345   cout<<title<<endl;
 346   int n=1000;
 347   for(int i=0;i<3;++i){
 348     double indexed_t=measure(IndexedTest(n));
 349     double manual_t=measure(ManualTest(n));
 350     cout<<"  10^"<<i+3<<" elmts: "
 351         <<setw(6)<<100.0*indexed_t/manual_t<<"% "
 352         <<"("
 353           <<setw(6)<<1000.0*indexed_t/CLOCKS_PER_SEC<<" ms / "
 354           <<setw(6)<<1000.0*manual_t/CLOCKS_PER_SEC<<" ms)"
 355         <<endl;
 356     n*=10;
 357   }
 358
 359   size_t indexed_t_node_size=IndexedTest::multi_index_node_size();
 360   size_t manual_t_node_size=ManualTest::node_size();
 361
 362   if(manual_t_node_size){
 363     cout<<"  space gain: "
 364         <<setw(6)<<100.0*indexed_t_node_size/manual_t_node_size<<"%"<<endl;
 365   }
 366 }
 367
 368 /* compare_structures accept a multi_index_container instantiation and
 369  * several standard containers, builds a manual simulation out of the
 370  * latter and run the tests.
 371  */
 372
 373 template <typename IndexedType,typename ManualType>
 374 void compare_structures(const char* title)
 375 {
 376   run_tests<
 377     mono_container<IndexedType>,
 378     mono_container<ManualType>
 379   >(title);
 380 }
 381
 382 template <typename IndexedType,typename ManualType1,typename ManualType2>
 383 void compare_structures2(const char* title)
 384 {
 385   run_tests<
 386     mono_container<IndexedType>,
 387     bi_container<ManualType1,ManualType2>
 388   >(title);
 389 }
 390
 391 template <
 392   typename IndexedType,
 393   typename ManualType1,typename ManualType2,typename ManualType3
 394 >
 395 void compare_structures3(const char* title)
 396 {
 397   run_tests<
 398     mono_container<IndexedType>,
 399     tri_container<ManualType1,ManualType2,ManualType3>
 400   >(title);
 401 }
 402
 403 int main()
 404 {
 405   /* some stdlibs provide the discussed but finally rejected std::identity */
 406   using boost::multi_index::identity;
 407
 408   {
 409     /* 1 ordered index */
 410
 411     typedef multi_index_container<int> indexed_t;
 412     typedef set<int>                   manual_t;
 413
 414     compare_structures<indexed_t,manual_t>(
 415       "1 ordered index");
 416   }
 417   {
 418     /* 1 sequenced index */
 419
 420     typedef list_wrapper<
 421       multi_index_container<
 422         int,
 423         indexed_by<sequenced<> >
 424       >
 425     >                                  indexed_t;
 426     typedef list_wrapper<list<int> >   manual_t;
 427
 428     compare_structures<indexed_t,manual_t>(
 429       "1 sequenced index");
 430   }
 431   {
 432     /* 2 ordered indices */
 433
 434     typedef multi_index_container<
 435       int,
 436       indexed_by<
 437         ordered_unique<identity<int> >,
 438         ordered_non_unique<identity<int> >
 439       >
 440     >                                  indexed_t;
 441     typedef set<int>                   manual_t1;
 442     typedef multiset<
 443       manual_t1::iterator,
 444       it_compare<
 445         manual_t1::iterator,
 446         manual_t1::key_compare
 447       >
 448     >                                  manual_t2;
 449
 450     compare_structures2<indexed_t,manual_t1,manual_t2>(
 451       "2 ordered indices");
 452   }
 453   {
 454     /* 1 ordered index + 1 sequenced index */
 455
 456     typedef multi_index_container<
 457       int,
 458       indexed_by<
 459         boost::multi_index::ordered_unique<identity<int> >,
 460         sequenced<>
 461       >
 462     >                                  indexed_t;
 463     typedef list_wrapper<
 464       list<int>
 465     >                                  manual_t1;
 466     typedef multiset<
 467       manual_t1::iterator,
 468       it_compare<
 469         manual_t1::iterator,
 470         std::less<int>
 471       >
 472     >                                  manual_t2;
 473
 474     compare_structures2<indexed_t,manual_t1,manual_t2>(
 475       "1 ordered index + 1 sequenced index");
 476   }
 477   {
 478     /* 3 ordered indices */
 479
 480     typedef multi_index_container<
 481       int,
 482       indexed_by<
 483         ordered_unique<identity<int> >,
 484         ordered_non_unique<identity<int> >,
 485         ordered_non_unique<identity<int> >
 486       >
 487     >                                  indexed_t;
 488     typedef set<int>                   manual_t1;
 489     typedef multiset_wrapper<
 490       multiset<
 491         manual_t1::iterator,
 492         it_compare<
 493           manual_t1::iterator,
 494           manual_t1::key_compare
 495         >
 496       >
 497     >                                  manual_t2;
 498     typedef multiset<
 499       manual_t2::iterator,
 500       it_compare<
 501         manual_t2::iterator,
 502         manual_t2::key_compare
 503       >
 504     >                                  manual_t3;
 505
 506     compare_structures3<indexed_t,manual_t1,manual_t2,manual_t3>(
 507       "3 ordered indices");
 508   }
 509   {
 510     /* 2 ordered indices + 1 sequenced index */
 511
 512     typedef multi_index_container<
 513       int,
 514       indexed_by<
 515         ordered_unique<identity<int> >,
 516         ordered_non_unique<identity<int> >,
 517         sequenced<>
 518       >
 519     >                                  indexed_t;
 520     typedef list_wrapper<
 521       list<int>
 522     >                                  manual_t1;
 523     typedef multiset_wrapper<
 524       multiset<
 525         manual_t1::iterator,
 526         it_compare<
 527           manual_t1::iterator,
 528           std::less<int>
 529         >
 530       >
 531     >                                  manual_t2;
 532     typedef multiset<
 533       manual_t2::iterator,
 534       it_compare<
 535         manual_t2::iterator,
 536         manual_t2::key_compare
 537       >
 538     >                                  manual_t3;
 539
 540     compare_structures3<indexed_t,manual_t1,manual_t2,manual_t3>(
 541       "2 ordered indices + 1 sequenced index");
 542   }
 543
 544   return 0;
 545 }