123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277 |
- /*=============================================================================
- 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
- }
|