
Boost : 
Subject: Re: [boost] [heap] A performance test and some questions
From: Thomas Klimpel (Thomas.Klimpel_at_[hidden])
Date: 20110607 15:15:45
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 (gcc4.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_heap449f378 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

gcc4.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
gcc4.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
gcc4.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
gcc4.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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk