Squashed 'third_party/boostorg/multi_index/' content from commit d95a949
Change-Id: Ie67c2d797c11dc122c7f11e767e81691bf2191a4
git-subtree-dir: third_party/boostorg/multi_index
git-subtree-split: d95a94942b918140e565feb99ed36ea97c30084e
diff --git a/perf/test_perf.cpp b/perf/test_perf.cpp
new file mode 100644
index 0000000..7b24417
--- /dev/null
+++ b/perf/test_perf.cpp
@@ -0,0 +1,545 @@
+/* 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;
+}