| /* 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; |
| } |