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-06 03:44:15

hi thomas,

> 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. And "fibonacci_heap" seems to be the fastest heap
> from Boost.Heap in this performance test, while TStaticHeap is still a
> factor two slower than the tuned TSequentialHeap.

i breefly looked into your heap implementation and it seems to follow a 
different design than boost.heap ... actually more similar to the implementation 
of the heaps that are currently used in bgl. this probably explains the 
performance difference.

> I guess the problem here is that I found no way around using
> "std::pair<value_type, value_type*>" as value_type for the heap, because I
> need to know the position in the bulk of the point with the smallest
> arrival time. But Dijkstra algorithm should be no different, I have to
> know the vertex in the graph with the shortest path.

you mean std::pair<value_type, handle_type> in order to store the handle inside? 
this may be a hole in the API. at the moment it is possible to convert an 
iterator to a handle (s_handle_from_iterator), so possibly i should add an 
handle_type s_handle_from_reference(reference); to all mutable heaps ...

> Independent of this, I also have a totally different question. There is a
> FIXME in line 233 of the test program, and if the following line is
> commented out, fibonacci_heap shows undefined behavior, ranging from
> segmentation fault to failing the Sanity Check. Here is the code
> surrounding the FIXME:

will have a look, what is going wrong here ...

tim