///////////////////////////////////////////////////////////////////////////// // // (C) Copyright Ion Gaztanaga 2007-2009 // // 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>