123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550 |
- /////////////////////////////////////////////////////////////////////////////
- //
- // (C) Copyright Ion Gaztanaga 2007-2013
- //
- // 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 = 4;
- 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>
|