546 lines
13 KiB
C++
546 lines
13 KiB
C++
/* 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;
|
|
}
|