summaryrefslogtreecommitdiffstats
path: root/src/boost/libs/heap/tools
diff options
context:
space:
mode:
Diffstat (limited to 'src/boost/libs/heap/tools')
-rw-r--r--src/boost/libs/heap/tools/heap_benchmarks.hpp277
-rw-r--r--src/boost/libs/heap/tools/high_resolution_timer.hpp208
-rw-r--r--src/boost/libs/heap/tools/throughput_benchmarks.cpp248
3 files changed, 733 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
+}
diff --git a/src/boost/libs/heap/tools/high_resolution_timer.hpp b/src/boost/libs/heap/tools/high_resolution_timer.hpp
new file mode 100644
index 00000000..9893b244
--- /dev/null
+++ b/src/boost/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/src/boost/libs/heap/tools/throughput_benchmarks.cpp b/src/boost/libs/heap/tools/throughput_benchmarks.cpp
new file mode 100644
index 00000000..ea3f5b0d
--- /dev/null
+++ b/src/boost/libs/heap/tools/throughput_benchmarks.cpp
@@ -0,0 +1,248 @@
+/*=============================================================================
+ 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 <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>();
+}
generated by cgit v1.2.3 (git 2.39.1) at 2025-01-08 21:29:06 +0000