RE: [boost] 'stable' priority queue

From: Harry Erwin (harry.erwin_at_[hidden])
Date: 2001-04-18 05:18:06

>  >
>>  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
>

It probably depends on the detailed implementation of the STL heap 
algorithms for your compiler. Moving things around in the underlying 
data structure should use swap, but is more likely to just use the 
raw operator=(const T&) and temporaries. If operator=() is written 
correctly, it will _also_ use temporaries, and you can see where that 
heads.

-- 
---
Harry Erwin, PhD, Senior Lecturer of Computing, University of 
Sunderland. Computational neuroscientist modeling bat bioacoustics 
and behavior. <http://world.std.com/~herwin>