poly_collection/example/perf.cpp

/* Copyright 2016-2024 Joaquin M Lopez Munoz.
 * Distributed under the Boost Software License, Version 1.0.
 * (See accompanying file LICENSE_1_0.txt or copy at
 * http://www.boost.org/LICENSE_1_0.txt)
 *
 * See http://www.boost.org/libs/poly_collection for library home page.
 */
  
/* Boost.PolyCollection performance tests */

#include <algorithm>
#include <array>
#include <chrono>
#include <cmath>
#include <numeric> 

std::chrono::high_resolution_clock::time_point measure_start,measure_pause;
    
template<typename F>
double measure(F f)
{
  using namespace std::chrono;
    
  static const int              num_trials=10;
  static const milliseconds     min_time_per_trial(200);
  std::array<double,num_trials> trials;
  volatile decltype(f())        res; /* to avoid optimizing f() away */
    
  for(int i=0;i<num_trials;++i){
    int                               runs=0;
    high_resolution_clock::time_point t2;
    
    measure_start=high_resolution_clock::now();
    do{
      res=f();
      ++runs;
      t2=high_resolution_clock::now();
    }while(t2-measure_start<min_time_per_trial);
    trials[i]=duration_cast<duration<double>>(t2-measure_start).count()/runs;
  }
  (void)res; /* var not used warn */
    
  std::sort(trials.begin(),trials.end());
  return std::accumulate(
    trials.begin()+2,trials.end()-2,0.0)/(trials.size()-4);
}

template<typename F>
double measure(unsigned int n,F f)
{
  double t=measure(f);
  return (t/n)*10E9;
}    

void pause_timing()
{
  measure_pause=std::chrono::high_resolution_clock::now();
}
    
void resume_timing()
{
  measure_start+=std::chrono::high_resolution_clock::now()-measure_pause;
}

#include <algorithm>
#include <array>
#include <boost/mp11/list.hpp>
#include <boost/variant2/variant.hpp>
#include <boost/poly_collection/algorithm.hpp>
#include <boost/poly_collection/any_collection.hpp>
#include <boost/poly_collection/base_collection.hpp>
#include <boost/poly_collection/function_collection.hpp>
#include <boost/poly_collection/variant_collection.hpp>
#include <boost/ptr_container/ptr_container.hpp>
#include <boost/type_erasure/any.hpp>
#include <boost/type_erasure/callable.hpp>
#include <boost/type_erasure/builtin.hpp>
#include <boost/type_erasure/operators.hpp>
#include <boost/type_erasure/typeid_of.hpp>
#include <functional>
#include <random>
#include <string>
#include <utility>
#include <vector>

//[perf_base_types
struct base
{
  virtual ~base()=default;
  virtual int operator()(int)const=0;
};

struct derived1 final:base
{
  derived1(int n):n{n}{}
  virtual int operator()(int)const{return n;}
  
  int n;
};

struct derived2 final:base
{
  derived2(int n):n{n}{}
  virtual int operator()(int x)const{return x*n;}
  
  int unused,n;
};

struct derived3 final:base
{
  derived3(int n):n{n}{}
  virtual int operator()(int x)const{return x*x*n;}
  
  int unused,n;
};
//]

//[perf_function_types
struct concrete1
{
  concrete1(int n):n{n}{}
  int operator()(int)const{return n;}
  
  int n;
};

struct concrete2
{
  concrete2(int n):n{n}{}
  int operator()(int x)const{return x*n;}
  
  int unused,n;
};

struct concrete3
{
  concrete3(int n):n{n}{}
  int operator()(int x)const{return x*x*n;}
  
  int unused,n;
};
//]

template<typename Base>
struct ptr_vector:boost::ptr_vector<Base>
{
public:
  template<typename T>
  BOOST_FORCEINLINE void insert(const T& x)
  {
    this->push_back(new T{x});
  }

  template<typename F>
  BOOST_FORCEINLINE void for_each(F f)
  {
    std::for_each(this->begin(),this->end(),f);
  }

  void prepare_for_for_each(){}
};

template<typename Base>
struct sorted_ptr_vector:ptr_vector<Base>
{
  void prepare_for_for_each()
  {
    std::sort(
      this->c_array(),this->c_array()+this->size(),
      [](Base* x,Base* y){return typeid(*x).before(typeid(*y));});
  }
};

template<typename Base>
struct shuffled_ptr_vector:ptr_vector<Base>
{
  void prepare_for_for_each()
  {
    std::shuffle(
     this->c_array(),this->c_array()+this->size(),std::mt19937(1));
  }
};

template<typename Base>
struct base_collection:boost::base_collection<Base>
{
  template<typename F>
  BOOST_FORCEINLINE void for_each(F f)
  {
    std::for_each(this->begin(),this->end(),f);
  }

  void prepare_for_for_each(){}
};

