RE: [boost] 'stable' priority queue

From: Geurt Vos (G.Vos_at_[hidden])
Date: 2001-04-18 04:11:19

> 
> Concerning the other question with respect to a newer version of the
> priority queues package: I haven't worked on this stuff since I have
> submitted an initial version. Actually, I haven't even pushed it
> through a review yet. If anybody is interested in taking this stuff
> over or to collaborate on the integration into Boost, I would really
> welcome any help with this! If you want me to do something, 
> push me :-)
> 

I will try to get them compiled for at least
BC++5.5 and VC++ 6. This is not necessarily
integrating stuff into boost. It's merely the
first step.

I already did some timing tests on Borland, 
with different implementations for stable
priority queues. In the test I only measured
the time it takes to push an element. 10
elements are pushed. The first 5 are unique,
the second 5 are equivalent to the 'middle'
item. 

When the elements are of type std::string,
and only the first char is the priority, then
std::multiset out-performs all other 
implementations. It's about 10-30% faster.

When the elements are of type int, I got some
astonishing results. 

1. boost::priority_queue is about 30% faster
than the std one and around 60% faster than
multiset. 

2. multiset is twice as fast as fibonacci_heap
(lazy_fibonacci_heap is slightly faster then 
fibonacci_heap).

3. multiset is around 25% faster than pairing_heap
and splay_heap.

didn't try d_heap because it doesn't compile...

One conclusing from this is that a priorty_queue
wrapper is less suitable for large objects, because
some copying is done (correct?).

Another: heaps are slower than multiset!

Geurt