libs/multi_index/perf/test_perf.cpp

/* Boost.MultiIndex performance test.
 *
 * Copyright 2003-2013 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/multi_index for library home page.
 */
#include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
#include <algorithm>
#include <assert.h>
#include <boost/multi_index_container.hpp>
#include <boost/multi_index/identity.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/sequenced_index.hpp>
#include <boost/next_prior.hpp>
#include <climits>
#include <ctime>
#include <iomanip>
#include <iostream>
#include <list>
#include <set>
#include <string>
#include <vector>
using namespace std;
using namespace boost::multi_index;
/* Measurement harness by Andrew Koenig, extracted from companion code to
 *   Stroustrup, B.: "Wrapping C++ Member Function Calls", The C++ Report,
 *     June 2000, Vol 12/No 6.
 * Original code retrievable at: http://www.research.att.com/~bs/wrap_code.cpp
 */
// How many clock units does it take to interrogate the clock?
static double clock_overhead()
{
    clock_t k = clock(), start, limit;
    // Wait for the clock to tick
    do start = clock();
    while (start == k);
    // interrogate the clock until it has advanced at least a second
    // (for reasonable accuracy)
    limit = start + CLOCKS_PER_SEC;
    unsigned long r = 0;
    while ((k = clock()) < limit)
        ++r;
    return double(k - start) / r;
}
// We'd like the odds to be factor:1 that the result is
// within percent% of the median
const int factor = 10;
const int percent = 20;
// Measure a function (object) factor*2 times,
// appending the measurements to the second argument
template<class F>
void measure_aux(F f, vector<double>& mv)
{
    static double ovhd = clock_overhead();
    // Ensure we don't reallocate in mid-measurement
    mv.reserve(mv.size() + factor*2);
    // Wait for the clock to tick
    clock_t k = clock();
    clock_t start;
    do start = clock();
    while (start == k);
    // Do 2*factor measurements
    for (int i = 2*factor; i; --i) {
        unsigned long count = 0, limit = 1, tcount = 0;
        // Original code used CLOCKS_PER_SEC/100
        const clock_t clocklimit = start + CLOCKS_PER_SEC/10;
        clock_t t;
        do {
            while (count < limit) {
                f();
                ++count;
            }
            limit *= 2;
            ++tcount;
        } while ((t = clock()) < clocklimit);
        // Wait for the clock to tick again;
        clock_t t2;
        do ++tcount;
        while ((t2 = clock()) == t);
        // Append the measurement to the vector
        mv.push_back(((t2 - start) - (tcount * ovhd)) / count);
        // Establish a new starting point
        start = t2;
    }
}
// Returns the number of clock units per iteration
// With odds of factor:1, the measurement is within percent% of
// the value returned, which is also the median of all measurements.
template<class F>
double measure(F f)
{
    vector<double> mv;
    int n = 0;                        // iteration counter
    do {
        ++n;
        // Try 2*factor measurements
        measure_aux(f, mv);
        assert(mv.size() == 2*n*factor);
        // Compute the median.  We know the size is even, so we cheat.
        sort(mv.begin(), mv.end());
        double median = (mv[n*factor] + mv[n*factor-1])/2;
        // If the extrema are within threshold of the median, we're done
        if (mv[n] > (median * (100-percent))/100 &&
            mv[mv.size() - n - 1] < (median * (100+percent))/100)
            return median;
    } while (mv.size() < factor * 200);
    // Give up!
    clog << "Help!\n\n";
    exit(1);
}
/* dereferencing compare predicate */
template <typename Iterator,typename Compare>
struct it_compare
{
  bool operator()(const Iterator& x,const Iterator& y)const{return comp(*x,*y);}
private:
  Compare comp;
};
/* list_wrapper and multiset_wrapper adapt std::lists and std::multisets
 * to make them conform to a set-like insert interface which test
 * routines do assume.
 */
template <typename List>
struct list_wrapper:List
{
  typedef typename List::value_type value_type;
  typedef typename List::iterator   iterator;
  pair<iterator,bool> insert(const value_type& v)
  {
    List::push_back(v);
    return pair<iterator,bool>(boost::prior(List::end()),true);
  }
};
template <typename Multiset>
struct multiset_wrapper:Multiset
{
  typedef typename Multiset::value_type value_type;
  typedef typename Multiset::iterator   iterator;
  pair<iterator,bool> insert(const value_type& v)
  {
    return pair<iterator,bool>(Multiset::insert(v),true);
  }
};
/* space comsumption of manual simulations is determined by checking
 * the node sizes of the containers involved. This cannot be done in a
 * portable manner, so node_size has to be written on a per stdlibrary
 * basis. Add your own versions if necessary.
 */