template<typename Base,typename... T>
struct poly_for_each_base_collection:base_collection<Base>
{
  template<typename F>
  BOOST_FORCEINLINE void for_each(F f)
  {
    boost::poly_collection::for_each<T...>(this->begin(),this->end(),f);
  }
};

template<typename Signature>
struct func_vector:std::vector<std::function<Signature>>
{
  template<typename T> BOOST_FORCEINLINE void insert(const T& x)
  {
    this->push_back(x);
  }

  template<typename F>
  BOOST_FORCEINLINE void for_each(F f)
  {
    std::for_each(this->begin(),this->end(),f);
  }

  void prepare_for_for_each(){}
};

template<typename Signature>
struct sorted_func_vector:func_vector<Signature>
{
  void prepare_for_for_each()
  {
    using value_type=typename sorted_func_vector::value_type;
    std::sort(
      this->begin(),this->end(),[](const value_type& x,const value_type& y){
        return x.target_type().before(y.target_type());
      });
  }
};

template<typename Signature>
struct shuffled_func_vector:func_vector<Signature>
{
  void prepare_for_for_each()
  {
    std::shuffle(this->begin(),this->end(),std::mt19937(1));
  }
};

template<typename Signature>
struct func_collection:boost::function_collection<Signature>
{
  template<typename F>
  BOOST_FORCEINLINE void for_each(F f)
  {
    std::for_each(this->begin(),this->end(),f);
  }

  void prepare_for_for_each(){}
};

template<typename Signature,typename... T>
struct poly_for_each_func_collection:func_collection<Signature>
{
  template<typename F>
  BOOST_FORCEINLINE void for_each(F f)
  {
    boost::poly_collection::for_each<T...>(this->begin(),this->end(),f);
  }
};

template<typename Concept>
struct any_vector:std::vector<boost::type_erasure::any<Concept>>
{
  template<typename T> void insert(const T& x)
  {
    this->push_back(x);
  }

  template<typename F>
  BOOST_FORCEINLINE void for_each(F f)
  {
    std::for_each(this->begin(),this->end(),f);
  }

  void prepare_for_for_each(){}
};

template<typename Concept>
struct sorted_any_vector:any_vector<Concept>
{
  void prepare_for_for_each()
  {
    using value_type=typename sorted_any_vector::value_type;
    std::sort(
      this->begin(),this->end(),[](const value_type& x,const value_type& y){
        return typeid_of(x).before(typeid_of(y));
      });
  }
};

template<typename Concept>
struct shuffled_any_vector:any_vector<Concept>
{
  void prepare_for_for_each()
  {
    std::shuffle(this->begin(),this->end(),std::mt19937(1));
  }
};

template<typename Concept>
struct any_collection:boost::any_collection<Concept>
{
  template<typename F>
  BOOST_FORCEINLINE void for_each(F f)
  {
    std::for_each(this->begin(),this->end(),f);
  }

  void prepare_for_for_each(){}
};

template<typename Concept,typename... T>
struct poly_for_each_any_collection:any_collection<Concept>
{
  template<typename F>
  BOOST_FORCEINLINE void for_each(F f)
  {
    boost::poly_collection::for_each<T...>(this->begin(),this->end(),f);
  }
};

template<typename L>
struct variant_vector:
  std::vector<boost::mp11::mp_rename<L,boost::variant2::variant>>
{
  template<typename T> void insert(const T& x)
  {
    this->push_back(x);
  }

  template<typename F>
  BOOST_FORCEINLINE void for_each(F f)
  {
    std::for_each(this->begin(),this->end(),f);
  }

  void prepare_for_for_each(){}
};

template<typename L>
struct sorted_variant_vector:variant_vector<L>
{
  void prepare_for_for_each()
  {
    using value_type=typename sorted_variant_vector::value_type;
    std::sort(
      this->begin(),this->end(),[](const value_type& x,const value_type& y){
        return x.index()<y.index();
      });
  }
};

template<typename L>
struct shuffled_variant_vector:variant_vector<L>
{
  void prepare_for_for_each()
  {
    std::shuffle(this->begin(),this->end(),std::mt19937(1));
  }
};

template<typename L>
struct variant_collection:boost::variant_collection<L>
{
  template<typename F>
  BOOST_FORCEINLINE void for_each(F f)
  {
    std::for_each(this->begin(),this->end(),f);
  }

  void prepare_for_for_each(){}
};

template<typename L,typename... T>
struct poly_for_each_variant_collection:variant_collection<L>
{
  template<typename F>
  BOOST_FORCEINLINE void for_each(F f)
  {
    boost::poly_collection::for_each<T...>(this->begin(),this->end(),f);
  }
};

#include <iostream>

template<typename... Printables>
void print(Printables... ps)
{
  const char* delim="";
  using seq=int[1+sizeof...(ps)];
  (void)seq{0,(std::cout<<delim<<ps,delim=";",0)...};
  std::cout<<"\n";
}

