libs/multi_index/perf/test_perf.cpp

   1 /* Boost.MultiIndex performance test.
   2  *
   3  * Copyright 2003-2008 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(
 343   const char* title
 344   BOOST_APPEND_EXPLICIT_TEMPLATE_TYPE(IndexedTest)
 345   BOOST_APPEND_EXPLICIT_TEMPLATE_TYPE(ManualTest))
 346 {
 347   cout<<fixed<<setprecision(2);
 348   cout<<title<<endl;
 349   int n=1000;
 350   for(int i=0;i<3;++i){
 351     double indexed_t=measure(IndexedTest(n));
 352     double manual_t=measure(ManualTest(n));
 353     cout<<"  10^"<<i+3<<" elmts: "
 354         <<setw(6)<<100.0*indexed_t/manual_t<<"% "
 355         <<"("
 356           <<setw(6)<<1000.0*indexed_t/CLOCKS_PER_SEC<<" ms / "
 357           <<setw(6)<<1000.0*manual_t/CLOCKS_PER_SEC<<" ms)"
 358         <<endl;
 359     n*=10;
 360   }
 361
 362   size_t indexed_t_node_size=IndexedTest::multi_index_node_size();
 363   size_t manual_t_node_size=ManualTest::node_size();
 364
 365   if(manual_t_node_size){
 366     cout<<"  space gain: "
 367         <<setw(6)<<100.0*indexed_t_node_size/manual_t_node_size<<"%"<<endl;
 368   }
 369 }
 370
 371 /* compare_structures accept a multi_index_container instantiation and
 372  * several standard containers, builds a manual simulation out of the
 373  * latter and run the tests.
 374  */
 375
 376 template <typename IndexedType,typename ManualType>
 377 void compare_structures(
 378   const char* title
 379   BOOST_APPEND_EXPLICIT_TEMPLATE_TYPE(IndexedType)
 380   BOOST_APPEND_EXPLICIT_TEMPLATE_TYPE(ManualType))
 381 {
 382   run_tests<
 383     mono_container<IndexedType>,
 384     mono_container<ManualType>
 385   >(title);
 386 }
 387
 388 template <typename IndexedType,typename ManualType1,typename ManualType2>
 389 void compare_structures2(
 390   const char* title
 391   BOOST_APPEND_EXPLICIT_TEMPLATE_TYPE(IndexedType)
 392   BOOST_APPEND_EXPLICIT_TEMPLATE_TYPE(ManualType1)
 393   BOOST_APPEND_EXPLICIT_TEMPLATE_TYPE(ManualType2))
 394 {
 395   run_tests<
 396     mono_container<IndexedType>,
 397     bi_container<ManualType1,ManualType2>
 398   >(title);
 399 }
 400
 401 template <
 402   typename IndexedType,
 403   typename ManualType1,typename ManualType2,typename ManualType3
 404 >
 405 void compare_structures3(
 406   const char* title
 407   BOOST_APPEND_EXPLICIT_TEMPLATE_TYPE(IndexedType)
 408   BOOST_APPEND_EXPLICIT_TEMPLATE_TYPE(ManualType1)
 409   BOOST_APPEND_EXPLICIT_TEMPLATE_TYPE(ManualType2)
 410   BOOST_APPEND_EXPLICIT_TEMPLATE_TYPE(ManualType3))
 411 {
 412   run_tests<
 413     mono_container<IndexedType>,
 414     tri_container<ManualType1,ManualType2,ManualType3>
 415   >(title);
 416 }
 417
 418 int main()
 419 {
 420   {
 421     /* 1 ordered index */
 422
 423     typedef multi_index_container<int> indexed_t;
 424     typedef set<int>                   manual_t;
 425     indexed_t dummy; /* MSVC++ 6.0 chokes if indexed_t is not instantiated */
 426
 427     compare_structures<indexed_t,manual_t>(
 428       "1 ordered index");
 429   }
 430   {
 431     /* 1 sequenced index */
 432
 433     typedef list_wrapper<
 434       multi_index_container<
 435         int,
 436         indexed_by<sequenced<> >
 437       >
 438     >                                  indexed_t;
 439     typedef list_wrapper<list<int> >   manual_t;
 440     indexed_t dummy; /* MSVC++ 6.0 chokes if indexed_t is not instantiated */
 441
 442     compare_structures<indexed_t,manual_t>(
 443       "1 sequenced index");
 444   }
 445   {
 446     /* 2 ordered indices */
 447
 448     typedef multi_index_container<
 449       int,
 450       indexed_by<
 451         ordered_unique<identity<int> >,
 452         ordered_non_unique<identity<int> >
 453       >
 454     >                                  indexed_t;
 455     typedef set<int>                   manual_t1;
 456     typedef multiset<
 457       manual_t1::iterator,
 458       it_compare<
 459         manual_t1::iterator,
 460         manual_t1::key_compare
 461       >
 462     >                                  manual_t2;
 463     indexed_t dummy; /* MSVC++ 6.0 chokes if indexed_t is not instantiated */
 464
 465     compare_structures2<indexed_t,manual_t1,manual_t2>(
 466       "2 ordered indices");
 467   }
 468   {
 469     /* 1 ordered index + 1 sequenced index */
 470
 471     typedef multi_index_container<
 472       int,
 473       indexed_by<
 474         boost::multi_index::ordered_unique<identity<int> >,
 475         sequenced<>
 476       >
 477     >                                  indexed_t;
 478     typedef list_wrapper<
 479       list<int>
 480     >                                  manual_t1;
 481     typedef multiset<
 482       manual_t1::iterator,
 483       it_compare<
 484         manual_t1::iterator,
 485         std::less<int>
 486       >
 487     >                                  manual_t2;
 488     indexed_t dummy; /* MSVC++ 6.0 chokes if indexed_t is not instantiated */
 489
 490     compare_structures2<indexed_t,manual_t1,manual_t2>(
 491       "1 ordered index + 1 sequenced index");
 492   }
 493   {
 494     /* 3 ordered indices */
 495
 496     typedef multi_index_container<
 497       int,
 498       indexed_by<
 499         ordered_unique<identity<int> >,
 500         ordered_non_unique<identity<int> >,
 501         ordered_non_unique<identity<int> >
 502       >
 503     >                                  indexed_t;
 504     typedef set<int>                   manual_t1;
 505     typedef multiset_wrapper<
 506       multiset<
 507         manual_t1::iterator,
 508         it_compare<
 509           manual_t1::iterator,
 510           manual_t1::key_compare
 511         >
 512       >
 513     >                                  manual_t2;
 514     typedef multiset<
 515       manual_t2::iterator,
 516       it_compare<
 517         manual_t2::iterator,
 518         manual_t2::key_compare
 519       >
 520     >                                  manual_t3;
 521     indexed_t dummy; /* MSVC++ 6.0 chokes if indexed_t is not instantiated */
 522
 523     compare_structures3<indexed_t,manual_t1,manual_t2,manual_t3>(
 524       "3 ordered indices");
 525   }
 526   {
 527     /* 2 ordered indices + 1 sequenced index */
 528
 529     typedef multi_index_container<
 530       int,
 531       indexed_by<
 532         ordered_unique<identity<int> >,
 533         ordered_non_unique<identity<int> >,
 534         sequenced<>
 535       >
 536     >                                  indexed_t;
 537     typedef list_wrapper<
 538       list<int>
 539     >                                  manual_t1;
 540     typedef multiset_wrapper<
 541       multiset<
 542         manual_t1::iterator,
 543         it_compare<
 544           manual_t1::iterator,
 545           std::less<int>
 546         >
 547       >
 548     >                                  manual_t2;
 549     typedef multiset<
 550       manual_t2::iterator,
 551       it_compare<
 552         manual_t2::iterator,
 553         manual_t2::key_compare
 554       >
 555     >                                  manual_t3;
 556     indexed_t dummy; /* MSVC++ 6.0 chokes if indexed_t is not instantiated */
 557
 558     compare_structures3<indexed_t,manual_t1,manual_t2,manual_t3>(
 559       "2 ordered indices + 1 sequenced index");
 560   }
 561
 562   return 0;
 563 }