#if defined(BOOST_DINKUMWARE_STDLIB)
template<typename Container>
size_t node_size(const Container&)
{
  return sizeof(*Container().begin()._Mynode());
}
#elif defined(__GLIBCPP__) || defined(__GLIBCXX__)
template<typename Container>
size_t node_size(const Container&)
{
  typedef typename Container::iterator::_Link_type node_ptr;
  node_ptr p=0;
  return sizeof(*p);
}
template<typename Value,typename Allocator>
size_t node_size(const list<Value,Allocator>&)
{
  return sizeof(typename list<Value,Allocator>::iterator::_Node);
}
template<typename List>
size_t node_size(const list_wrapper<List>&)
{
  return sizeof(typename List::iterator::_Node);
}
#else
/* default version returns 0 by convention */
template<typename Container>
size_t node_size(const Container&)
{
  return 0;
}
#endif
/* mono_container runs the tested routine on multi_index and manual
 * simulations comprised of one standard container.
 * bi_container and tri_container run the equivalent routine for manual
 * compositions of two and three standard containers, respectively.
 */
template <typename Container>
struct mono_container
{
  mono_container(int n_):n(n_){}
  void operator()()
  {
    typedef typename Container::iterator iterator;
    Container c;
    for(int i=0;i<n;++i)c.insert(i);
    for(iterator it=c.begin();it!=c.end();)c.erase(it++);
  }
  static size_t multi_index_node_size()
  {
    return sizeof(*Container().begin().get_node());
  }
  static size_t node_size()
  {
    return ::node_size(Container());
  }
private:
  int n;
};
template <typename Container1,typename Container2>
struct bi_container
{
  bi_container(int n_):n(n_){}
  void operator()()
  {
    typedef typename Container1::iterator iterator1;
    typedef typename Container2::iterator iterator2;
    Container1 c1;
    Container2 c2;
    for(int i=0;i<n;++i){
      iterator1 it1=c1.insert(i).first;
      c2.insert(it1);
    }
    for(iterator2 it2=c2.begin();it2!=c2.end();)
    {
      c1.erase(*it2);
      c2.erase(it2++);
    }
  }
  static size_t node_size()
  {
    return ::node_size(Container1())+::node_size(Container2());
  }
private:
  int n;
};
template <typename Container1,typename Container2,typename Container3>
struct tri_container
{
  tri_container(int n_):n(n_){}
  void operator()()
  {
    typedef typename Container1::iterator iterator1;
    typedef typename Container2::iterator iterator2;
    typedef typename Container3::iterator iterator3;
    Container1 c1;
    Container2 c2;
    Container3 c3;
    for(int i=0;i<n;++i){
      iterator1 it1=c1.insert(i).first;
      iterator2 it2=c2.insert(it1).first;
      c3.insert(it2);
    }
    for(iterator3 it3=c3.begin();it3!=c3.end();)
    {
      c1.erase(**it3);
      c2.erase(*it3);
      c3.erase(it3++);
    }
  }
  static size_t node_size()
  {
    return ::node_size(Container1())+
           ::node_size(Container2())+::node_size(Container3());
  }
private:
  int n;
};
/* measure and compare two routines for several numbers of elements
 * and also estimates relative memory consumption.
 */
template <typename IndexedTest,typename ManualTest>
void run_tests(const char* title)
{
  cout<<fixed<<setprecision(2);
  cout<<title<<endl;
  int n=1000;
  for(int i=0;i<3;++i){
    double indexed_t=measure(IndexedTest(n));
    double manual_t=measure(ManualTest(n));
    cout<<"  10^"<<i+3<<" elmts: "
        <<setw(6)<<100.0*indexed_t/manual_t<<"% "
        <<"("
          <<setw(6)<<1000.0*indexed_t/CLOCKS_PER_SEC<<" ms / "
          <<setw(6)<<1000.0*manual_t/CLOCKS_PER_SEC<<" ms)"
        <<endl;
    n*=10;
  }
  size_t indexed_t_node_size=IndexedTest::multi_index_node_size();
  size_t manual_t_node_size=ManualTest::node_size();
  if(manual_t_node_size){
    cout<<"  space gain: "
        <<setw(6)<<100.0*indexed_t_node_size/manual_t_node_size<<"%"<<endl;
  }
}
/* compare_structures accept a multi_index_container instantiation and
 * several standard containers, builds a manual simulation out of the
 * latter and run the tests.
 */
