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-08 03:21:28

Tim Blechmann wrote:
> hi thomas,
>
> reproduced and fixed the issue with the fibonacci heap ...
>
> tim

I now also included pairing_heap and skew_heap in the performance test. However, I get a segfault for pairing_heap when running the "Linear Forward" performance test. That's the place with "//   if (0)" in the attached file. When I uncomment that line, I get the following results (linux32):

Performance Check for Linear Forward
   270 ticks and 15952569 compares for TStaticHeap
   280 ticks and 15952569 compares for TStaticHeap
   100 ticks and 5495826 compares for TSequentialHeap
    80 ticks and 5495826 compares for TSequentialHeap
   470 ticks and 20929621 compares for b_heap
   470 ticks and 20929621 compares for b_heap
   400 ticks and 7012461 compares for binomial_heap
   420 ticks and 7012461 compares for binomial_heap
   300 ticks and 16164008 compares for d_ary_heap
   290 ticks and 16164008 compares for d_ary_heap
   210 ticks and 5637046 compares for fibonacci_heap
   220 ticks and 5637046 compares for fibonacci_heap
   850 ticks and 17013833 compares for skew_heap
   850 ticks and 17013833 compares for skew_heap

Performance Check for Linear Backward
   280 ticks and 22976046 compares for TStaticHeap
   260 ticks and 22976046 compares for TStaticHeap
   100 ticks and 5225203 compares for TSequentialHeap
    90 ticks and 5225203 compares for TSequentialHeap
   620 ticks and 31971032 compares for b_heap
   630 ticks and 31971032 compares for b_heap
   260 ticks and 5636875 compares for binomial_heap
   270 ticks and 5636875 compares for binomial_heap
   350 ticks and 19465560 compares for d_ary_heap
   350 ticks and 19465560 compares for d_ary_heap
   220 ticks and 5866500 compares for fibonacci_heap
   230 ticks and 5866500 compares for fibonacci_heap
   140 ticks and 458856 compares for pairing_heap
   150 ticks and 458856 compares for pairing_heap
   100 ticks and 458856 compares for skew_heap
   110 ticks and 458856 compares for skew_heap

Performance Check for March
  1590 ticks and 93489201 compares for TStaticHeap
  1560 ticks and 93489201 compares for TStaticHeap
   710 ticks and 53507489 compares for TSequentialHeap
   730 ticks and 53507489 compares for TSequentialHeap
  2550 ticks and 121120384 compares for b_heap
  2530 ticks and 121120384 compares for b_heap
  3400 ticks and 73639894 compares for binomial_heap
  3410 ticks and 73639894 compares for binomial_heap
  1620 ticks and 92667621 compares for d_ary_heap
  1590 ticks and 92667621 compares for d_ary_heap
  1250 ticks and 39902719 compares for fibonacci_heap
  1260 ticks and 39902719 compares for fibonacci_heap
  1910 ticks and 38838757 compares for pairing_heap
  1900 ticks and 38838757 compares for pairing_heap
  6380 ticks and 100758422 compares for skew_heap
  6380 ticks and 100758422 compares for skew_heap

What's impressive here is that pairing_heap and skew_heap have a compare count a factor 10 smaller than any other heap for the "Linear Backward" performance test.

Regards,
Thomas