[boost] [Heaps] benchmarks

Subject: [boost] [Heaps] benchmarks
From: Phil Endecott (spam_from_boost_dev_at_[hidden])
Date: 2011-06-07 17:32:20

Dear All,

I have done some quick benchmarks; the code can be found here:

     http://chezphil.org/tmp/bench.tgz

This is a "work queue", i.e. it's a queue of 
boost::function<void(void)> "work items" with float priorities.  It's 
similar to a real application with fast (burst) fill and gradual drain; 
the pattern here is 10 pushes and 1 pop, repeated until all the work 
has been added, and then all of the work is popped in sequence.  The 
priorities are essentially random, and there are 100 000 items in total.

Currently my real application uses a std::multimap.  I've compared that 
with a std::vector using std::push|pop_heap, std::priority_queue using 
std::vector and std::deque, and the proposed heap::priority_queue and heap::b_heap.

The columns below are median-of-3 runtimes in seconds for:

1. 50 runs on a 32-bit 3 GHz AMD Athlon II Linux system, using g++ 
4.4.4 -O4.
2. 10 runs on a 32-bit 1.2 GHz VIA C7-M Linux syste, using g++4.4.2 -O4.
3. 5 runs on a 1.2 GHz ARMv5 Linux system, using g++ 4.4.2 -O4.

std::multimap                      3.20    3.69    3.37
std::vector + std::push|pop_heap   2.35    3.36    2.71
std::priority_queue<vector>        2.58    3.48    2.84
std::priority_queue<deque>         4.27    5.77    3.72
heap::priority_queue               2.49    3.37    2.74
heap::b_heap                       5.14    7.62    5.82

I was unable to try the proposed d_ary_heap because I couldn't find a 
working syntax for the arity template parameter - any ideas anyone?

The 3 implementations based on std::vector perform similarly, as 
expected.  I'm a bit surprised that my one is fastest, but the 
difference is small.  Also as expected the version using multimap is 
slower, though maybe not by as much as I had expected.

I was expecting the b_heap to be faster, but it is not; it is 
substantially slower.  What is going on there?  Does it all come down 
to size of data, cache size, etc?  Ideally, an "improved" 
implementation like this would be able to fall back to the naive 
implementation in cases where it does not function any better.  Or 
maybe I'm using it wrongly.

My understanding is that the fibonacci, binomial and other heaps only 
improve things when other operations e.g. merging are needed - is that correct?

Regards,  Phil.