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

Subject: Re: [boost] [heap] A performance test and some questions
From: Tim Blechmann (tim_at_[hidden])
Date: 2011-06-08 04:07:24

hi thomas,

> 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):

... the pairing heap is a self adjusting data structure ... and it is 
recursively implemented. there are some use cases, where the heap degenerates 
into a linear list ... the bigger problem is the fact that the heap is 
implemented recursively ... that means that in some cases you can run into a 
recursion of O(n) ...

in your example, your simply run into a stack overflow ... (there is a warning 
in the class reference about this issue)

> 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.

skep heaps have an amortized complexity for all operations. pairing heaps are 
difficult to analyze but give pretty good real-world results ...

cheers, tim