template <typename IndexedType,typename ManualType>
void compare_structures(const char* title)
{
  run_tests<
    mono_container<IndexedType>,
    mono_container<ManualType>
  >(title);
}
template <typename IndexedType,typename ManualType1,typename ManualType2>
void compare_structures2(const char* title)
{
  run_tests<
    mono_container<IndexedType>,
    bi_container<ManualType1,ManualType2>
  >(title);
}
template <
  typename IndexedType,
  typename ManualType1,typename ManualType2,typename ManualType3
>
void compare_structures3(const char* title)
{
  run_tests<
    mono_container<IndexedType>,
    tri_container<ManualType1,ManualType2,ManualType3>
  >(title);
}
int main()
{
  /* some stdlibs provide the discussed but finally rejected std::identity */
  using boost::multi_index::identity; 
  {
    /* 1 ordered index */
    typedef multi_index_container<int> indexed_t;
    typedef set<int>                   manual_t;
    compare_structures<indexed_t,manual_t>(
      "1 ordered index");
  }
  {
    /* 1 sequenced index */
    typedef list_wrapper<
      multi_index_container<
        int,
        indexed_by<sequenced<> > 
      >
    >                                  indexed_t;
    typedef list_wrapper<list<int> >   manual_t;
    compare_structures<indexed_t,manual_t>(
      "1 sequenced index");
  }
  {
    /* 2 ordered indices */
    typedef multi_index_container<
      int,
      indexed_by<
        ordered_unique<identity<int> >,
        ordered_non_unique<identity<int> >
      >
    >                                  indexed_t;
    typedef set<int>                   manual_t1;
    typedef multiset<
      manual_t1::iterator,
      it_compare<
        manual_t1::iterator,
        manual_t1::key_compare
      >
    >                                  manual_t2;
    compare_structures2<indexed_t,manual_t1,manual_t2>(
      "2 ordered indices");
  }
  {
    /* 1 ordered index + 1 sequenced index */
    typedef multi_index_container<
      int,
      indexed_by<
        boost::multi_index::ordered_unique<identity<int> >,
        sequenced<>
      >
    >                                  indexed_t;
    typedef list_wrapper<
      list<int>
    >                                  manual_t1;
    typedef multiset<
      manual_t1::iterator,
      it_compare<
        manual_t1::iterator,
        std::less<int>
      >
    >                                  manual_t2;
    compare_structures2<indexed_t,manual_t1,manual_t2>(
      "1 ordered index + 1 sequenced index");
  }
  {
    /* 3 ordered indices */
    typedef multi_index_container<
      int,
      indexed_by<
        ordered_unique<identity<int> >,
        ordered_non_unique<identity<int> >,
        ordered_non_unique<identity<int> >
      >
    >                                  indexed_t;
    typedef set<int>                   manual_t1;
    typedef multiset_wrapper<
      multiset<
        manual_t1::iterator,
        it_compare<
          manual_t1::iterator,
          manual_t1::key_compare
        >
      >
    >                                  manual_t2;
    typedef multiset<
      manual_t2::iterator,
      it_compare<
        manual_t2::iterator,
        manual_t2::key_compare
      >
    >                                  manual_t3;
    compare_structures3<indexed_t,manual_t1,manual_t2,manual_t3>(
      "3 ordered indices");
  }
  {
    /* 2 ordered indices + 1 sequenced index */
    typedef multi_index_container<
      int,
      indexed_by<
        ordered_unique<identity<int> >,
        ordered_non_unique<identity<int> >,
        sequenced<>
      >
    >                                  indexed_t;
    typedef list_wrapper<
      list<int>
    >                                  manual_t1;
    typedef multiset_wrapper<
      multiset<
        manual_t1::iterator,
        it_compare<
          manual_t1::iterator,
          std::less<int>
        >
      >
    >                                  manual_t2;
    typedef multiset<
      manual_t2::iterator,
      it_compare<
        manual_t2::iterator,
        manual_t2::key_compare
      >
    >                                  manual_t3;
    compare_structures3<indexed_t,manual_t1,manual_t2,manual_t3>(
      "2 ordered indices + 1 sequenced index");
  }
  return 0;
}