Imported Upstream version 1.49.0upstream/1.49.0

3 files changed, 717 insertions, 0 deletions

diff --git a/libs/heap/tools/heap_benchmarks.hpp b/libs/heap/tools/heap_benchmarks.hpp
new file mode 100644
index 0000000000..5e1d1bbd3f
--- /dev/null
+++ b/libs/heap/tools/heap_benchmarks.hpp
@@ -0,0 +1,269 @@
+#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
+}
diff --git a/libs/heap/tools/high_resolution_timer.hpp b/libs/heap/tools/high_resolution_timer.hpp
new file mode 100644
index 0000000000..9893b24413
--- /dev/null
+++ b/libs/heap/tools/high_resolution_timer.hpp
@@ -0,0 +1,208 @@
+/*=============================================================================
+    Copyright (c) 2005-2007 Hartmut Kaiser
+                  2007, 2009 Tim Blechmann
+
+    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)
+=============================================================================*/
+#if !defined(BOOST_HIGH_RESOLUTION_TIMER_HPP)
+#define BOOST_HIGH_RESOLUTION_TIMER_HPP
+
+#include <boost/config.hpp>
+#include <boost/throw_exception.hpp>
+
+#if _POSIX_C_SOURCE >= 199309L
+
+#include "time.h"
+
+#include <stdexcept>
+#include <limits>
+
+namespace boost {
+
+class high_resolution_timer
+{
+public:
+    high_resolution_timer()
+    {
+        restart();
+    }
+
+    void restart()
+    {
+        int status = clock_gettime(CLOCK_REALTIME, &start_time);
+
+        if (status == -1)
+            boost::throw_exception(std::runtime_error("Couldn't initialize start_time"));
+    }
+
+    double elapsed() const                  // return elapsed time in seconds
+    {
+        struct timespec now;
+
+        int status = clock_gettime(CLOCK_REALTIME, &now);
+
+        if (status == -1)
+            boost::throw_exception(std::runtime_error("Couldn't get current time"));
+
+        struct timespec diff;
+
+        double ret_sec = double(now.tv_sec - start_time.tv_sec);
+        double ret_nsec = double(now.tv_nsec - start_time.tv_nsec);
+
+        while (ret_nsec < 0)
+        {
+            ret_sec -= 1.0;
+            ret_nsec += 1e9;
+        }
+
+        double ret = ret_sec + ret_nsec / 1e9;
+
+        return ret;
+    }
+
+    double elapsed_max() const   // return estimated maximum value for elapsed()
+    {
+        return double((std::numeric_limits<double>::max)());
+    }
+
+    double elapsed_min() const            // return minimum value for elapsed()
+    {
+        return 0.0;
+    }
+
+private:
+    struct timespec start_time;
+};
+
+} // namespace boost
+
+#elif defined(__APPLE__)
+
+#import <mach/mach_time.h>
+
+
+namespace boost {
+
+class high_resolution_timer
+{
+public:
+    high_resolution_timer(void)
+    {
+        mach_timebase_info_data_t info;
+
+        kern_return_t err = mach_timebase_info(&info);
+        if (err)
+            throw std::runtime_error("cannot create mach timebase info");
+
+        conversion_factor = (double)info.numer/(double)info.denom;
+        restart();
+    }
+
+    void restart()
+    {
+        start = mach_absolute_time();
+    }
+
+    double elapsed() const                  // return elapsed time in seconds
+    {
+        uint64_t now = mach_absolute_time();
+        double duration = double(now - start) * conversion_factor;
+
+        return duration
+    }
+
+    double elapsed_max() const   // return estimated maximum value for elapsed()
+    {
+        return double((std::numeric_limits<double>::max)());
+    }
+
+    double elapsed_min() const            // return minimum value for elapsed()
+    {
+        return 0.0;
+    }
+
+private:
+    uint64_t start;
+    double conversion_factor;
+};
+
+} // namespace boost
+
+#elif defined(BOOST_WINDOWS)
+
+#include <stdexcept>
+#include <limits>
+#include <windows.h>
+
+namespace boost {
+
+///////////////////////////////////////////////////////////////////////////////
+//
+//  high_resolution_timer
+//      A timer object measures elapsed time.
+//      CAUTION: Windows only!
+//
+///////////////////////////////////////////////////////////////////////////////
+class high_resolution_timer
+{
+public:
+    high_resolution_timer()
+    {
+        start_time.QuadPart = 0;
+        frequency.QuadPart = 0;
+
+        if (!QueryPerformanceFrequency(&frequency))
+            boost::throw_exception(std::runtime_error("Couldn't acquire frequency"));
+
+        restart();
+    }
+
+    void restart()
+    {
+        if (!QueryPerformanceCounter(&start_time))
+            boost::throw_exception(std::runtime_error("Couldn't initialize start_time"));
+    }
+
+    double elapsed() const                  // return elapsed time in seconds
+    {
+        LARGE_INTEGER now;
+        if (!QueryPerformanceCounter(&now))
+            boost::throw_exception(std::runtime_error("Couldn't get current time"));
+
+        return double(now.QuadPart - start_time.QuadPart) / frequency.QuadPart;
+    }
+
+    double elapsed_max() const   // return estimated maximum value for elapsed()
+    {
+        return (double((std::numeric_limits<LONGLONG>::max)())
+            - double(start_time.QuadPart)) / double(frequency.QuadPart);
+    }
+
+    double elapsed_min() const            // return minimum value for elapsed()
+    {
+        return 1.0 / frequency.QuadPart;
+    }
+
+private:
+    LARGE_INTEGER start_time;
+    LARGE_INTEGER frequency;
+};
+
+} // namespace boost
+
+#else
+
+//  For other platforms, simply fall back to boost::timer
+#include <boost/timer.hpp>
+#include <boost/throw_exception.hpp>
+
+namespace boost {
+    typedef boost::timer high_resolution_timer;
+}
+
+#endif
+
+#endif  // !defined(BOOST_HIGH_RESOLUTION_TIMER_HPP)
+
diff --git a/libs/heap/tools/throughput_benchmarks.cpp b/libs/heap/tools/throughput_benchmarks.cpp
new file mode 100644
index 0000000000..74c440a01b
--- /dev/null
+++ b/libs/heap/tools/throughput_benchmarks.cpp
@@ -0,0 +1,240 @@
+#include <iostream>
+#include <iomanip>
+
+
+#include "../../../boost/heap/d_ary_heap.hpp"
+#include "../../../boost/heap/pairing_heap.hpp"
+#include "../../../boost/heap/fibonacci_heap.hpp"
+#include "../../../boost/heap/binomial_heap.hpp"
+#include "../../../boost/heap/skew_heap.hpp"
+
+#include "heap_benchmarks.hpp"
+
+using namespace std;
+
+template <typename benchmark_selector>
+void run_benchmarks_immutable(void)
+{
+    for (int i = 4; i != max_data; ++i) {
+        for (int j = 0; j != 8; ++j) {
+            int size = 1<<i;
+            if (j%4 == 1)
+                size += 1<<(i-3);
+            if (j%4 == 2)
+                size += 1<<(i-2);
+            if (j%4 == 3)
+                size += (1<<(i-3)) + (1<<(i-2));
+            if (j >= 4)
+                size += (1<<(i-1));
+
+            cout << size << "\t";
+            {
+                typedef typename benchmark_selector::
+                    template rebind<boost::heap::d_ary_heap<long, boost::heap::arity<2> > >
+                    ::type benchmark_functor;
+                benchmark_functor benchmark(size);
+                double result = run_benchmark(benchmark);
+                cout << result << '\t';
+            }
+
+            {
+                typedef typename benchmark_selector::
+                    template rebind<boost::heap::d_ary_heap<long, boost::heap::arity<2>, boost::heap::mutable_<true> > >
+                    ::type benchmark_functor;
+                benchmark_functor benchmark(size);
+                double result = run_benchmark(benchmark);
+                cout << result << '\t';
+            }
+
+            {
+                typedef typename benchmark_selector::
+                    template rebind<boost::heap::d_ary_heap<long, boost::heap::arity<4> > >
+                    ::type benchmark_functor;
+                benchmark_functor benchmark(size);
+                double result = run_benchmark(benchmark);
+                cout << result << '\t';
+            }
+
+            {
+                typedef typename benchmark_selector::
+                    template rebind<boost::heap::d_ary_heap<long, boost::heap::arity<4>, boost::heap::mutable_<true> > >
+                    ::type benchmark_functor;
+                benchmark_functor benchmark(size);
+                double result = run_benchmark(benchmark);
+                cout << result << '\t';
+            }
+
+            {
+                typedef typename benchmark_selector::
+                    template rebind<boost::heap::d_ary_heap<long, boost::heap::arity<8> > >
+                    ::type benchmark_functor;
+                benchmark_functor benchmark(size);
+                double result = run_benchmark(benchmark);
+                cout << result << '\t';
+            }
+
+            {
+                typedef typename benchmark_selector::
+                    template rebind<boost::heap::d_ary_heap<long, boost::heap::arity<8>, boost::heap::mutable_<true> > >
+                    ::type benchmark_functor;
+                benchmark_functor benchmark(size);
+                double result = run_benchmark(benchmark);
+                cout << result << '\t';
+            }
+
+            {
+                typedef typename benchmark_selector::
+                    template rebind<boost::heap::binomial_heap<long> >
+                    ::type benchmark_functor;
+                benchmark_functor benchmark(size);
+                double result = run_benchmark(benchmark);
+                cout << result << '\t';
+            }
+
+            {
+                typedef typename benchmark_selector::
+                    template rebind<boost::heap::fibonacci_heap<long> >
+                    ::type benchmark_functor;
+                benchmark_functor benchmark(size);
+                double result = run_benchmark(benchmark);
+                cout << result << '\t';
+            }
+
+            {
+                typedef typename benchmark_selector::
+                    template rebind<boost::heap::pairing_heap<long> >
+                    ::type benchmark_functor;
+                benchmark_functor benchmark(size);
+                double result = run_benchmark(benchmark);
+                cout << result << '\t';
+            }
+
+            {
+                typedef typename benchmark_selector::
+                    template rebind<boost::heap::skew_heap<long> >
+                    ::type benchmark_functor;
+                benchmark_functor benchmark(size);
+                double result = run_benchmark(benchmark);
+                cout << result << '\t';
+            }
+
+            {
+                typedef typename benchmark_selector::
+                    template rebind<boost::heap::skew_heap<long> >
+                    ::type benchmark_functor;
+                benchmark_functor benchmark(size);
+                double result = run_benchmark(benchmark);
+                cout << result << '\t';
+            }
+            cout << endl;
+        }
+    }
+}
+
+template <typename benchmark_selector>
+void run_benchmarks_mutable(void)
+{
+    for (int i = 4; i != max_data; ++i)
+    {
+        for (int j = 0; j != 8; ++j)
+        {
+            int size = 1<<i;
+            if (j%4 == 1)
+                size += 1<<(i-3);
+            if (j%4 == 2)
+                size += 1<<(i-2);
+            if (j%4 == 3)
+                size += (1<<(i-3)) + (1<<(i-2));
+            if (j >= 4)
+                size += (1<<(i-1));
+
+            cout << size << "\t";
+            {
+                typedef typename benchmark_selector::
+                    template rebind<boost::heap::d_ary_heap<long, boost::heap::arity<2>, boost::heap::mutable_<true> > >
+                    ::type benchmark_functor;
+                benchmark_functor benchmark(size);
+                double result = run_benchmark(benchmark);
+                cout << result << '\t';
+            }
+
+            {
+                typedef typename benchmark_selector::
+                    template rebind<boost::heap::d_ary_heap<long, boost::heap::arity<4>, boost::heap::mutable_<true> > >
+                    ::type benchmark_functor;
+                benchmark_functor benchmark(size);
+                double result = run_benchmark(benchmark);
+                cout << result << '\t';
+            }
+
+            {
+                typedef typename benchmark_selector::
+                    template rebind<boost::heap::d_ary_heap<long, boost::heap::arity<8>, boost::heap::mutable_<true> > >
+                    ::type benchmark_functor;
+                benchmark_functor benchmark(size);
+                double result = run_benchmark(benchmark);
+                cout << result << '\t';
+            }
+
+            {
+                typedef typename benchmark_selector::
+                    template rebind<boost::heap::binomial_heap<long> >
+                    ::type benchmark_functor;
+                benchmark_functor benchmark(size);
+                double result = run_benchmark(benchmark);
+                cout << result << '\t';
+            }
+
+            {
+                typedef typename benchmark_selector::
+                    template rebind<boost::heap::fibonacci_heap<long> >
+                    ::type benchmark_functor;
+                benchmark_functor benchmark(size);
+                double result = run_benchmark(benchmark);
+                cout << result << '\t';
+            }
+
+            {
+                typedef typename benchmark_selector::
+                    template rebind<boost::heap::pairing_heap<long> >
+                    ::type benchmark_functor;
+                benchmark_functor benchmark(size);
+                double result = run_benchmark(benchmark);
+                cout << result << '\t';
+            }
+
+            {
+                typedef typename benchmark_selector::
+                    template rebind<boost::heap::skew_heap<long, boost::heap::mutable_<true> > >
+                    ::type benchmark_functor;
+                benchmark_functor benchmark(size);
+                double result = run_benchmark(benchmark);
+                cout << result << '\t';
+            }
+            cout << endl;
+        }
+    }
+}
+
+int main()
+{
+    cout << fixed << setprecision(12);
+
+    cout << "sequential push" << endl;
+    run_benchmarks_immutable<make_sequential_push>();
+
+    cout << endl << "sequential pop" << endl;
+    run_benchmarks_immutable<make_sequential_pop>();
+
+    cout << endl << "sequential increase" << endl;
+    run_benchmarks_mutable<make_sequential_increase>();
+
+    cout << endl << "sequential decrease" << endl;
+    run_benchmarks_mutable<make_sequential_decrease>();
+
+    cout << endl << "merge_and_clear" << endl;
+    run_benchmarks_immutable<make_merge_and_clear>();
+
+    cout << endl << "equivalence" << endl;
+    run_benchmarks_immutable<make_equivalence>();
+}