libs/multi_index/perf/test_perf.cpp
/* Boost.MultiIndex performance test. * * Copyright 2003-2008 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 BOOST_APPEND_EXPLICIT_TEMPLATE_TYPE(IndexedTest) BOOST_APPEND_EXPLICIT_TEMPLATE_TYPE(ManualTest)) { 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 BOOST_APPEND_EXPLICIT_TEMPLATE_TYPE(IndexedType) BOOST_APPEND_EXPLICIT_TEMPLATE_TYPE(ManualType)) { run_tests< mono_container<IndexedType>, mono_container<ManualType> >(title); } template <typename IndexedType,typename ManualType1,typename ManualType2> void compare_structures2( const char* title BOOST_APPEND_EXPLICIT_TEMPLATE_TYPE(IndexedType) BOOST_APPEND_EXPLICIT_TEMPLATE_TYPE(ManualType1) BOOST_APPEND_EXPLICIT_TEMPLATE_TYPE(ManualType2)) { 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 BOOST_APPEND_EXPLICIT_TEMPLATE_TYPE(IndexedType) BOOST_APPEND_EXPLICIT_TEMPLATE_TYPE(ManualType1) BOOST_APPEND_EXPLICIT_TEMPLATE_TYPE(ManualType2) BOOST_APPEND_EXPLICIT_TEMPLATE_TYPE(ManualType3)) { run_tests< mono_container<IndexedType>, tri_container<ManualType1,ManualType2,ManualType3> >(title); } int main() { { /* 1 ordered index */ typedef multi_index_container<int> indexed_t; typedef set<int> manual_t; indexed_t dummy; /* MSVC++ 6.0 chokes if indexed_t is not instantiated */ 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; indexed_t dummy; /* MSVC++ 6.0 chokes if indexed_t is not instantiated */ 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; indexed_t dummy; /* MSVC++ 6.0 chokes if indexed_t is not instantiated */ 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; indexed_t dummy; /* MSVC++ 6.0 chokes if indexed_t is not instantiated */ 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; indexed_t dummy; /* MSVC++ 6.0 chokes if indexed_t is not instantiated */ 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; indexed_t dummy; /* MSVC++ 6.0 chokes if indexed_t is not instantiated */ compare_structures3<indexed_t,manual_t1,manual_t2,manual_t3>( "2 ordered indices + 1 sequenced index"); } return 0; }