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