Re: [boost] Heaps and Queues for GSoC - stable priority queue?

Subject: Re: [boost] Heaps and Queues for GSoC - stable priority queue?
From: Cliff Green (cliffg_at_[hidden])
Date: 2010-03-20 12:07:43

>That's an interesting requirement. It may be the case that some of the more
>exotic heaps can be used to do something similar. This seems like it would
>be a good issue to address (and possibly solve) as part of a larger summer 
>project.

Cool! I was thinking the (relatively small) scope and domain (heaps and 
queues) fits well for a GSoC project.

The use cases where I've needed a stable priority queue have been networking 
related, but I'm sure there's other domains with similar use cases.

To reiterate, a stable priority queue maintains insertion order (FIFO) for 
entries with equal priority (std::priority_queue does not guarantee 
insertion order).

I've needed this to implement priorities for outgoing message queues, where 
higher priority messages get put at the front of the queue. But it's 
important that messages with similar priority maintain the insertion order. 
There's obvious ways to make this work by adding extra data (counter or time 
stamp), or by creating a different data structure (e.g. hash table of simple 
queues), but there's drawbacks to each of these approaches. A "native" 
stable priority queue would not add any memory or data structure overhead, 
at the cost (I'm assuming) of a slightly more complex internal tree or heap 
structure / ordering algorithm.

This "low memory overhead" is important because of both the "small" and 
"large" use cases. For example, an embedded system might need a simple 
stable priority queue that is lean and mean as possible. I'm currently 
looking at some CAN network related programming, and each device on the 
network is very limited in memory and processing power (the anticipated 
price point for the associated product is a few dollars). If I end up 
writing code for it, I'd love to be able to use Boost facilities as much as 
possible (I don't know the development environment yet, so don't know if it 
will be possible). On the other end of the use case scale, an outgoing queue 
might be in a large scale environment with gigs of memory, but the queue 
might need to have a large number of entries (e.g. millions). In this case, 
even a small bit of extra memory (e.g. an integer counter, as I've 
implemented in the past) has large costs.

BTW, I see this container as having the same interface as 
std::priority_queue, but with the additional ordering guarantee. I would 
assume a good name is boost::stable_priority_queue, but there may be other 
people with more experience with this kind of container that can suggest 
better alternatives.

Thanks, Andrew, and any GSoC participants that take this on.

Cliff