ceph/src/boost/libs/flyweight/example/perf.cpp

   1 /* Boost.Flyweight example of performance comparison.
   2  *
   3  * Copyright 2006-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/flyweight for library home page.
   9  */
  10
  11 #include <boost/flyweight/flyweight.hpp>
  12 #include <boost/flyweight/hashed_factory.hpp>
  13 #include <boost/flyweight/set_factory.hpp>
  14 #include <boost/flyweight/static_holder.hpp>
  15 #include <boost/flyweight/simple_locking.hpp>
  16 #include <boost/flyweight/refcounted.hpp>
  17 #include <boost/flyweight/no_tracking.hpp>
  18 #include <boost/mpl/bool.hpp>
  19 #include <boost/tokenizer.hpp>
  20 #include <algorithm>
  21 #include <cstddef>
  22 #include <cstdlib>
  23 #include <ctime>
  24 #include <fstream>
  25 #include <iostream>
  26 #include <numeric>
  27 #include <sstream>
  28 #include <string>
  29 #include <vector>
  30
  31 #if defined(BOOST_NO_STDC_NAMESPACE)
  32 namespace std{
  33 using ::clock;
  34 using ::clock_t;
  35 using ::exit;
  36 }
  37 #endif
  38
  39 using namespace boost::flyweights;
  40
  41 /* Instrumented allocator family keeping track of the memory in
  42  * current use.
  43  */
  44
  45 std::size_t count_allocator_mem=0;
  46
  47 template<typename T>
  48 class count_allocator
  49 {
  50 public:
  51   typedef std::size_t     size_type;
  52   typedef std::ptrdiff_t  difference_type;
  53   typedef T*              pointer;
  54   typedef const T*        const_pointer;
  55   typedef T&              reference;
  56   typedef const T&        const_reference;
  57   typedef T               value_type;
  58   template<class U>struct rebind{typedef count_allocator<U> other;};
  59
  60   count_allocator(){}
  61   count_allocator(const count_allocator<T>&){}
  62   template<class U>count_allocator(const count_allocator<U>&,int=0){}
  63
  64   pointer       address(reference x)const{return &x;}
  65   const_pointer address(const_reference x)const{return &x;}
  66
  67   pointer allocate(size_type n,const void* =0)
  68   {
  69     pointer p=(T*)(new char[n*sizeof(T)]);
  70     count_allocator_mem+=n*sizeof(T);
  71     return p;
  72   }
  73
  74   void deallocate(void* p,size_type n)
  75   {
  76     count_allocator_mem-=n*sizeof(T);
  77     delete [](char *)p;
  78   }
  79
  80   size_type max_size() const{return (size_type )(-1);}
  81   void      construct(pointer p,const T& val){new(p)T(val);}
  82   void      destroy(pointer p){p->~T();}
  83
  84   friend bool operator==(const count_allocator&,const count_allocator&)
  85   {
  86     return true;
  87   }
  88
  89   friend bool operator!=(const count_allocator&,const count_allocator&)
  90   {
  91     return false;
  92   }
  93 };
  94
  95 template<>
  96 class count_allocator<void>
  97 {
  98 public:
  99   typedef void*           pointer;
 100   typedef const void*     const_pointer;
 101   typedef void            value_type;
 102   template<class U>struct rebind{typedef count_allocator<U> other;};
 103 };
 104
 105 /* Define some count_allocator-based types and Boost.Flyweight components */
 106
 107 typedef std::basic_string<
 108   char,std::char_traits<char>,count_allocator<char>
 109 > count_string;
 110
 111 typedef hashed_factory<
 112   boost::hash<boost::mpl::_2>,
 113   std::equal_to<boost::mpl::_2>,
 114   count_allocator<boost::mpl::_1>
 115 > count_hashed_factory;
 116
 117 typedef set_factory<
 118   std::less<boost::mpl::_2>,
 119   count_allocator<boost::mpl::_1>
 120 > count_set_factory;
 121
 122 /* Some additional utilities used by the test routine */
 123
 124 class timer
 125 {
 126 public:
 127   timer(){restart();}
 128
 129   void restart(){t=std::clock();}
 130
 131   void time(const char* str)
 132   {
 133     std::cout<<str<<": "<<(double)(std::clock()-t)/CLOCKS_PER_SEC<<" s\n";
 134   }
 135
 136 private:
 137   std::clock_t t;
 138 };
 139
 140 template<typename T>
 141 struct is_flyweight:
 142   boost::mpl::false_{};
 143
 144 template<
 145   typename T,
 146   typename Arg1,typename Arg2,typename Arg3,typename Arg4,typename Arg5
 147 >
 148 struct is_flyweight<flyweight<T,Arg1,Arg2,Arg3,Arg4,Arg5> >:
 149   boost::mpl::true_{};
 150
 151 struct length_adder
 152 {
 153   std::size_t operator()(std::size_t n,const count_string& x)const
 154   {
 155     return n+x.size();
 156   }
 157 };
 158
 159 /* Measure time and memory performance for a String, which is assumed
 160  * to be either a plain string type or a string flyweight.
 161  */
 162
 163 template<typename String>
 164 struct test
 165 {
 166   static std::size_t run(const std::string& file)
 167   {
 168     typedef std::vector<String,count_allocator<String> > count_vector;
 169
 170     /* Define a tokenizer on std::istreambuf. */
 171
 172     typedef std::istreambuf_iterator<char> char_iterator;
 173     typedef boost::tokenizer<
 174       boost::char_separator<char>,
 175       char_iterator
 176     >                                      tokenizer;
 177
 178     std::ifstream ifs(file.c_str());
 179     if(!ifs){
 180       std::cout<<"can't open "<<file<<std::endl;
 181       std::exit(EXIT_FAILURE);
 182     }
 183
 184     /* Initialization; tokenize using space and common punctuaction as
 185      * separators, and keeping the separators.
 186      */
 187
 188     timer t;
 189
 190     tokenizer tok=tokenizer(
 191       char_iterator(ifs),char_iterator(),
 192       boost::char_separator<char>(
 193         "",
 194         "\t\n\r !\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~"));
 195     count_vector txt;
 196     for(tokenizer::iterator it=tok.begin();it!=tok.end();++it){
 197       txt.push_back(String(it->c_str()));
 198     }
 199
 200     t.time("initialization time");
 201
 202     /* Assignment */
 203
 204     t.restart();
 205
 206     count_vector txt2;
 207     for(int i=0;i<10;++i){
 208       txt2.insert(txt2.end(),txt.begin(),txt.end());
 209     }
 210
 211     t.time("assignment time");
 212
 213     /* Equality comparison */
 214
 215     t.restart();
 216
 217     std::size_t c=0;
 218     for(int i=0;i<100;++i){
 219       c+=std::count(txt.begin(),txt.end(),txt[c%txt.size()]);
 220     }
 221
 222     t.time("equality comparison time");
 223
 224     /* Value access */
 225
 226     t.restart();
 227
 228     std::size_t s=0;
 229     for(int i=0;i<20;++i){
 230       s+=std::accumulate(txt2.begin(),txt2.end(),s,length_adder());
 231     }
 232
 233     t.time("value access time");
 234
 235     std::cout<<"bytes used: "<<count_allocator_mem;
 236     if(is_flyweight<String>::value){
 237       std::size_t flyweight_mem=(txt.capacity()+txt2.capacity())*sizeof(String);
 238       std::cout<<"= flyweights("<<flyweight_mem
 239                <<")+values("<<count_allocator_mem-flyweight_mem<<")";
 240     }
 241     std::cout<<"\n";
 242
 243     return c+s;
 244   }
 245 };
 246
 247 /* table of test cases for the user to select from */
 248
 249 struct test_case
 250 {
 251   const char* name;
 252   std::size_t (*test)(const std::string&);
 253 };
 254
 255 test_case test_table[]=
 256 {
 257   {
 258     "simple string",
 259     test<count_string>::run
 260   },
 261   {
 262     "flyweight, hashed factory",
 263     test<flyweight<count_string,count_hashed_factory> >::run
 264   },
 265   {
 266     "flyweight, hashed factory, no tracking",
 267     test<flyweight<count_string,count_hashed_factory,no_tracking> >::run
 268   },
 269   {
 270     "flyweight, set-based factory",
 271     test<flyweight<count_string,count_set_factory> >::run
 272   },
 273   {
 274     "flyweight, set-based factory, no tracking",
 275     test<flyweight<count_string,count_set_factory,no_tracking> >::run
 276   }
 277 };
 278
 279 const int num_test_cases=sizeof(test_table)/sizeof(test_case);
 280
 281 int main()
 282 {
 283   try{
 284     for(int i=0;i<num_test_cases;++i){
 285       std::cout<<i+1<<". "<<test_table[i].name<<"\n";
 286     }
 287     int option=-1;
 288     for(;;){
 289       std::cout<<"select option, enter to exit: ";
 290       std::string str;
 291       std::getline(std::cin,str);
 292       if(str.empty())std::exit(EXIT_SUCCESS);
 293       std::istringstream istr(str);
 294       istr>>option;
 295       if(option>=1&&option<=num_test_cases){
 296         --option; /* pass from 1-based menu to 0-based test_table */
 297         break;
 298       }
 299     }
 300
 301     std::cout<<"enter file name: ";
 302     std::string file;
 303     std::getline(std::cin,file);
 304     std::size_t result=0;
 305     result=test_table[option].test(file);
 306   }
 307   catch(const std::exception& e){
 308     std::cout<<"error: "<<e.what()<<"\n";
 309   }
 310
 311   return 0;
 312 }