Re: [boost] [Heaps] benchmarks

Subject: Re: [boost] [Heaps] benchmarks
From: Thomas Klimpel (Thomas.Klimpel_at_[hidden])
Date: 2011-06-13 08:43:56

Phil Endecott wrote:
> 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.

You have specified -O4 as compile option, but not -DNDEBUG. For me, some of the heaps from Boost.Heap are actually faster than the other options when I specify -DNDEBUG. Not specifying -DNDEBUG is an unfair comparison, since the extensive use of assertions is not a bad thing.

> 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 get the following times on a ubuntu system with gcc-4.4.3 (I also added another heap to the comparison):

time ./bench_seqheap
3.36user 0.18system 0:03.61elapsed 98%CPU (0avgtext+0avgdata 14736maxresident)k
0inputs+0outputs (0major+28908minor)pagefaults 0swaps
time ./bench_boostbheap
11.94user 0.18system 0:12.26elapsed 98%CPU (0avgtext+0avgdata 12064maxresident)k
0inputs+0outputs (0major+22377minor)pagefaults 0swaps
time ./bench_boostqueue
6.20user 0.18system 0:07.51elapsed 85%CPU (0avgtext+0avgdata 12000maxresident)k
0inputs+0outputs (0major+22372minor)pagefaults 0swaps
time ./bench_boostdary
5.90user 0.14system 0:06.13elapsed 98%CPU (0avgtext+0avgdata 12016maxresident)k
0inputs+0outputs (0major+22373minor)pagefaults 0swaps
time ./bench_stdqueuedeque
9.17user 0.14system 0:09.46elapsed 98%CPU (0avgtext+0avgdata 12192maxresident)k
0inputs+0outputs (0major+21257minor)pagefaults 0swaps
time ./bench_stdqueuevec
6.23user 0.42system 0:06.85elapsed 97%CPU (0avgtext+0avgdata 15808maxresident)k
0inputs+0outputs (0major+52910minor)pagefaults 0swaps
time ./bench_stdheap
6.00user 0.15system 0:06.24elapsed 98%CPU (0avgtext+0avgdata 12016maxresident)k
0inputs+0outputs (0major+22373minor)pagefaults 0swaps
time ./bench_map
8.58user 0.04system 0:08.72elapsed 98%CPU (0avgtext+0avgdata 19136maxresident)k
0inputs+0outputs (0major+1250minor)pagefaults 0swaps

My own conclusion is that besides b_heap, all heaps perfrom quite reasonable. I also see that the d_ary heap performs quite well.

Regards,
Thomas