summaryrefslogtreecommitdiffstats
path: root/src/boost/libs/intrusive/perf
diff options
context:
space:
mode:
Diffstat (limited to 'src/boost/libs/intrusive/perf')
-rw-r--r--src/boost/libs/intrusive/perf/Jamfile.v234
-rw-r--r--src/boost/libs/intrusive/perf/perf_list.cpp550
-rw-r--r--src/boost/libs/intrusive/perf/tree_perf_test.cpp214
3 files changed, 798 insertions, 0 deletions
diff --git a/src/boost/libs/intrusive/perf/Jamfile.v2 b/src/boost/libs/intrusive/perf/Jamfile.v2
new file mode 100644
index 00000000..8c35ee8b
--- /dev/null
+++ b/src/boost/libs/intrusive/perf/Jamfile.v2
@@ -0,0 +1,34 @@
+# Boost Intrusive Library Performance test Jamfile
+
+# (C) Copyright Ion Gaztanaga 2006-2013.
+# Use, modification and distribution are subject to 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)
+
+# Adapted from John Maddock's TR1 Jamfile.v2
+# Copyright John Maddock 2005.
+# Use, modification and distribution are subject to 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)
+
+# this rule enumerates through all the sources and invokes
+# the run rule for each source, the result is a list of all
+# the run rules, which we can pass on to the test_suite rule:
+
+rule test_all
+{
+ local all_rules = ;
+
+ for local fileb in [ glob *.cpp ]
+ {
+ all_rules += [ run $(fileb)
+ : # additional args
+ : # test-files
+ : # requirements
+ ] ;
+ }
+
+ return $(all_rules) ;
+}
+
+test-suite intrusive_perf : [ test_all r ] ;
diff --git a/src/boost/libs/intrusive/perf/perf_list.cpp b/src/boost/libs/intrusive/perf/perf_list.cpp
new file mode 100644
index 00000000..112507f7
--- /dev/null
+++ b/src/boost/libs/intrusive/perf/perf_list.cpp
@@ -0,0 +1,550 @@
+/////////////////////////////////////////////////////////////////////////////
+//
+// (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>
diff --git a/src/boost/libs/intrusive/perf/tree_perf_test.cpp b/src/boost/libs/intrusive/perf/tree_perf_test.cpp
new file mode 100644
index 00000000..5215ea08
--- /dev/null
+++ b/src/boost/libs/intrusive/perf/tree_perf_test.cpp
@@ -0,0 +1,214 @@
+/////////////////////////////////////////////////////////////////////////////
+//
+// (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 <iostream>
+#include <vector>
+#include <boost/intrusive/set.hpp>
+#include <boost/intrusive/sg_set.hpp>
+#include <boost/intrusive/avl_set.hpp>
+#include <boost/date_time/posix_time/posix_time.hpp>
+#include <cstdlib>
+
+using namespace boost::posix_time;
+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>
+{
+ std::size_t 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, class HookType>
+struct itest_class //The object for intrusive containers
+ : public HookType, public test_class<BigSize>
+{
+};
+
+#ifdef NDEBUG
+const std::size_t NumElem = 1000000;
+#else
+const std::size_t NumElem = 10000;
+#endif
+const std::size_t NumRepeat = 4;
+
+enum InsertionType
+{
+ Monotonic,
+ Random
+};
+
+template<class Container>
+void fill_vector(Container &values, InsertionType insertion_type)
+{
+ switch(insertion_type){
+ case Monotonic:{
+ for( typename Container::size_type i = 0, max = values.size()
+ ; i != max
+ ; ++i){
+ values[i].i_ = i;
+ }
+ }
+ break;
+ case Random:{
+ std::srand(0);
+ for( typename Container::size_type i = 0, max = values.size()
+ ; i != max
+ ; ++i){
+ values[i].i_ = i;
+ }
+ std::random_shuffle(values.begin(), values.end());
+ }
+ break;
+ default:{
+ std::abort();
+ }
+ }
+}
+
+template<class Container>
+void test_insertion(Container &c, const char *ContainerName, InsertionType insertion_type)
+{
+ std::cout << "Container " << ContainerName << std::endl;
+ //Prepare
+ typedef typename Container::size_type size_type;
+ typedef typename Container::value_type value_type;
+ ptime tini, tend;
+ std::vector<Container::value_type> values(NumElem);
+ {
+ fill_vector(values, insertion_type);
+ //Insert
+ tini = microsec_clock::universal_time();
+ for( size_type repeat = 0, repeat_max = NumRepeat
+ ; repeat != repeat_max
+ ; ++repeat){
+ c.clear();
+ for( size_type i = 0, max = values.size()
+ ; i != max
+ ; ++i){
+ c.insert(values[i]);
+ }
+ if(c.size() != values.size()){
+ std::cout << " ERROR: size not consistent" << std::endl;
+ }
+ }
+ tend = microsec_clock::universal_time();
+ std::cout << " Insert ns/iter: " << double((tend-tini).total_nanoseconds())/double(NumElem*NumRepeat) << std::endl;
+ }
+ //Search
+ {
+ value_type v;
+ tini = microsec_clock::universal_time();
+ for( size_type repeat = 0, repeat_max = NumRepeat
+ ; repeat != repeat_max
+ ; ++repeat){
+ size_type found = 0;
+ for( size_type i = 0, max = values.size()
+ ; i != max
+ ; ++i){
+ v.i_ = i;
+ found += static_cast<size_type>(c.end() != c.find(v));
+ }
+ if(found != NumElem){
+ std::cout << " ERROR: all not found (" << found << ") vs. (" << NumElem << ")" << std::endl;
+ }
+ }
+ tend = microsec_clock::universal_time();
+ std::cout << " Search ns/iter: " << double((tend-tini).total_nanoseconds())/double(NumElem*NumRepeat) << std::endl;
+ }
+}
+
+
+void test_insert_search(InsertionType insertion_type)
+{
+ {
+ typedef set_base_hook< link_mode<normal_link> > SetHook;
+ typedef set< itest_class<true, SetHook> > Set;
+ Set c;
+ test_insertion(c, "Set", insertion_type);
+ }
+ {
+ typedef avl_set_base_hook< link_mode<normal_link> > AvlSetHook;
+ typedef avl_set< itest_class<true, AvlSetHook> > AvlSet;
+ AvlSet c;
+ test_insertion(c, "AvlSet", insertion_type);
+ }
+ {
+ typedef bs_set_base_hook< link_mode<normal_link> > BsSetHook;
+ typedef sg_set< itest_class<true, BsSetHook> > SgSet;
+ SgSet c;
+ c.balance_factor(0.55f);
+ test_insertion(c, "SgSet(alpha 0.55)", insertion_type);
+ }
+ {
+ typedef bs_set_base_hook< link_mode<normal_link> > BsSetHook;
+ typedef sg_set< itest_class<true, BsSetHook> > SgSet;
+ SgSet c;
+ c.balance_factor(0.60f);
+ test_insertion(c, "SgSet(alpha 0.60)", insertion_type);
+ }
+ {
+ typedef bs_set_base_hook< link_mode<normal_link> > BsSetHook;
+ typedef sg_set< itest_class<true, BsSetHook> > SgSet;
+ SgSet c;
+ c.balance_factor(0.65f);
+ test_insertion(c, "SgSet(alpha 0.65)", insertion_type);
+ }
+ {
+ typedef bs_set_base_hook< link_mode<normal_link> > BsSetHook;
+ typedef sg_set< itest_class<true, BsSetHook> > SgSet;
+ SgSet c;
+ test_insertion(c, "SgSet(alpha 0.7)", insertion_type);
+ }
+ {
+ typedef bs_set_base_hook< link_mode<normal_link> > BsSetHook;
+ typedef sg_set< itest_class<true, BsSetHook> > SgSet;
+ SgSet c;
+ c.balance_factor(0.75f);
+ test_insertion(c, "SgSet(alpha 0.75)", insertion_type);
+ }
+ {
+ typedef bs_set_base_hook< link_mode<normal_link> > BsSetHook;
+ typedef sg_set< itest_class<true, BsSetHook> > SgSet;
+ SgSet c;
+ c.balance_factor(0.80f);
+ test_insertion(c, "SgSet(alpha 0.80)", insertion_type);
+ }
+ {
+ typedef bs_set_base_hook< link_mode<normal_link> > BsSetHook;
+ typedef sg_set< itest_class<true, BsSetHook>, floating_point<false> > SgSet;
+ SgSet c;
+ test_insertion(c, "SgSet(no float, alpha 1/sqrt(2)~0,7071)", insertion_type);
+ }
+}
+
+int main()
+{
+ std::cout << "MONOTONIC INPUTS\n";
+ std::cout << "----------------\n\n";
+ test_insert_search(Monotonic);
+ std::cout << "----------------\n\n";
+ std::cout << "RANDOM INPUTS\n";
+ std::cout << "----------------\n\n";
+ test_insert_search(Random);
+ std::cout << "----------------\n\n";
+ return 0;
+}
+
+#include <boost/intrusive/detail/config_end.hpp>
generated by cgit v1.2.3 (git 2.39.1) at 2025-01-30 12:44:07 +0000