Re: [boost] [heap] A performance test and some questions

Thomas Klimpel wrote:

We can see that "fibonacci_heap" has always more than a factor two fewer comparisons than TStaticHeap (a simple text book binary heap implementation used as reference), but is always more than a factor two slower than TStaticHeap.

Actually, it looks like I had the most unfortunate compiler/platform combination possible (gcc-4.3.4 on cygwin). I have now tested on the same machine, but with different compilers and different platforms (linux32/cygwin/win32/). On linux, "fibonacci_heap" is actually faster than TStaticHeap. (I have compiled with -march_native, and -DSLOPPY_COMPARE, for better performance: g++ -o linux heaptest.cpp -O2 -DNDEBUG -march=native -Iboost_heap-449f378 -I/media/sda1/nobackup/boost_release/ -DHAVE_SEQ_HEAP -DSLOPPY_COMPARE). Looks like the performance of a each specific heap implementation heavily depends on the compiler, but in a pretty unpredictable way. Regards, Thomas -------- gcc-4.4.3 (linux32): Performance Check for Linear Forward 220 ticks and 0 compares for TStaticHeap 230 ticks and 0 compares for TStaticHeap 80 ticks and 0 compares for TSequentialHeap 70 ticks and 0 compares for TSequentialHeap 470 ticks and 0 compares for b_heap 460 ticks and 0 compares for b_heap 410 ticks and 0 compares for binomial_heap 430 ticks and 0 compares for binomial_heap 340 ticks and 0 compares for d_ary_heap 360 ticks and 0 compares for d_ary_heap 200 ticks and 0 compares for fibonacci_heap 210 ticks and 0 compares for fibonacci_heap Performance Check for Linear Backward 240 ticks and 0 compares for TStaticHeap 230 ticks and 0 compares for TStaticHeap 90 ticks and 0 compares for TSequentialHeap 80 ticks and 0 compares for TSequentialHeap 590 ticks and 0 compares for b_heap 600 ticks and 0 compares for b_heap 280 ticks and 0 compares for binomial_heap 300 ticks and 0 compares for binomial_heap 380 ticks and 0 compares for d_ary_heap 400 ticks and 0 compares for d_ary_heap 220 ticks and 0 compares for fibonacci_heap 230 ticks and 0 compares for fibonacci_heap Performance Check for March 1320 ticks and 0 compares for TStaticHeap 1290 ticks and 0 compares for TStaticHeap 620 ticks and 0 compares for TSequentialHeap 600 ticks and 0 compares for TSequentialHeap 2530 ticks and 0 compares for b_heap 2520 ticks and 0 compares for b_heap 3480 ticks and 0 compares for binomial_heap 3540 ticks and 0 compares for binomial_heap 1880 ticks and 0 compares for d_ary_heap 1870 ticks and 0 compares for d_ary_heap 1130 ticks and 0 compares for fibonacci_heap 1170 ticks and 0 compares for fibonacci_heap gcc-4.3.4 (cygwin): Performance Check for Linear Forward 265 ticks and 0 compares for TStaticHeap 234 ticks and 0 compares for TStaticHeap 79 ticks and 0 compares for TSequentialHeap 62 ticks and 0 compares for TSequentialHeap 875 ticks and 0 compares for b_heap 875 ticks and 0 compares for b_heap 844 ticks and 0 compares for binomial_heap 844 ticks and 0 compares for binomial_heap 781 ticks and 0 compares for d_ary_heap 797 ticks and 0 compares for d_ary_heap 609 ticks and 0 compares for fibonacci_heap 594 ticks and 0 compares for fibonacci_heap Performance Check for Linear Backward 266 ticks and 0 compares for TStaticHeap 234 ticks and 0 compares for TStaticHeap 94 ticks and 0 compares for TSequentialHeap 78 ticks and 0 compares for TSequentialHeap 1015 ticks and 0 compares for b_heap 1016 ticks and 0 compares for b_heap 703 ticks and 0 compares for binomial_heap 687 ticks and 0 compares for binomial_heap 798 ticks and 0 compares for d_ary_heap 812 ticks and 0 compares for d_ary_heap 610 ticks and 0 compares for fibonacci_heap 625 ticks and 0 compares for fibonacci_heap Performance Check for March 1499 ticks and 0 compares for TStaticHeap 1469 ticks and 0 compares for TStaticHeap 781 ticks and 0 compares for TSequentialHeap 782 ticks and 0 compares for TSequentialHeap 5155 ticks and 0 compares for b_heap 5125 ticks and 0 compares for b_heap 5922 ticks and 0 compares for binomial_heap 5890 ticks and 0 compares for binomial_heap 4407 ticks and 0 compares for d_ary_heap 4375 ticks and 0 compares for d_ary_heap 3703 ticks and 0 compares for fibonacci_heap 3703 ticks and 0 compares for fibonacci_heap gcc-4.3.3 (win32): Performance Check for Linear Forward 266 ticks and 0 compares for TStaticHeap 234 ticks and 0 compares for TStaticHeap 94 ticks and 0 compares for TSequentialHeap 62 ticks and 0 compares for TSequentialHeap 813 ticks and 0 compares for b_heap 875 ticks and 0 compares for b_heap 765 ticks and 0 compares for binomial_heap 735 ticks and 0 compares for binomial_heap 719 ticks and 0 compares for d_ary_heap 813 ticks and 0 compares for d_ary_heap 547 ticks and 0 compares for fibonacci_heap 562 ticks and 0 compares for fibonacci_heap Performance Check for Linear Backward 250 ticks and 0 compares for TStaticHeap 250 ticks and 0 compares for TStaticHeap 94 ticks and 0 compares for TSequentialHeap 94 ticks and 0 compares for TSequentialHeap 984 ticks and 0 compares for b_heap 984 ticks and 0 compares for b_heap 625 ticks and 0 compares for binomial_heap 641 ticks and 0 compares for binomial_heap 765 ticks and 0 compares for d_ary_heap 766 ticks and 0 compares for d_ary_heap 578 ticks and 0 compares for fibonacci_heap 562 ticks and 0 compares for fibonacci_heap Performance Check for March 1500 ticks and 0 compares for TStaticHeap 1453 ticks and 0 compares for TStaticHeap 875 ticks and 0 compares for TSequentialHeap 860 ticks and 0 compares for TSequentialHeap 3781 ticks and 0 compares for b_heap 3797 ticks and 0 compares for b_heap 4484 ticks and 0 compares for binomial_heap 4469 ticks and 0 compares for binomial_heap 2953 ticks and 0 compares for d_ary_heap 3016 ticks and 0 compares for d_ary_heap 2218 ticks and 0 compares for fibonacci_heap 2219 ticks and 0 compares for fibonacci_heap gcc-4.5.2 (win32): Performance Check for Linear Forward 235 ticks and 0 compares for TStaticHeap 234 ticks and 0 compares for TStaticHeap 94 ticks and 0 compares for TSequentialHeap 78 ticks and 0 compares for TSequentialHeap 797 ticks and 0 compares for b_heap 875 ticks and 0 compares for b_heap 750 ticks and 0 compares for binomial_heap 750 ticks and 0 compares for binomial_heap 703 ticks and 0 compares for d_ary_heap 828 ticks and 0 compares for d_ary_heap 563 ticks and 0 compares for fibonacci_heap 562 ticks and 0 compares for fibonacci_heap Performance Check for Linear Backward 250 ticks and 0 compares for TStaticHeap 235 ticks and 0 compares for TStaticHeap 109 ticks and 0 compares for TSequentialHeap 109 ticks and 0 compares for TSequentialHeap 922 ticks and 0 compares for b_heap 922 ticks and 0 compares for b_heap 625 ticks and 0 compares for binomial_heap 609 ticks and 0 compares for binomial_heap 750 ticks and 0 compares for d_ary_heap 735 ticks and 0 compares for d_ary_heap 594 ticks and 0 compares for fibonacci_heap 578 ticks and 0 compares for fibonacci_heap Performance Check for March 1281 ticks and 0 compares for TStaticHeap 1250 ticks and 0 compares for TStaticHeap 937 ticks and 0 compares for TSequentialHeap 938 ticks and 0 compares for TSequentialHeap 3422 ticks and 0 compares for b_heap 3437 ticks and 0 compares for b_heap 4188 ticks and 0 compares for binomial_heap 4234 ticks and 0 compares for binomial_heap 2750 ticks and 0 compares for d_ary_heap 2797 ticks and 0 compares for d_ary_heap 2031 ticks and 0 compares for fibonacci_heap 2032 ticks and 0 compares for fibonacci_heap MSVC9: Performance Check for Linear Forward 250 ticks and 0 compares for TStaticHeap 265 ticks and 0 compares for TStaticHeap 78 ticks and 0 compares for TSequentialHeap 63 ticks and 0 compares for TSequentialHeap 1062 ticks and 0 compares for b_heap 1141 ticks and 0 compares for b_heap 781 ticks and 0 compares for binomial_heap 782 ticks and 0 compares for binomial_heap 687 ticks and 0 compares for d_ary_heap 766 ticks and 0 compares for d_ary_heap 562 ticks and 0 compares for fibonacci_heap 563 ticks and 0 compares for fibonacci_heap Performance Check for Linear Backward 250 ticks and 0 compares for TStaticHeap 250 ticks and 0 compares for TStaticHeap 94 ticks and 0 compares for TSequentialHeap 94 ticks and 0 compares for TSequentialHeap 1312 ticks and 0 compares for b_heap 1250 ticks and 0 compares for b_heap 625 ticks and 0 compares for binomial_heap 625 ticks and 0 compares for binomial_heap 719 ticks and 0 compares for d_ary_heap 688 ticks and 0 compares for d_ary_heap 609 ticks and 0 compares for fibonacci_heap 562 ticks and 0 compares for fibonacci_heap Performance Check for March 1344 ticks and 0 compares for TStaticHeap 1297 ticks and 0 compares for TStaticHeap 781 ticks and 0 compares for TSequentialHeap 766 ticks and 0 compares for TSequentialHeap 5031 ticks and 0 compares for b_heap 5047 ticks and 0 compares for b_heap 4375 ticks and 0 compares for binomial_heap 4360 ticks and 0 compares for binomial_heap 2562 ticks and 0 compares for d_ary_heap 2594 ticks and 0 compares for d_ary_heap 2031 ticks and 0 compares for fibonacci_heap 2016 ticks and 0 compares for fibonacci_heap MSVC10: Performance Check for Linear Forward 250 ticks and 0 compares for TStaticHeap 250 ticks and 0 compares for TStaticHeap 63 ticks and 0 compares for TSequentialHeap 63 ticks and 0 compares for TSequentialHeap 875 ticks and 0 compares for b_heap 969 ticks and 0 compares for b_heap 750 ticks and 0 compares for binomial_heap 766 ticks and 0 compares for binomial_heap 656 ticks and 0 compares for d_ary_heap 750 ticks and 0 compares for d_ary_heap 594 ticks and 0 compares for fibonacci_heap 562 ticks and 0 compares for fibonacci_heap Performance Check for Linear Backward 266 ticks and 0 compares for TStaticHeap 250 ticks and 0 compares for TStaticHeap 94 ticks and 0 compares for TSequentialHeap 78 ticks and 0 compares for TSequentialHeap 1078 ticks and 0 compares for b_heap 1062 ticks and 0 compares for b_heap 594 ticks and 0 compares for binomial_heap 609 ticks and 0 compares for binomial_heap 672 ticks and 0 compares for d_ary_heap 672 ticks and 0 compares for d_ary_heap 578 ticks and 0 compares for fibonacci_heap 562 ticks and 0 compares for fibonacci_heap Performance Check for March 1328 ticks and 0 compares for TStaticHeap 1313 ticks and 0 compares for TStaticHeap 765 ticks and 0 compares for TSequentialHeap 750 ticks and 0 compares for TSequentialHeap 4000 ticks and 0 compares for b_heap 4000 ticks and 0 compares for b_heap 4359 ticks and 0 compares for binomial_heap 4344 ticks and 0 compares for binomial_heap 2390 ticks and 0 compares for d_ary_heap 2438 ticks and 0 compares for d_ary_heap 2062 ticks and 0 compares for fibonacci_heap 2063 ticks and 0 compares for fibonacci_heap