libs/heap/tools/heap_benchmarks.hpp

   1 /*=============================================================================
   2     Copyright (c) 2010 Tim Blechmann
   3
   4     Use, modification and distribution is subject to the Boost Software
   5     License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   6     http://www.boost.org/LICENSE_1_0.txt)
   7 =============================================================================*/
   8
   9 #include <algorithm>
  10 #include <vector>
  11
  12 #include <boost/foreach.hpp>
  13 #include "high_resolution_timer.hpp"
  14
  15 #include <boost/heap/heap_merge.hpp>
  16
  17 #if defined(__GNUC__) && (!defined __INTEL_COMPILER)
  18 #define no_inline __attribute__ ((noinline))
  19 #else
  20 #define no_inline
  21 #endif
  22
  23 typedef std::vector<int> test_data;
  24
  25 const int num_benchmarks = 1;
  26
  27 inline test_data make_sequential_test_data(int size)
  28 {
  29     test_data v(size);
  30     for (int i = 0; i != size; ++i)
  31         v[i] = i;
  32     return v;
  33 }
  34
  35 inline test_data make_test_data(int size)
  36 {
  37     test_data v = make_sequential_test_data(size);
  38     std::random_shuffle(v.begin(), v.end());
  39     return v;
  40 }
  41
  42 const int max_data = 20;
  43
  44 test_data const & get_data(int index)
  45 {
  46     static std::vector <test_data> data;
  47     if (data.empty())
  48         for (int i = 0; i != num_benchmarks; ++i)
  49             data.push_back(make_test_data((1<<(max_data+1))+1024));
  50
  51     return data[index];
  52 }
  53
  54
  55 #define DEFINE_BENCHMARKS_SELECTOR(SUFFIX)  \
  56 struct make_##SUFFIX                        \
  57 {                                           \
  58     template <typename heap>                \
  59     struct rebind {                         \
  60         typedef run_##SUFFIX<heap> type;    \
  61     };                                      \
  62 };
  63
  64
  65 template <typename pri_queue>
  66 void fill_heap(pri_queue & q, int index, int size, int offset = 0)
  67 {
  68     test_data const & data = get_data(index);
  69
  70     for (int i = 0; i != size + 1; ++i) {
  71         q.push(data[i]);
  72         int top = q.top();
  73         q.pop();
  74         q.push(top);
  75     }
  76 }
  77
  78 template <typename pri_queue,
  79           typename handle_container
  80          >
  81 void fill_heap_with_handles(pri_queue & q, handle_container & handles, int index, int size, int offset = 0)
  82 {
  83     test_data const & data = get_data(index);
  84
  85     for (int i = 0; i != size + 1; ++i) {
  86         handles[i] = q.push(data[i]);
  87
  88         if (i > 0) {
  89             typename pri_queue::handle_type last = handles[i-1];
  90             int val = *last;
  91             q.erase(last);
  92             handles[i-1] = q.push(val);
  93         }
  94     }
  95 }
  96
  97
  98 template <typename pri_queue>
  99 struct run_sequential_push
 100 {
 101     run_sequential_push(int size):
 102         size(size)
 103     {}
 104
 105     void prepare(int index)
 106     {
 107         q.clear();
 108         fill_heap(q, index, size);
 109     }
 110
 111     no_inline void operator()(int index)
 112     {
 113         test_data const & data = get_data(index);
 114
 115         for (int i = 0; i != 16; ++i)
 116             q.push(data[(1<<max_data) + i]);
 117     }
 118
 119     pri_queue q;
 120     int size;
 121 };
 122
 123 DEFINE_BENCHMARKS_SELECTOR(sequential_push)
 124
 125 template <typename pri_queue>
 126 struct run_sequential_pop
 127 {
 128     run_sequential_pop(int size):
 129         size(size)
 130     {}
 131
 132     void prepare(int index)
 133     {
 134         q.clear();
 135         fill_heap(q, index, size);
 136     }
 137
 138     no_inline void operator()(int index)
 139     {
 140         for (int i = 0; i != 16; ++i)
 141             q.pop();
 142     }
 143
 144     pri_queue q;
 145     int size;
 146 };
 147
 148 DEFINE_BENCHMARKS_SELECTOR(sequential_pop)
 149
 150 template <typename pri_queue>
 151 struct run_sequential_increase
 152 {
 153     run_sequential_increase(int size):
 154         size(size), handles(size)
 155     {}
 156
 157     void prepare(int index)
 158     {
 159         q.clear();
 160         fill_heap_with_handles(q, handles, index, size);
 161     }
 162
 163     no_inline void operator()(int index)
 164     {
 165         test_data const & data = get_data(index);
 166         for (int i = 0; i != 16; ++i)
 167             q.increase(handles[i], data[i] + (1<<max_data));
 168     }
 169
 170     pri_queue q;
 171     int size;
 172     std::vector<typename pri_queue::handle_type> handles;
 173 };
 174
 175 DEFINE_BENCHMARKS_SELECTOR(sequential_increase)
 176
 177 template <typename pri_queue>
 178 struct run_sequential_decrease
 179 {
 180     run_sequential_decrease(int size):
 181         size(size), handles(size)
 182     {}
 183
 184     void prepare(int index)
 185     {
 186         q.clear();
 187         fill_heap_with_handles(q, handles, index, size);
 188     }
 189
 190     no_inline void operator()(int index)
 191     {
 192         test_data const & data = get_data(index);
 193         for (int i = 0; i != 16; ++i)
 194             q.decrease(handles[i], data[i] + (1<<max_data));
 195     }
 196
 197     pri_queue q;
 198     int size;
 199     std::vector<typename pri_queue::handle_type> handles;
 200 };
 201
 202 DEFINE_BENCHMARKS_SELECTOR(sequential_decrease)
 203
 204 template <typename pri_queue>
 205 struct run_merge_and_clear
 206 {
 207     run_merge_and_clear(int size):
 208         size(size)
 209     {}
 210
 211     void prepare(int index)
 212     {
 213         q.clear();
 214         r.clear();
 215
 216         fill_heap(q, index, size);
 217         fill_heap(r, index, size, size);
 218     }
 219
 220     no_inline void operator()(int index)
 221     {
 222         boost::heap::heap_merge(q, r);
 223     }
 224
 225     pri_queue q, r;
 226     int size;
 227 };
 228
 229 DEFINE_BENCHMARKS_SELECTOR(merge_and_clear)
 230
 231 template <typename pri_queue>
 232 struct run_equivalence
 233 {
 234     run_equivalence(int size):
 235         size(size)
 236     {}
 237
 238     void prepare(int index)
 239     {
 240         q.clear();
 241         r.clear();
 242         s.clear();
 243
 244         fill_heap(q, index, size);
 245         fill_heap(r, index, size, size);
 246         fill_heap(s, index, size);
 247     }
 248
 249     no_inline bool operator()(int index)
 250     {
 251         return (q == r) ^ (q == s);
 252     }
 253
 254     pri_queue q, r, s;
 255     int size;
 256 };
 257
 258 DEFINE_BENCHMARKS_SELECTOR(equivalence)
 259
 260
 261 template <typename benchmark>
 262 inline double run_benchmark(benchmark & b)
 263 {
 264     boost::high_resolution_timer timer;
 265     std::vector<double> results;
 266
 267     for (int i = 0; i != num_benchmarks; ++i)
 268     {
 269         b.prepare(i);
 270         timer.restart();
 271         b(i);
 272         double t = timer.elapsed();
 273         results.push_back(t);
 274     }
 275
 276     return results.at(results.size()/2); // median
 277 }