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

   1 /* Copyright 2016-2017 Joaquin M Lopez Munoz.
   2  * Distributed under the Boost Software License, Version 1.0.
   3  * (See accompanying file LICENSE_1_0.txt or copy at
   4  * http://www.boost.org/LICENSE_1_0.txt)
   5  *
   6  * See http://www.boost.org/libs/poly_collection for library home page.
   7  */
   8
   9 /* Boost.PolyCollection performance tests */
  10
  11 #include <algorithm>
  12 #include <array>
  13 #include <chrono>
  14 #include <cmath>
  15 #include <numeric>
  16
  17 std::chrono::high_resolution_clock::time_point measure_start,measure_pause;
  18
  19 template<typename F>
  20 double measure(F f)
  21 {
  22   using namespace std::chrono;
  23
  24   static const int              num_trials=10;
  25   static const milliseconds     min_time_per_trial(200);
  26   std::array<double,num_trials> trials;
  27   volatile decltype(f())        res; /* to avoid optimizing f() away */
  28
  29   for(int i=0;i<num_trials;++i){
  30     int                               runs=0;
  31     high_resolution_clock::time_point t2;
  32
  33     measure_start=high_resolution_clock::now();
  34     do{
  35       res=f();
  36       ++runs;
  37       t2=high_resolution_clock::now();
  38     }while(t2-measure_start<min_time_per_trial);
  39     trials[i]=duration_cast<duration<double>>(t2-measure_start).count()/runs;
  40   }
  41   (void)res; /* var not used warn */
  42
  43   std::sort(trials.begin(),trials.end());
  44   return std::accumulate(
  45     trials.begin()+2,trials.end()-2,0.0)/(trials.size()-4);
  46 }
  47
  48 template<typename F>
  49 double measure(unsigned int n,F f)
  50 {
  51   double t=measure(f);
  52   return (t/n)*10E9;
  53 }
  54
  55 void pause_timing()
  56 {
  57   measure_pause=std::chrono::high_resolution_clock::now();
  58 }
  59
  60 void resume_timing()
  61 {
  62   measure_start+=std::chrono::high_resolution_clock::now()-measure_pause;
  63 }
  64
  65 #include <algorithm>
  66 #include <array>
  67 #include <boost/poly_collection/algorithm.hpp>
  68 #include <boost/poly_collection/any_collection.hpp>
  69 #include <boost/poly_collection/base_collection.hpp>
  70 #include <boost/poly_collection/function_collection.hpp>
  71 #include <boost/ptr_container/ptr_container.hpp>
  72 #include <boost/type_erasure/any.hpp>
  73 #include <boost/type_erasure/callable.hpp>
  74 #include <boost/type_erasure/builtin.hpp>
  75 #include <boost/type_erasure/operators.hpp>
  76 #include <boost/type_erasure/typeid_of.hpp>
  77 #include <functional>
  78 #include <random>
  79 #include <string>
  80 #include <utility>
  81 #include <vector>
  82
  83 //[perf_base_types
  84 struct base
  85 {
  86   virtual ~base()=default;
  87   virtual int operator()(int)const=0;
  88 };
  89
  90 struct derived1 final:base
  91 {
  92   derived1(int n):n{n}{}
  93   virtual int operator()(int)const{return n;}
  94
  95   int n;
  96 };
  97
  98 struct derived2 final:base
  99 {
 100   derived2(int n):n{n}{}
 101   virtual int operator()(int x)const{return x*n;}
 102
 103   int unused,n;
 104 };
 105
 106 struct derived3 final:base
 107 {
 108   derived3(int n):n{n}{}
 109   virtual int operator()(int x)const{return x*x*n;}
 110
 111   int unused,n;
 112 };
 113 //]
 114
 115 //[perf_function_types
 116 struct concrete1
 117 {
 118   concrete1(int n):n{n}{}
 119   int operator()(int)const{return n;}
 120
 121   int n;
 122 };
 123
 124 struct concrete2
 125 {
 126   concrete2(int n):n{n}{}
 127   int operator()(int x)const{return x*n;}
 128
 129   int unused,n;
 130 };
 131
 132 struct concrete3
 133 {
 134   concrete3(int n):n{n}{}
 135   int operator()(int x)const{return x*x*n;}
 136
 137   int unused,n;
 138 };
 139 //]
 140
 141 template<typename Base>
 142 struct ptr_vector:boost::ptr_vector<Base>
 143 {
 144 public:
 145   template<typename T>
 146   void insert(const T& x)
 147   {
 148     this->push_back(new T{x});
 149   }
 150
 151   template<typename F>
 152   void for_each(F f)
 153   {
 154     std::for_each(this->begin(),this->end(),f);
 155   }
 156
 157   void prepare_for_for_each(){}
 158 };
 159
 160 template<typename Base>
 161 struct sorted_ptr_vector:ptr_vector<Base>
 162 {
 163   void prepare_for_for_each()
 164   {
 165     std::sort(
 166       this->c_array(),this->c_array()+this->size(),
 167       [](Base* x,Base* y){return typeid(*x).before(typeid(*y));});
 168   }
 169 };
 170
 171 template<typename Base>
 172 struct shuffled_ptr_vector:ptr_vector<Base>
 173 {
 174   void prepare_for_for_each()
 175   {
 176     std::shuffle(
 177      this->c_array(),this->c_array()+this->size(),std::mt19937(1));
 178   }
 179 };
 180
 181 template<typename Base>
 182 struct base_collection:boost::base_collection<Base>
 183 {
 184   template<typename F>
 185   void for_each(F f)
 186   {
 187     std::for_each(this->begin(),this->end(),f);
 188   }
 189
 190   void prepare_for_for_each(){}
 191 };
 192
 193 template<typename Base,typename... T>
 194 struct poly_for_each_base_collection:base_collection<Base>
 195 {
 196   template<typename F>
 197   void for_each(F f)
 198   {
 199     boost::poly_collection::for_each<T...>(this->begin(),this->end(),f);
 200   }
 201 };
 202
 203 template<typename Signature>
 204 struct func_vector:std::vector<std::function<Signature>>
 205 {
 206   template<typename T> void insert(const T& x)
 207   {
 208     this->push_back(x);
 209   }
 210
 211   template<typename F>
 212   void for_each(F f)
 213   {
 214     std::for_each(this->begin(),this->end(),f);
 215   }
 216
 217   void prepare_for_for_each(){}
 218 };
 219
 220 template<typename Signature>
 221 struct sorted_func_vector:func_vector<Signature>
 222 {
 223   void prepare_for_for_each()
 224   {
 225     using value_type=typename sorted_func_vector::value_type;
 226     std::sort(
 227       this->begin(),this->end(),[](const value_type& x,const value_type& y){
 228         return x.target_type().before(y.target_type());
 229       });
 230   }
 231 };
 232
 233 template<typename Signature>
 234 struct shuffled_func_vector:func_vector<Signature>
 235 {
 236   void prepare_for_for_each()
 237   {
 238     std::shuffle(this->begin(),this->end(),std::mt19937(1));
 239   }
 240 };
 241
 242 template<typename Signature>
 243 struct func_collection:boost::function_collection<Signature>
 244 {
 245   template<typename F>
 246   void for_each(F f)
 247   {
 248     std::for_each(this->begin(),this->end(),f);
 249   }
 250
 251   void prepare_for_for_each(){}
 252 };
 253
 254 template<typename Signature,typename... T>
 255 struct poly_for_each_func_collection:func_collection<Signature>
 256 {
 257   template<typename F>
 258   void for_each(F f)
 259   {
 260     boost::poly_collection::for_each<T...>(this->begin(),this->end(),f);
 261   }
 262 };
 263
 264 template<typename Concept>
 265 struct any_vector:std::vector<boost::type_erasure::any<Concept>>
 266 {
 267   template<typename T> void insert(const T& x)
 268   {
 269     this->push_back(x);
 270   }
 271
 272   template<typename F>
 273   void for_each(F f)
 274   {
 275     std::for_each(this->begin(),this->end(),f);
 276   }
 277
 278   void prepare_for_for_each(){}
 279 };
 280
 281 template<typename Concept>
 282 struct sorted_any_vector:any_vector<Concept>
 283 {
 284   void prepare_for_for_each()
 285   {
 286     using value_type=typename sorted_any_vector::value_type;
 287     std::sort(
 288       this->begin(),this->end(),[](const value_type& x,const value_type& y){
 289         return typeid_of(x).before(typeid_of(y));
 290       });
 291   }
 292 };
 293
 294 template<typename Concept>
 295 struct shuffled_any_vector:any_vector<Concept>
 296 {
 297   void prepare_for_for_each()
 298   {
 299     std::shuffle(this->begin(),this->end(),std::mt19937(1));
 300   }
 301 };
 302
 303 template<typename Concept>
 304 struct any_collection:boost::any_collection<Concept>
 305 {
 306   template<typename F>
 307   void for_each(F f)
 308   {
 309     std::for_each(this->begin(),this->end(),f);
 310   }
 311
 312   void prepare_for_for_each(){}
 313 };
 314
 315 template<typename Concept,typename... T>
 316 struct poly_for_each_any_collection:any_collection<Concept>
 317 {
 318   template<typename F>
 319   void for_each(F f)
 320   {
 321     boost::poly_collection::for_each<T...>(this->begin(),this->end(),f);
 322   }
 323 };
 324
 325 #include <iostream>
 326
 327 template<typename... Printables>
 328 void print(Printables... ps)
 329 {
 330   const char* delim="";
 331   using seq=int[1+sizeof...(ps)];
 332   (void)seq{0,(std::cout<<delim<<ps,delim=";",0)...};
 333   std::cout<<"\n";
 334 }
 335
 336 template<typename T>
 337 struct label
 338 {
 339   label(const char* str):str{str}{}
 340   operator const char*()const{return str;}
 341   const char* str;
 342 };
 343
 344 template<typename... T>
 345 struct element_sequence{};
 346
 347 template<
 348   typename... Element,
 349   typename Container
 350 >
 351 void container_fill(unsigned int n,element_sequence<Element...>,Container& c)
 352 {
 353   auto m=n/sizeof...(Element);
 354   for(unsigned int i=0;i!=m;++i){
 355     using seq=int[sizeof...(Element)];
 356     (void)seq{(c.insert(Element(i)),0)...};
 357   }
 358 }
 359
 360 struct insert_perf_functor
 361 {
 362   template<
 363     typename... Element,
 364     typename Container
 365   >
 366   std::size_t operator()(
 367     unsigned int n,element_sequence<Element...> elements,label<Container>)const
 368   {
 369     pause_timing();
 370     std::size_t res=0;
 371     {
 372       Container c;
 373       resume_timing();
 374       container_fill(n,elements,c);
 375       pause_timing();
 376       res=c.size();
 377     }
 378     resume_timing();
 379     return res;
 380   }
 381 };
 382
 383 template<
 384   typename... Element,
 385   typename Container
 386 >
 387 double insert_perf(
 388   unsigned int n,element_sequence<Element...> elements,label<Container> label)
 389 {
 390   return measure(n,std::bind(insert_perf_functor{},n,elements,label));
 391 }
 392
 393 template<
 394   typename... Element,
 395   typename... Container
 396 >
 397 void insert_perf(
 398   unsigned int n0,unsigned int n1,unsigned int dsav,
 399   element_sequence<Element...> elements,label<Container>... labels)
 400 {
 401   std::cout<<"insert:\n";
 402   print("n",labels...);
 403
 404   for(unsigned int s=0,n=n0;
 405       (n=(unsigned int)std::round(n0*std::pow(10.0,s/1000.0)))<=n1;
 406       s+=dsav){
 407     unsigned int m=(unsigned int)std::round(n/sizeof...(Element)),
 408                  nn=m*sizeof...(Element);
 409     print(nn,insert_perf(nn,elements,labels)...);
 410   }
 411 }
 412
 413 struct for_each_perf_functor
 414 {
 415   template<typename F,typename Container>
 416   auto operator()(F f,Container& c)const->decltype(f.res)
 417   {
 418     c.for_each(std::ref(f));
 419     return f.res;
 420   }
 421 };
 422
 423 template<
 424   typename... Element,
 425   typename F,
 426   typename Container
 427 >
 428 double for_each_perf(
 429   unsigned int n,
 430   element_sequence<Element...> elements,F f,label<Container>)
 431 {
 432   Container c;
 433   container_fill(n,elements,c);
 434   c.prepare_for_for_each();
 435   return measure(n,std::bind(for_each_perf_functor{},f,std::ref(c)));
 436 }
 437
 438 template<
 439   typename... Element,
 440   typename F,
 441   typename... Container
 442 >
 443 void for_each_perf(
 444   unsigned int n0,unsigned int n1,unsigned int dsav,
 445   element_sequence<Element...> elements,F f,label<Container>... labels)
 446 {
 447   std::cout<<"for_each:\n";
 448   print("n",labels...);
 449
 450   for(unsigned int s=0,n=n0;
 451       (n=(unsigned int)std::round(n0*std::pow(10.0,s/1000.0)))<=n1;
 452       s+=dsav){
 453     unsigned int m=(unsigned int)std::round(n/sizeof...(Element)),
 454                  nn=m*sizeof...(Element);
 455     print(nn,for_each_perf(nn,elements,f,labels)...);
 456   }
 457 }
 458
 459 //[perf_for_each_callable
 460 struct for_each_callable
 461 {
 462   for_each_callable():res{0}{}
 463
 464   template<typename T>
 465   void operator()(T& x){
 466     res+=x(2);
 467   }
 468
 469   int res;
 470 };
 471 //]
 472
 473 //[perf_for_each_incrementable
 474 struct for_each_incrementable
 475 {
 476   for_each_incrementable():res{0}{}
 477
 478   template<typename T>
 479   void operator()(T& x){
 480     ++x;
 481     ++res;
 482   }
 483
 484   int res;
 485 };
 486 //]
 487
 488 int main(int argc, char *argv[])
 489 {
 490   using test=std::pair<std::string,bool&>;
 491
 492   bool all=false,
 493        insert_base=false,
 494        for_each_base=false,
 495        insert_function=false,
 496        for_each_function=false,
 497        insert_any=false,
 498        for_each_any=false;
 499   std::array<test,7> tests={{
 500     {"all",all},
 501     {"insert_base",insert_base},
 502     {"for_each_base",for_each_base},
 503     {"insert_function",insert_function},
 504     {"for_each_function",for_each_function},
 505     {"insert_any",insert_any},
 506     {"for_each_any",for_each_any}
 507   }};
 508
 509   if(argc<2){
 510      std::cout<<"specify one or more tests to execute:\n";
 511      for(const auto& p:tests)std::cout<<"  "<<p.first<<"\n";
 512      return 1;
 513   }
 514
 515   for(int arg=1;arg<argc;++arg){
 516     auto it=std::find_if(tests.begin(),tests.end(),[&](test& t){
 517       return t.first==argv[arg];
 518     });
 519     if(it==tests.end()){
 520       std::cout<<"invalid test name\n";
 521       return 1;
 522     }
 523     it->second=true;
 524   }
 525
 526   unsigned int n0=100,n1=10000000,dsav=50; /* sav for savart */
 527
 528   {
 529     auto seq=  element_sequence<
 530                  derived1,derived1,derived2,derived2,derived3>{};
 531     auto f=    for_each_callable{};
 532     auto pv=   label<ptr_vector<base>>
 533                {"ptr_vector"};
 534     auto spv=  label<sorted_ptr_vector<base>>
 535                {"sorted ptr_vector"};
 536     auto shpv= label<shuffled_ptr_vector<base>>
 537                {"shuffled ptr_vector"};
 538     auto bc=   label<base_collection<base>>
 539                {"base_collection"};
 540     auto fbc=  label<poly_for_each_base_collection<base>>
 541                {"base_collection (poly::for_each)"};
 542     auto rfbc= label<
 543                  poly_for_each_base_collection<base,derived1,derived2,derived2>
 544                >
 545                {"base_collection (restituted poly::for_each)"};
 546
 547     if(all||insert_base)insert_perf(n0,n1,dsav,seq,pv,bc);
 548     if(all||for_each_base)for_each_perf(
 549       n0,n1,dsav,seq,f,pv,spv,shpv,bc,fbc,rfbc);
 550   }
 551   {
 552     using signature=int(int);
 553
 554     auto seq=  element_sequence<
 555                  concrete1,concrete1,concrete2,concrete2,concrete3>{};
 556     auto f =   for_each_callable{};
 557     auto fv=   label<func_vector<signature>>
 558                {"func_vector"};
 559     auto sfv=  label<sorted_func_vector<signature>>
 560                {"sorted func_vector"};
 561     auto shfv= label<shuffled_func_vector<signature>>
 562                {"shuffled func_vector"};
 563     auto fc=   label<func_collection<signature>>
 564                {"function_collection"};
 565     auto ffc=  label<poly_for_each_func_collection<signature>>
 566                {"function_collection (poly::for_each)"};
 567     auto rffc= label<poly_for_each_func_collection<
 568                  signature,concrete1,concrete2,concrete3>>
 569                {"function_collection (restituted poly::for_each)"};
 570
 571     if(all||insert_function)insert_perf(n0,n1,dsav,seq,fv,fc);
 572     if(all||for_each_function)for_each_perf(
 573       n0,n1,dsav,seq,f,fv,sfv,shfv,fc,ffc,rffc);
 574   }
 575   {
 576 //[perf_any_types
 577     using concept_=boost::mpl::vector<
 578       boost::type_erasure::copy_constructible<>,
 579       boost::type_erasure::relaxed,
 580       boost::type_erasure::typeid_<>,
 581       boost::type_erasure::incrementable<>
 582     >;
 583 //]
 584
 585     auto seq=  element_sequence<int,int,double,double,char>{};
 586     auto f=    for_each_incrementable{};
 587     auto av=   label<any_vector<concept_>>
 588                {"any_vector"};
 589     auto sav=  label<sorted_any_vector<concept_>>
 590                {"sorted any_vector"};
 591     auto shav= label<shuffled_any_vector<concept_>>
 592                {"shuffled any_vector"};
 593     auto ac=   label<any_collection<concept_>>
 594                {"any_collection"};
 595     auto fac=  label<poly_for_each_any_collection<concept_>>
 596                {"any_collection (poly::for_each)"};
 597     auto rfac= label<poly_for_each_any_collection<concept_,int,double,char>>
 598                {"any_collection (restituted poly::for_each)"};
 599
 600     if(all||insert_any)insert_perf(n0,n1,dsav,seq,av,ac);
 601     if(all||for_each_any)for_each_perf(
 602       n0,n1,dsav,seq,f,av,sav,shav,ac,fac,rfac);
 603   }
 604 }