Re: [boost] [Heaps] benchmarks

Subject: Re: [boost] [Heaps] benchmarks
From: Tim Blechmann (tim_at_[hidden])
Date: 2011-06-09 03:58:51

> > Tim, you're proposing this b-heap purely as a performance optimisation
> > compared to the "traditional" heap, but we've not yet seen any cases
> > where it is actually faster.  If it can be faster we need to see some
> > examples, and the documentation should qualify when it can be expected
> > to be better. If it's not faster, it should be dropped.
> 
> I don't think removal would be the right solution, but it certainly
> shouldn't be recommended as a best choice. Part of what I like about
> this library is that it provides a framework for evaluating
> comparative heap performance. While it doesn't appear to perform as
> well now, it's possible that future architectures may be more amenable
> to b-heap implementations. If not, then Boost has an implementation
> that can be used to empirically demonstrate otherwise.

i read somewhere that binary heaps are usually the first and the last answer 
when choosing a heap data structure ... although they have an amortized 
complexity of O(log(n)) for most operations.

> The same argument can probably be made for binomial heaps and fibonacci
> heaps.

binomial heaps implement most operations in O(log(n)) worst-case and are 
efficiently mergable ...
fibonacci heaps are of interest, since the support `push' and `merge' in O(1) 
amortized complexity (at the cost of implementing some operations in O(n) worst-
case complexity)

so the selection of the best heap data structure is really dependent on:

* the type (efficiency of std::swap and comparison like std::less)

* the size of the problem (for small sizes you do not need to care about the 
amortized complexity so much)

* is the program focussed on throughput or worst-case latency

* the use case: different access patterns have different performance 
characteristics.

so instead of telling the people to `use this', i prefer to give people a choice 
to select the best data structure for their applications

tim