libs/intrusive/perf/perf_list.cpp
/////////////////////////////////////////////////////////////////////////////
//
// (C) Copyright Ion Gaztanaga 2007-2012
//
// 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/intrusive for documentation.
//
/////////////////////////////////////////////////////////////////////////////
//Includes for tests
#include <boost/intrusive/detail/config_begin.hpp>
#include <boost/config.hpp>
#include <list>
#include <functional>
#include <iostream>
#include <boost/intrusive/list.hpp>
#include <boost/date_time/posix_time/posix_time.hpp>
using namespace boost::posix_time;
//[perf_list_value_type
//Iteration and element count defines
const int NumIter = 100;
const int NumElements = 50000;
using namespace boost::intrusive;
template<bool BigSize> struct filler { int dummy[10]; };
template <> struct filler<false> {};
template<bool BigSize> //The object for non-intrusive containers
struct test_class : private filler<BigSize>
{
int i_;
test_class() {}
test_class(int i) : i_(i) {}
friend bool operator <(const test_class &l, const test_class &r) { return l.i_ < r.i_; }
friend bool operator >(const test_class &l, const test_class &r) { return l.i_ > r.i_; }
};
template <bool BigSize, link_mode_type LinkMode>
struct itest_class //The object for intrusive containers
: public list_base_hook<link_mode<LinkMode> >, public test_class<BigSize>
{
itest_class() {}
itest_class(int i) : test_class<BigSize>(i) {}
};
template<class FuncObj> //Adapts functors taking values to functors taking pointers
struct func_ptr_adaptor : public FuncObj
{
typedef typename FuncObj::first_argument_type* first_argument_type;
typedef typename FuncObj::second_argument_type* second_argument_type;
typedef typename FuncObj::result_type result_type;
result_type operator()(first_argument_type a, second_argument_type b) const
{ return FuncObj::operator()(*a, *b); }
};
//]
template <bool BigSize, link_mode_type LinkMode>
struct get_ilist //Helps to define an intrusive list from a policy
{
typedef list<itest_class<BigSize, LinkMode>, constant_time_size<false> > type;
};
template <bool BigSize> //Helps to define an std list
struct get_list { typedef std::list<test_class<BigSize> > type; };
template <bool BigSize> //Helps to define an std pointer list
struct get_ptrlist { typedef std::list<test_class<BigSize>*> type; };
////////////////////////////////////////////////////////////////////////
//
// PUSH_BACK
//
////////////////////////////////////////////////////////////////////////
template <bool BigSize, link_mode_type LinkMode>
void test_intrusive_list_push_back()
{
typedef typename get_ilist<BigSize, LinkMode>::type ilist;
ptime tini = microsec_clock::universal_time();
for(int i = 0; i < NumIter; ++i){
//First create the elements and insert them in the intrusive list
//[perf_list_push_back_intrusive
std::vector<typename ilist::value_type> objects(NumElements);
ilist l;
for(int i = 0; i < NumElements; ++i)
l.push_back(objects[i]);
//Elements are unlinked in ilist's destructor
//Elements are destroyed in vector's destructor
//]
}
ptime tend = microsec_clock::universal_time();
std::cout << "link_mode: " << LinkMode << ", usecs/iteration: "
<< (tend-tini).total_microseconds()/NumIter << std::endl;
}
template <bool BigSize>
void test_std_list_push_back()
{
typedef typename get_list<BigSize>::type stdlist;
ptime tini = microsec_clock::universal_time();
for(int i = 0; i < NumIter; ++i){
//Now create the std list and insert
//[perf_list_push_back_stdlist
stdlist l;
for(int i = 0; i < NumElements; ++i)
l.push_back(typename stdlist::value_type(i));
//Elements unlinked and destroyed in stdlist's destructor
//]
}
ptime tend = microsec_clock::universal_time();
std::cout << "std::list usecs/iteration: "
<< (tend-tini).total_microseconds()/NumIter << std::endl;
}
template <bool BigSize>
void test_compact_std_ptrlist_push_back()
{
typedef typename get_list<BigSize>::type stdlist;
typedef typename get_ptrlist<BigSize>::type stdptrlist;
//Now measure insertion time, including element creation
ptime tini = microsec_clock::universal_time();
for(int i = 0; i < NumIter; ++i){
//Create elements and insert their pointer in the list
//[perf_list_push_back_stdptrlist
std::vector<typename stdlist::value_type> objects(NumElements);
stdptrlist l;
for(int i = 0; i < NumElements; ++i)
l.push_back(&objects[i]);
//Pointers to elements unlinked and destroyed in stdptrlist's destructor
//Elements destroyed in vector's destructor
//]
}
ptime tend = microsec_clock::universal_time();
std::cout << "compact std::list usecs/iteration: "
<< (tend-tini).total_microseconds()/NumIter << std::endl;
}
template <bool BigSize>
void test_disperse_std_ptrlist_push_back()
{
typedef typename get_list<BigSize>::type stdlist;
typedef typename get_ptrlist<BigSize>::type stdptrlist;
//Now measure insertion time, including element creation
ptime tini = microsec_clock::universal_time();
for(int i = 0; i < NumIter; ++i){
//Create elements and insert their pointer in the list
//[perf_list_push_back_disperse_stdptrlist
stdlist objects; stdptrlist l;
for(int i = 0; i < NumElements; ++i){
objects.push_back(typename stdlist::value_type(i));
l.push_back(&objects.back());
}
//Pointers to elements unlinked and destroyed in stdptrlist's destructor
//Elements unlinked and destroyed in stdlist's destructor
//]
}
ptime tend = microsec_clock::universal_time();
std::cout << "disperse std::list usecs/iteration: "
<< (tend-tini).total_microseconds()/NumIter << std::endl;
}
////////////////////////////////////////////////////////////////////////
//
// REVERSE
//
////////////////////////////////////////////////////////////////////////
//[perf_list_reverse
template <bool BigSize, link_mode_type LinkMode>
void test_intrusive_list_reverse()
{
typedef typename get_ilist<BigSize, LinkMode>::type ilist;
//First create the elements
std::vector<typename ilist::value_type> objects(NumElements);
//Now create the intrusive list and insert data
ilist l(objects.begin(), objects.end());
//Now measure sorting time
ptime tini = microsec_clock::universal_time();
for(int i = 0; i < NumIter; ++i){
l.reverse();
}
ptime tend = microsec_clock::universal_time();
std::cout << "link_mode: " << LinkMode << ", usecs/iteration: "
<< (tend-tini).total_microseconds()/NumIter << std::endl;
}
template <bool BigSize>
void test_std_list_reverse()
{
typedef typename get_list<BigSize>::type stdlist;
//Create the list and insert values
stdlist l;
for(int i = 0; i < NumElements; ++i)
l.push_back(typename stdlist::value_type());
//Now measure sorting time
ptime tini = microsec_clock::universal_time();
for(int i = 0; i < NumIter; ++i){
l.reverse();
}
ptime tend = microsec_clock::universal_time();
std::cout << "std::list usecs/iteration: "
<< (tend-tini).total_microseconds()/NumIter << std::endl;
}
template <bool BigSize>
void test_compact_std_ptrlist_reverse()
{
typedef typename get_list<BigSize>::type stdlist;
typedef typename get_ptrlist<BigSize>::type stdptrlist;
//First create the elements
std::vector<typename stdlist::value_type> objects(NumElements);
//Now create the std list and insert
stdptrlist l;
for(int i = 0; i < NumElements; ++i)
l.push_back(&objects[i]);
//Now measure sorting time
ptime tini = microsec_clock::universal_time();
for(int i = 0; i < NumIter; ++i){
l.reverse();
}
ptime tend = microsec_clock::universal_time();
std::cout << "compact std::list usecs/iteration: "
<< (tend-tini).total_microseconds()/NumIter << std::endl;
}
template <bool BigSize>
void test_disperse_std_ptrlist_reverse()
{
typedef typename get_list<BigSize>::type stdlist;
typedef typename get_ptrlist<BigSize>::type stdptrlist;
//First create the elements
std::list<typename stdlist::value_type> objects;
//Now create the std list and insert
stdptrlist l;
for(int i = 0; i < NumElements; ++i){
objects.push_back(typename stdlist::value_type());
l.push_back(&objects.back());
}
//Now measure sorting time
ptime tini = microsec_clock::universal_time();
for(int i = 0; i < NumIter; ++i){
l.reverse();
}
ptime tend = microsec_clock::universal_time();
std::cout << "disperse std::list usecs/iteration: "
<< (tend-tini).total_microseconds()/NumIter << std::endl;
}
//]
////////////////////////////////////////////////////////////////////////
//
// SORT
//
////////////////////////////////////////////////////////////////////////
//[perf_list_sort
template <bool BigSize, link_mode_type LinkMode>
void test_intrusive_list_sort()
{
typedef typename get_ilist<BigSize, LinkMode>::type ilist;
//First create the elements
std::vector<typename ilist::value_type> objects(NumElements);
for(int i = 0; i < NumElements; ++i)
objects[i].i_ = i;
//Now create the intrusive list and insert data
ilist l(objects.begin(), objects.end());
//Now measure sorting time
ptime tini = microsec_clock::universal_time();
for(int i = 0; i < NumIter; ++i){
if(!(i % 2)){
l.sort(std::greater<typename ilist::value_type>());
}
else{
l.sort(std::less<typename ilist::value_type>());
}
}
ptime tend = microsec_clock::universal_time();
std::cout << "link_mode: " << LinkMode << ", usecs/iteration: "
<< (tend-tini).total_microseconds()/NumIter << std::endl;
}
template <bool BigSize>
void test_std_list_sort()
{
typedef typename get_list<BigSize>::type stdlist;
//Create the list and insert values
stdlist l;
for(int i = 0; i < NumElements; ++i)
l.push_back(typename stdlist::value_type(i));
//Now measure sorting time
ptime tini = microsec_clock::universal_time();
for(int i = 0; i < NumIter; ++i){
if(!(i % 2)){
l.sort(std::greater<typename stdlist::value_type>());
}
else{
l.sort(std::less<typename stdlist::value_type>());
}
}
ptime tend = microsec_clock::universal_time();
std::cout << "std::list usecs/iteration: "
<< (tend-tini).total_microseconds()/NumIter << std::endl;
}
template <bool BigSize>
void test_compact_std_ptrlist_sort()
{
typedef typename get_list<BigSize>::type stdlist;
typedef typename get_ptrlist<BigSize>::type stdptrlist;
//First create the elements
std::vector<typename stdlist::value_type> objects(NumElements);
for(int i = 0; i < NumElements; ++i)
objects[i].i_ = i;
//Now create the std list and insert
stdptrlist l;
for(int i = 0; i < NumElements; ++i)
l.push_back(&objects[i]);
//Now measure sorting time
ptime tini = microsec_clock::universal_time();
for(int i = 0; i < NumIter; ++i){
if(!(i % 2)){
l.sort(func_ptr_adaptor<std::greater<typename stdlist::value_type> >());
}
else{
l.sort(func_ptr_adaptor<std::less<typename stdlist::value_type> >());
}
}
ptime tend = microsec_clock::universal_time();
std::cout << "compact std::list usecs/iteration: "
<< (tend-tini).total_microseconds()/NumIter << std::endl;
}
template <bool BigSize>
void test_disperse_std_ptrlist_sort()
{
typedef typename get_list<BigSize>::type stdlist;
typedef typename get_ptrlist<BigSize>::type stdptrlist;
//First create the elements and the list
std::list<typename stdlist::value_type> objects;
stdptrlist l;
for(int i = 0; i < NumElements; ++i){
objects.push_back(typename stdlist::value_type(i));
l.push_back(&objects.back());
}
//Now measure sorting time
ptime tini = microsec_clock::universal_time();
for(int i = 0; i < NumIter; ++i){
if(!(i % 2)){
l.sort(func_ptr_adaptor<std::greater<typename stdlist::value_type> >());
}
else{
l.sort(func_ptr_adaptor<std::less<typename stdlist::value_type> >());
}
}
ptime tend = microsec_clock::universal_time();
std::cout << "disperse std::list usecs/iteration: "
<< (tend-tini).total_microseconds()/NumIter << std::endl;
}
//]
////////////////////////////////////////////////////////////////////////
//
// WRITE ACCESS
//
////////////////////////////////////////////////////////////////////////
//[perf_list_write_access
template <bool BigSize, link_mode_type LinkMode>
void test_intrusive_list_write_access()
{
typedef typename get_ilist<BigSize, LinkMode>::type ilist;
//First create the elements
std::vector<typename ilist::value_type> objects(NumElements);
for(int i = 0; i < NumElements; ++i){
objects[i].i_ = i;
}
//Now create the intrusive list and insert data
ilist l(objects.begin(), objects.end());
//Now measure access time to the value type
ptime tini = microsec_clock::universal_time();
for(int i = 0; i < NumIter; ++i){
typename ilist::iterator it(l.begin()), end(l.end());
for(; it != end; ++it){
++(it->i_);
}
}
ptime tend = microsec_clock::universal_time();
std::cout << "link_mode: " << LinkMode << ", usecs/iteration: "
<< (tend-tini).total_microseconds()/NumIter << std::endl;
}
template <bool BigSize>
void test_std_list_write_access()
{
typedef typename get_list<BigSize>::type stdlist;
//Create the list and insert values
stdlist l;
for(int i = 0; i < NumElements; ++i)
l.push_back(typename stdlist::value_type(i));
//Now measure access time to the value type
ptime tini = microsec_clock::universal_time();
for(int i = 0; i < NumIter; ++i){
typename stdlist::iterator it(l.begin()), end(l.end());
for(; it != end; ++it){
++(it->i_);
}
}
ptime tend = microsec_clock::universal_time();
std::cout << "std::list usecs/iteration: "
<< (tend-tini).total_microseconds()/NumIter << std::endl;
}
template <bool BigSize>
void test_compact_std_ptrlist_write_access()
{
typedef typename get_list<BigSize>::type stdlist;
typedef typename get_ptrlist<BigSize>::type stdptrlist;
//First create the elements
std::vector<typename stdlist::value_type> objects(NumElements);
for(int i = 0; i < NumElements; ++i){
objects[i].i_ = i;
}
//Now create the std list and insert
stdptrlist l;
for(int i = 0; i < NumElements; ++i)
l.push_back(&objects[i]);
//Now measure access time to the value type
ptime tini = microsec_clock::universal_time();
for(int i = 0; i < NumIter; ++i){
typename stdptrlist::iterator it(l.begin()), end(l.end());
for(; it != end; ++it){
++((*it)->i_);
}
}
ptime tend = microsec_clock::universal_time();
std::cout << "compact std::list usecs/iteration: "
<< (tend-tini).total_microseconds()/NumIter << std::endl;
}
template <bool BigSize>
void test_disperse_std_ptrlist_write_access()
{
typedef typename get_list<BigSize>::type stdlist;
typedef typename get_ptrlist<BigSize>::type stdptrlist;
//First create the elements
std::list<typename stdlist::value_type> objects;
//Now create the std list and insert
stdptrlist l;
for(int i = 0; i < NumElements; ++i){
objects.push_back(typename stdlist::value_type(i));
l.push_back(&objects.back());
}
//Now measure access time to the value type
ptime tini = microsec_clock::universal_time();
for(int i = 0; i < NumIter; ++i){
typename stdptrlist::iterator it(l.begin()), end(l.end());
for(; it != end; ++it){
++((*it)->i_);
}
}
ptime tend = microsec_clock::universal_time();
std::cout << "disperse std::list usecs/iteration: "
<< (tend-tini).total_microseconds()/NumIter << std::endl;
}
//]
////////////////////////////////////////////////////////////////////////
//
// ALL TESTS
//
////////////////////////////////////////////////////////////////////////
template<bool BigSize>
void do_all_tests()
{
std::cout << "\n\nTesting push back() with BigSize:" << BigSize << std::endl;
test_intrusive_list_push_back<BigSize, normal_link>();
test_intrusive_list_push_back<BigSize, safe_link>();
test_intrusive_list_push_back<BigSize, auto_unlink>();
test_std_list_push_back<BigSize> ();
test_compact_std_ptrlist_push_back<BigSize>();
test_disperse_std_ptrlist_push_back<BigSize>();
//reverse
std::cout << "\n\nTesting reverse() with BigSize:" << BigSize << std::endl;
test_intrusive_list_reverse<BigSize, normal_link>();
test_intrusive_list_reverse<BigSize, safe_link>();
test_intrusive_list_reverse<BigSize, auto_unlink>();
test_std_list_reverse<BigSize>();
test_compact_std_ptrlist_reverse<BigSize>();
test_disperse_std_ptrlist_reverse<BigSize>();
//sort
std::cout << "\n\nTesting sort() with BigSize:" << BigSize << std::endl;
test_intrusive_list_sort<BigSize, normal_link>();
test_intrusive_list_sort<BigSize, safe_link>();
test_intrusive_list_sort<BigSize, auto_unlink>();
test_std_list_sort<BigSize>();
test_compact_std_ptrlist_sort<BigSize>();
test_disperse_std_ptrlist_sort<BigSize>();
//write_access
std::cout << "\n\nTesting write_access() with BigSize:" << BigSize << std::endl;
test_intrusive_list_write_access<BigSize, normal_link>();
test_intrusive_list_write_access<BigSize, safe_link>();
test_intrusive_list_write_access<BigSize, auto_unlink>();
test_std_list_write_access<BigSize>();
test_compact_std_ptrlist_write_access<BigSize>();
test_disperse_std_ptrlist_write_access<BigSize>();
}
int main()
{
//First pass the tests with a small size class
do_all_tests<false>();
//Now pass the tests with a big size class
do_all_tests<true>();
return 0;
}
#include <boost/intrusive/detail/config_end.hpp>