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

Subject: Re: [boost] [heap] A performance test and some questions
From: Thomas Klimpel (Thomas.Klimpel_at_[hidden])
Date: 2011-06-07 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 (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