ceph/src/boost/libs/intrusive/perf/tree_perf_test.cpp

   1 /////////////////////////////////////////////////////////////////////////////
   2 //
   3 // (C) Copyright Ion Gaztanaga  2007-2013
   4 //
   5 // Distributed under the Boost Software License, Version 1.0.
   6 //    (See accompanying file LICENSE_1_0.txt or copy at
   7 //          http://www.boost.org/LICENSE_1_0.txt)
   8 //
   9 // See http://www.boost.org/libs/intrusive for documentation.
  10 //
  11 /////////////////////////////////////////////////////////////////////////////
  12
  13 //Includes for tests
  14 #include <boost/intrusive/detail/config_begin.hpp>
  15 #include <boost/config.hpp>
  16 #include <iostream>
  17 #include <vector>
  18 #include <boost/intrusive/set.hpp>
  19 #include <boost/intrusive/sg_set.hpp>
  20 #include <boost/intrusive/avl_set.hpp>
  21 #include <boost/date_time/posix_time/posix_time.hpp>
  22 #include <cstdlib>
  23
  24 using namespace boost::posix_time;
  25 using namespace boost::intrusive;
  26
  27 template<bool BigSize>  struct filler        {  int dummy[10];   };
  28 template <>             struct filler<false> {};
  29
  30 template<bool BigSize> //The object for non-intrusive containers
  31 struct test_class :  private filler<BigSize>
  32 {
  33    std::size_t i_;
  34    friend bool operator <(const test_class &l, const test_class &r)  {  return l.i_ < r.i_;  }
  35    friend bool operator >(const test_class &l, const test_class &r)  {  return l.i_ > r.i_;  }
  36 };
  37
  38 template <bool BigSize, class HookType>
  39 struct itest_class   //The object for intrusive containers
  40    :  public HookType,  public test_class<BigSize>
  41 {
  42 };
  43
  44 #ifdef NDEBUG
  45 const std::size_t NumElem = 1000000;
  46 #else
  47 const std::size_t NumElem = 10000;
  48 #endif
  49 const std::size_t NumRepeat = 4;
  50
  51 enum InsertionType
  52 {
  53    Monotonic,
  54    Random
  55 };
  56
  57 template<class Container>
  58 void fill_vector(Container &values, InsertionType insertion_type)
  59 {
  60    switch(insertion_type){
  61       case Monotonic:{
  62          for( typename Container::size_type i = 0, max = values.size()
  63             ; i != max
  64             ; ++i){
  65             values[i].i_ = i;
  66          }
  67       }
  68       break;
  69       case Random:{
  70          std::srand(0);
  71          for( typename Container::size_type i = 0, max = values.size()
  72             ; i != max
  73             ; ++i){
  74             values[i].i_ = i;
  75          }
  76          std::random_shuffle(values.begin(), values.end());
  77       }
  78       break;
  79       default:{
  80          std::abort();
  81       }
  82    }
  83 }
  84
  85 template<class Container>
  86 void test_insertion(Container &c, const char *ContainerName, InsertionType insertion_type)
  87 {
  88    std::cout << "Container " << ContainerName << std::endl;
  89    //Prepare
  90    typedef typename Container::size_type  size_type;
  91    typedef typename Container::value_type value_type;
  92    ptime tini, tend;
  93    std::vector<value_type> values(NumElem);
  94    {
  95       fill_vector(values, insertion_type);
  96       //Insert
  97       tini = microsec_clock::universal_time();
  98       for( size_type repeat = 0, repeat_max = NumRepeat
  99          ; repeat != repeat_max
 100          ; ++repeat){
 101          c.clear();
 102          for( size_type i = 0, max = values.size()
 103             ; i != max
 104             ; ++i){
 105                c.insert(values[i]);
 106          }
 107          if(c.size() != values.size()){
 108             std::cout << "    ERROR: size not consistent" << std::endl;
 109          }
 110       }
 111       tend = microsec_clock::universal_time();
 112       std::cout << "    Insert ns/iter: " << double((tend-tini).total_nanoseconds())/double(NumElem*NumRepeat) << std::endl;
 113    }
 114    //Search
 115    {
 116       value_type v;
 117       tini = microsec_clock::universal_time();
 118       for( size_type repeat = 0, repeat_max = NumRepeat
 119          ; repeat != repeat_max
 120          ; ++repeat){
 121          size_type found = 0;
 122          for( size_type i = 0, max = values.size()
 123             ; i != max
 124             ; ++i){
 125                v.i_ = i;
 126                found += static_cast<size_type>(c.end() != c.find(v));
 127          }
 128          if(found != NumElem){
 129             std::cout << "    ERROR: all not found (" << found << ") vs. (" << NumElem << ")" << std::endl;
 130          }
 131       }
 132       tend = microsec_clock::universal_time();
 133       std::cout << "    Search ns/iter: " << double((tend-tini).total_nanoseconds())/double(NumElem*NumRepeat) << std::endl;
 134    }
 135 }
 136
 137
 138 void test_insert_search(InsertionType insertion_type)
 139 {
 140    {
 141       typedef set_base_hook< link_mode<normal_link> > SetHook;
 142       typedef set< itest_class<true, SetHook> > Set;
 143       Set c;
 144       test_insertion(c, "Set", insertion_type);
 145    }
 146    {
 147       typedef avl_set_base_hook< link_mode<normal_link> > AvlSetHook;
 148       typedef avl_set< itest_class<true, AvlSetHook> > AvlSet;
 149       AvlSet c;
 150       test_insertion(c, "AvlSet", insertion_type);
 151    }
 152    {
 153       typedef bs_set_base_hook< link_mode<normal_link> > BsSetHook;
 154       typedef sg_set< itest_class<true, BsSetHook> > SgSet;
 155       SgSet c;
 156       c.balance_factor(0.55f);
 157       test_insertion(c, "SgSet(alpha 0.55)", insertion_type);
 158    }
 159    {
 160       typedef bs_set_base_hook< link_mode<normal_link> > BsSetHook;
 161       typedef sg_set< itest_class<true, BsSetHook> > SgSet;
 162       SgSet c;
 163       c.balance_factor(0.60f);
 164       test_insertion(c, "SgSet(alpha 0.60)", insertion_type);
 165    }
 166    {
 167       typedef bs_set_base_hook< link_mode<normal_link> > BsSetHook;
 168       typedef sg_set< itest_class<true, BsSetHook> > SgSet;
 169       SgSet c;
 170       c.balance_factor(0.65f);
 171       test_insertion(c, "SgSet(alpha 0.65)", insertion_type);
 172    }
 173    {
 174       typedef bs_set_base_hook< link_mode<normal_link> > BsSetHook;
 175       typedef sg_set< itest_class<true, BsSetHook> > SgSet;
 176       SgSet c;
 177       test_insertion(c, "SgSet(alpha 0.7)", insertion_type);
 178    }
 179    {
 180       typedef bs_set_base_hook< link_mode<normal_link> > BsSetHook;
 181       typedef sg_set< itest_class<true, BsSetHook> > SgSet;
 182       SgSet c;
 183       c.balance_factor(0.75f);
 184       test_insertion(c, "SgSet(alpha 0.75)", insertion_type);
 185    }
 186    {
 187       typedef bs_set_base_hook< link_mode<normal_link> > BsSetHook;
 188       typedef sg_set< itest_class<true, BsSetHook> > SgSet;
 189       SgSet c;
 190       c.balance_factor(0.80f);
 191       test_insertion(c, "SgSet(alpha 0.80)", insertion_type);
 192    }
 193    {
 194       typedef bs_set_base_hook< link_mode<normal_link> > BsSetHook;
 195       typedef sg_set< itest_class<true, BsSetHook>, floating_point<false> > SgSet;
 196       SgSet c;
 197       test_insertion(c, "SgSet(no float, alpha 1/sqrt(2)~0,7071)", insertion_type);
 198    }
 199 }
 200
 201 int main()
 202 {
 203    std::cout << "MONOTONIC INPUTS\n";
 204    std::cout << "----------------\n\n";
 205    test_insert_search(Monotonic);
 206    std::cout << "----------------\n\n";
 207    std::cout << "RANDOM INPUTS\n";
 208    std::cout << "----------------\n\n";
 209    test_insert_search(Random);
 210    std::cout << "----------------\n\n";
 211    return 0;
 212 }
 213
 214 #include <boost/intrusive/detail/config_end.hpp>