Re: [boost] Dietmar Kuehl

From: Herve Bronnimann (hbr_at_[hidden])
Date: 2002-05-23 21:42:06

On Fri, May 24, 2002 at 01:39:00AM +0200, Dietmar Kuehl wrote:
> The difference in terms of performance is, however, probably not due
> to the use of inferior allocators but rather to the more involved
> maintenance of the objects: The need to identify the objects whose
> key is to be modified basically means that they have to stay in place
> in one form or the other. This in turn means that you have to modify
> several pointer when rearranging the heap.

Absolutely. Sometimes the (asymptotically) inferior structures are
better. A student implemented optimum branching in the BGL (this'll be
released very soon) and we used both fib. heaps with efficient merging and
array-heaps with trivial merging (pop out of one, push into the other).
The difference: 12s (fib) vs 3s (array).

Or perhaps it is that the asymptotic analysis is not exact enough...
or it's simply the constant factors.

> The node based heaps would probably benefit from a fast allocator, eg.
> one for a fixed small size of objects drawn from a pre-allocated arary,
> but I wouldn't expect a performance improvement of more than 10%. I
> haven't measured the difference, however. Maybe I'm wrong and the major
> time consumer is indeed the allocation...

Again, right. Red black trees from the SGI STL, with
boost::fast_pool_allocator or with std::allocator, have a difference of
less than 3% when constructed by repeated insertion. Before you see a
real difference, you're already running against secondary memory...
-- 
Hervé