Performance of Priority Queues

[Jan]

Hi there

Does anyone know how well STL priority-queues behave? At the moment i use them in a performance critical piece of code and would like to know, if that's a good idea.
The queue will most certainly hold a few hundred, maybe even thousand entries (each ~40 bytes) and the queue will be emptied and refilled very fast.

I didn't find a function to reserve memory for a priority-queue, therefore i fear, that the queue will allocate and free memory like mad.

I was thinking about using a vector instead and sort the array once, after all insertions were made, just before accessing the entries. Though that has other disadvantages.

Any ideas are very welcome,
Jan.

[Nils Pipenbrinck]

I didn't find a function to reserve memory for a priority-queue, therefore i fear, that the queue will allocate and free memory like mad.

Good question. Yes, STL will allocate like mad, and it will spend more time in the allocator than in the seraches/inserts/deletes.

STL provides a mechanism to overload the allocator of any container. Use that, and pool like mad. You can access/use it as a template argument (others - please chime in. I've never used them myself).

Also, you can as well roll your own priority queue if you only use them for one type or two. Theses aren't that difficult to implement and you have full control / no guessing over the allocation traversal behaviour. You might be surprised how fast a simple sorted array of something combined with binary search can be.

[CobraLionz]

The best way to find out is just to do it. Testing this would only take 5 lines of code.

Hi there

Does anyone know how well STL priority-queues behave? At the moment i use them in a performance critical piece of code and would like to know, if that's a good idea.
The queue will most certainly hold a few hundred, maybe even thousand entries (each ~40 bytes) and the queue will be emptied and refilled very fast.

I didn't find a function to reserve memory for a priority-queue, therefore i fear, that the queue will allocate and free memory like mad.

I was thinking about using a vector instead and sort the array once, after all insertions were made, just before accessing the entries. Though that has other disadvantages.

Any ideas are very welcome,
Jan.

[Jan]

I DID implement it. But since i am at the very beginning of this part of the project, the usage of it is only experimental, with only a few objects.

Also, i would need to profile it, or so, to really find out, if there is a big impact. And MAYBE someone already knows this...

[bladder]

STL provides a mechanism to overload the allocator of any container. Use that, and pool like mad. You can access/use it as a template argument (others - please chime in. I've never used them myself).

I would suggest looking into boost.pool (http://www.boost.org/libs/pool/doc/). It has a standard compliant allocator (http://www.boost.org/libs/pool/doc/interfaces/pool_alloc.html) that you can supply to the stl containers.


#include <queue>
#include <boost/pool/pool_alloc.hpp>


struct Object
{
int i;
std::string str;
float x;
};

typedef boost::pool_allocator<Object> object_allocator;


void main()
{
std::priority_queue< Object, std::vector< Object, object_allocator > > q;
}