Adding upstream version 16.2.11+ds.upstream/16.2.11+dsupstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 545 insertions, 0 deletions

diff --git a/src/boost/libs/multi_index/perf/test_perf.cpp b/src/boost/libs/multi_index/perf/test_perf.cpp
new file mode 100644
index 000000000..7b2441787
--- /dev/null
+++ b/src/boost/libs/multi_index/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;
+}