Re: [boost] [Heaps] benchmarks

Subject: Re: [boost] [Heaps] benchmarks
From: Phil Endecott (spam_from_boost_dev_at_[hidden])
Date: 2011-06-08 19:09:16

Tim Blechmann wrote:
>> it
>> would be great if the b_heap implementation performed no worse than the
>> "naive" version.
>
> it cannot: it uses a different tree structure than binary heaps, causing a 
> higher tree. with d-ary heaps, the arity is a tradeoff between tree height and 
> number of comparisons (higher arity, lower tree height but more comparisons). in 
> a similar manner, the b-heap adds a tradeoff between memory locality and tree 
> height ...
>
>
>> Also I've looked at your own benchmark graphs and it seems that there
>> is a fairly constant performance difference between the different heaps
>> - I don't see b_heaps getting faster than the alternatives as the queue
>> size increases.  
>
> maybe because my workstation has 8mb of cache

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.

Regards,  Phil.