template<typename T>
struct label
{
  label(const char* str):str{str}{}
  operator const char*()const{return str;}
  const char* str;
};

template<typename... T>
struct element_sequence{};

template<
  typename ElementSequence,
  typename Container
>
struct container_fill_helper
{
  Container&   c;
  unsigned int i;

  template<typename J>
  void operator()(J)const
  {
    using T=boost::mp11::mp_at_c<ElementSequence,J::value>;
    c.insert(T(i));
  }
};

template<
  typename... Element,
  typename Container
>
void container_fill(unsigned int n,element_sequence<Element...>,Container& c)
{
  pause_timing();
  std::mt19937                    rng{1};
  std::uniform_int_distribution<> d(0,sizeof...(Element)-1);
  resume_timing();

  for(unsigned int i=0;i!=n;++i){
    boost::mp11::mp_with_index<sizeof...(Element)>(
      d(rng),
      container_fill_helper<element_sequence<Element...>,Container>{c,i});
  }
}

struct insert_perf_functor
{
  template<
    typename... Element,
    typename Container
  >
  std::size_t operator()(
    unsigned int n,element_sequence<Element...> elements,label<Container>)const
  {
    pause_timing();
    std::size_t res=0;
    {
      Container c;
      resume_timing();
      container_fill(n,elements,c);
      pause_timing();
      res=c.size();
    }
    resume_timing();
    return res;
  }
};

template<
  typename... Element,
  typename Container
>
double insert_perf(
  unsigned int n,element_sequence<Element...> elements,label<Container> label)
{
  return measure(n,std::bind(insert_perf_functor{},n,elements,label));
}

template<
  typename... Element,
  typename... Container
>
void insert_perf(
  unsigned int n0,unsigned int n1,unsigned int dsav,
  element_sequence<Element...> elements,label<Container>... labels)
{
  std::cout<<"insert:\n";
  print("n",labels...);
  
  for(unsigned int s=0,n=n0;
      (n=(unsigned int)std::round(n0*std::pow(10.0,s/1000.0)))<=n1;
      s+=dsav){
    print(n,insert_perf(n,elements,labels)...);
  }
}

struct for_each_perf_functor
{
  template<typename F,typename Container>
  auto operator()(F f,Container& c)const->decltype(f.res)
  {
    c.for_each(std::ref(f));
    return f.res;
  }
};

template<
  typename... Element,
  typename F,
  typename Container
>
double for_each_perf(
  unsigned int n,
  element_sequence<Element...> elements,F f,label<Container>)
{
  Container c;
  container_fill(n,elements,c);
  c.prepare_for_for_each();
  return measure(n,std::bind(for_each_perf_functor{},f,std::ref(c)));
}

template<
  typename... Element,
  typename F,
  typename... Container
>
void for_each_perf(
  unsigned int n0,unsigned int n1,unsigned int dsav,
  element_sequence<Element...> elements,F f,label<Container>... labels)
{
  std::cout<<"for_each:\n";
  print("n",labels...);
  
  for(unsigned int s=0,n=n0;
      (n=(unsigned int)std::round(n0*std::pow(10.0,s/1000.0)))<=n1;
      s+=dsav){
    print(n,for_each_perf(n,elements,f,labels)...);
  }
}

//[perf_for_each_callable
struct for_each_callable
{
  for_each_callable():res{0}{}

  template<typename T>
  void operator()(T& x){
    res+=x(2);
  }

  int res;
};
//]

//[perf_for_each_incrementable
struct for_each_incrementable
{
  for_each_incrementable():res{0}{}

  template<typename T>
  void operator()(T& x){
    ++x;
    ++res;
  }

  int res;
};
//]

//[perf_for_each_alternative
struct for_each_alternative
{
  for_each_alternative():res{0}{}

  template<template<typename...> class V,typename... Ts>
  void operator()(V<Ts...>& x){
    visit(*this,x);
  }

  template<typename T>
  void operator()(T& x){
    ++x;
    ++res;
  }

  int res;
};
//]

