Adding upstream version 14.2.21.upstream/14.2.21upstream

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

1 files changed, 277 insertions, 0 deletions

diff --git a/src/boost/libs/heap/tools/heap_benchmarks.hpp b/src/boost/libs/heap/tools/heap_benchmarks.hpp
new file mode 100644
index 00000000..08bc6579
--- /dev/null
+++ b/src/boost/libs/heap/tools/heap_benchmarks.hpp
@@ -0,0 +1,277 @@
+/*=============================================================================
+    Copyright (c) 2010 Tim Blechmann
+
+    Use, modification and distribution is 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)
+=============================================================================*/
+
+#include <algorithm>
+#include <vector>
+
+#include <boost/foreach.hpp>
+#include "high_resolution_timer.hpp"
+
+#include <boost/heap/heap_merge.hpp>
+
+#if defined(__GNUC__) && (!defined __INTEL_COMPILER)
+#define no_inline __attribute__ ((noinline))
+#else
+#define no_inline
+#endif
+
+typedef std::vector<int> test_data;
+
+const int num_benchmarks = 1;
+
+inline test_data make_sequential_test_data(int size)
+{
+    test_data v(size);
+    for (int i = 0; i != size; ++i)
+        v[i] = i;
+    return v;
+}
+
+inline test_data make_test_data(int size)
+{
+    test_data v = make_sequential_test_data(size);
+    std::random_shuffle(v.begin(), v.end());
+    return v;
+}
+
+const int max_data = 20;
+
+test_data const & get_data(int index)
+{
+    static std::vector <test_data> data;
+    if (data.empty())
+        for (int i = 0; i != num_benchmarks; ++i)
+            data.push_back(make_test_data((1<<(max_data+1))+1024));
+
+    return data[index];
+}
+
+
+#define DEFINE_BENCHMARKS_SELECTOR(SUFFIX)  \
+struct make_##SUFFIX                        \
+{                                           \
+    template <typename heap>                \
+    struct rebind {                         \
+        typedef run_##SUFFIX<heap> type;    \
+    };                                      \
+};
+
+
+template <typename pri_queue>
+void fill_heap(pri_queue & q, int index, int size, int offset = 0)
+{
+    test_data const & data = get_data(index);
+
+    for (int i = 0; i != size + 1; ++i) {
+        q.push(data[i]);
+        int top = q.top();
+        q.pop();
+        q.push(top);
+    }
+}
+
+template <typename pri_queue,
+          typename handle_container
+         >
+void fill_heap_with_handles(pri_queue & q, handle_container & handles, int index, int size, int offset = 0)
+{
+    test_data const & data = get_data(index);
+
+    for (int i = 0; i != size + 1; ++i) {
+        handles[i] = q.push(data[i]);
+
+        if (i > 0) {
+            typename pri_queue::handle_type last = handles[i-1];
+            int val = *last;
+            q.erase(last);
+            handles[i-1] = q.push(val);
+        }
+    }
+}
+
+
+template <typename pri_queue>
+struct run_sequential_push
+{
+    run_sequential_push(int size):
+        size(size)
+    {}
+
+    void prepare(int index)
+    {
+        q.clear();
+        fill_heap(q, index, size);
+    }
+
+    no_inline void operator()(int index)
+    {
+        test_data const & data = get_data(index);
+
+        for (int i = 0; i != 16; ++i)
+            q.push(data[(1<<max_data) + i]);
+    }
+
+    pri_queue q;
+    int size;
+};
+
+DEFINE_BENCHMARKS_SELECTOR(sequential_push)
+
+template <typename pri_queue>
+struct run_sequential_pop
+{
+    run_sequential_pop(int size):
+        size(size)
+    {}
+
+    void prepare(int index)
+    {
+        q.clear();
+        fill_heap(q, index, size);
+    }
+
+    no_inline void operator()(int index)
+    {
+        for (int i = 0; i != 16; ++i)
+            q.pop();
+    }
+
+    pri_queue q;
+    int size;
+};
+
+DEFINE_BENCHMARKS_SELECTOR(sequential_pop)
+
+template <typename pri_queue>
+struct run_sequential_increase
+{
+    run_sequential_increase(int size):
+        size(size), handles(size)
+    {}
+
+    void prepare(int index)
+    {
+        q.clear();
+        fill_heap_with_handles(q, handles, index, size);
+    }
+
+    no_inline void operator()(int index)
+    {
+        test_data const & data = get_data(index);
+        for (int i = 0; i != 16; ++i)
+            q.increase(handles[i], data[i] + (1<<max_data));
+    }
+
+    pri_queue q;
+    int size;
+    std::vector<typename pri_queue::handle_type> handles;
+};
+
+DEFINE_BENCHMARKS_SELECTOR(sequential_increase)
+
+template <typename pri_queue>
+struct run_sequential_decrease
+{
+    run_sequential_decrease(int size):
+        size(size), handles(size)
+    {}
+
+    void prepare(int index)
+    {
+        q.clear();
+        fill_heap_with_handles(q, handles, index, size);
+    }
+
+    no_inline void operator()(int index)
+    {
+        test_data const & data = get_data(index);
+        for (int i = 0; i != 16; ++i)
+            q.decrease(handles[i], data[i] + (1<<max_data));
+    }
+
+    pri_queue q;
+    int size;
+    std::vector<typename pri_queue::handle_type> handles;
+};
+
+DEFINE_BENCHMARKS_SELECTOR(sequential_decrease)
+
+template <typename pri_queue>
+struct run_merge_and_clear
+{
+    run_merge_and_clear(int size):
+        size(size)
+    {}
+
+    void prepare(int index)
+    {
+        q.clear();
+        r.clear();
+
+        fill_heap(q, index, size);
+        fill_heap(r, index, size, size);
+    }
+
+    no_inline void operator()(int index)
+    {
+        boost::heap::heap_merge(q, r);
+    }
+
+    pri_queue q, r;
+    int size;
+};
+
+DEFINE_BENCHMARKS_SELECTOR(merge_and_clear)
+
+template <typename pri_queue>
+struct run_equivalence
+{
+    run_equivalence(int size):
+        size(size)
+    {}
+
+    void prepare(int index)
+    {
+        q.clear();
+        r.clear();
+        s.clear();
+
+        fill_heap(q, index, size);
+        fill_heap(r, index, size, size);
+        fill_heap(s, index, size);
+    }
+
+    no_inline bool operator()(int index)
+    {
+        return (q == r) ^ (q == s);
+    }
+
+    pri_queue q, r, s;
+    int size;
+};
+
+DEFINE_BENCHMARKS_SELECTOR(equivalence)
+
+
+template <typename benchmark>
+inline double run_benchmark(benchmark & b)
+{
+    boost::high_resolution_timer timer;
+    std::vector<double> results;
+
+    for (int i = 0; i != num_benchmarks; ++i)
+    {
+        b.prepare(i);
+        timer.restart();
+        b(i);
+        double t = timer.elapsed();
+        results.push_back(t);
+    }
+
+    return results.at(results.size()/2); // median
+}