int main(int argc,char *argv[])
{
  using test=std::pair<std::string,bool&>;

  bool all=false,
       insert_base=false,
       for_each_base=false,
       insert_function=false,
       for_each_function=false,
       insert_any=false,
       for_each_any=false,
       insert_variant=false,
       for_each_variant=false;
  std::array<test,9> tests={{
    {"all",all},
    {"insert_base",insert_base},
    {"for_each_base",for_each_base},
    {"insert_function",insert_function},
    {"for_each_function",for_each_function},
    {"insert_any",insert_any},
    {"for_each_any",for_each_any},
    {"insert_variant",insert_variant},
    {"for_each_variant",for_each_variant}
  }};

  if(argc<2){
     std::cout<<"specify one or more tests to execute:\n";
     for(const auto& p:tests)std::cout<<"  "<<p.first<<"\n";
     return 1;
  }

  for(int arg=1;arg<argc;++arg){
    auto it=std::find_if(tests.begin(),tests.end(),[&](test& t){
      return t.first==argv[arg];
    });
    if(it==tests.end()){
      std::cout<<"invalid test name\n";
      return 1;
    }
    it->second=true;
  }

  unsigned int n0=100,n1=10000000,dsav=50; /* sav for savart */

  {
    auto seq=  element_sequence<derived1,derived2,derived3>{};
    auto f=    for_each_callable{};
    auto pv=   label<ptr_vector<base>>
               {"ptr_vector"};
    auto spv=  label<sorted_ptr_vector<base>>
               {"sorted ptr_vector"};
    auto shpv= label<shuffled_ptr_vector<base>>
               {"shuffled ptr_vector"};
    auto bc=   label<base_collection<base>>
               {"base_collection"};
    auto fbc=  label<poly_for_each_base_collection<base>>
               {"base_collection (poly::for_each)"};
    auto rfbc= label<
                 poly_for_each_base_collection<base,derived1,derived2,derived3>
               >
               {"base_collection (restituted poly::for_each)"};

    if(all||insert_base)insert_perf(n0,n1,dsav,seq,pv,bc);
    if(all||for_each_base)for_each_perf(
      n0,n1,dsav,seq,f,pv,spv,shpv,bc,fbc,rfbc);
  }
  {
    using signature=int(int);

    auto seq=  element_sequence<concrete1,concrete2,concrete3>{};
    auto f =   for_each_callable{};
    auto fv=   label<func_vector<signature>>
               {"func_vector"};
    auto sfv=  label<sorted_func_vector<signature>>
               {"sorted func_vector"};
    auto shfv= label<shuffled_func_vector<signature>>
               {"shuffled func_vector"};
    auto fc=   label<func_collection<signature>>
               {"function_collection"};
    auto ffc=  label<poly_for_each_func_collection<signature>>
               {"function_collection (poly::for_each)"};
    auto rffc= label<poly_for_each_func_collection<
                 signature,concrete1,concrete2,concrete3>>
               {"function_collection (restituted poly::for_each)"};

    if(all||insert_function)insert_perf(n0,n1,dsav,seq,fv,fc);
    if(all||for_each_function)for_each_perf(
      n0,n1,dsav,seq,f,fv,sfv,shfv,fc,ffc,rffc);
  }
  {
//[perf_any_types
    using concept_=boost::mpl::vector<
      boost::type_erasure::copy_constructible<>,
      boost::type_erasure::relaxed,
      boost::type_erasure::typeid_<>,
      boost::type_erasure::incrementable<>
    >;
//]

    auto seq=  element_sequence<int,double,char>{};
    auto f=    for_each_incrementable{};
    auto av=   label<any_vector<concept_>>
               {"any_vector"};
    auto sav=  label<sorted_any_vector<concept_>>
               {"sorted any_vector"};
    auto shav= label<shuffled_any_vector<concept_>>
               {"shuffled any_vector"};
    auto ac=   label<any_collection<concept_>>
               {"any_collection"};
    auto fac=  label<poly_for_each_any_collection<concept_>>
               {"any_collection (poly::for_each)"};
    auto rfac= label<poly_for_each_any_collection<concept_,int,double,char>>
               {"any_collection (restituted poly::for_each)"};

    if(all||insert_any)insert_perf(n0,n1,dsav,seq,av,ac);
    if(all||for_each_any)for_each_perf(
      n0,n1,dsav,seq,f,av,sav,shav,ac,fac,rfac);
  }
  {
//[perf_variant_types
    using type_list=boost::mp11::mp_list<int,double,char>;
//]

    auto seq=  element_sequence<int,double,char>{};
    auto f=    for_each_alternative{};
    auto vv=   label<variant_vector<type_list>>
               {"variant_vector"};
    auto svv=  label<sorted_variant_vector<type_list>>
               {"sorted variant_vector"};
    auto shvv= label<shuffled_variant_vector<type_list>>
               {"shuffled variant_vector"};
    auto vc=   label<variant_collection<type_list>>
               {"variant_collection"};
    auto fvc=  label<poly_for_each_variant_collection<type_list>>
               {"variant_collection (poly::for_each)"};
    auto rfvc= label<
                 poly_for_each_variant_collection<
                   type_list,boost::poly_collection::all_types>>
               {"variant_collection (restituted poly::for_each)"};

    if(all||insert_variant)insert_perf(n0,n1,dsav,seq,vv,vc);
    if(all||for_each_variant)for_each_perf(
      n0,n1,dsav,seq,f,vv,svv,shvv,vc,fvc,rfvc);
  }
}