Sign in to follow this  

Thoughts on which priority queue I need

Recommended Posts

Hi all,

I'm currently working on a project that requires me to use/implement a priority queue. Its a server-side rendering engine that receives requests of various types (one of them is a render request) and returns relevant data (or images).

One of its aspects is its main loop which is drived by a queue. The queue can be filled with all kinds (not *too* many) of events, some may be new requests and some are internal. The queue needs to be thread-safe and prioritized.

Why prioritized ? Since some events may be more important than others in some contexts. For example, at the beginning the server loads up a group of images (its a medical imaging application so these are DICOM images), on the order of ~1000 for the average case. The minimum can be even 1 and the maximum can be 10000 or so.

The events that signal loading of those images will arrive at the queue but at the same time, more important events for rendering of images may need to be added to the queue and in order to finish the rendering it would be a better idea to handle all events relevant for rendering before continuing with the "load" operation.

Now, the typical scenario using the queue is:

1. first time, the server receives many events at a rapid pace.
2. after these are handled, the queue will mostly contain a very few number of events for the duration of the session.

Up until now I could get away with using ACE's Ace_Message_Queue_Ex which is template based and provides thread-safe access. Also, it will block if I try to
dequeue when the queue is empty. Perfect.

It just isn't priorizied and using ACE's dynamic queue is annoying because its semantics aren't well suited to the task.

I considered using std's priority_queue but I'm concerned with:

1. The allocation of memory in the extreme cases of ~10000 events at the very beginning, if the underlying container is a vector as it has an exponential allocation strategy.

2. When the queue will fill with those ~10000, with a priority_queue that provides only amortized O(logn) complexity, the cost of adding another item may be high.

All this assuming I handle the thread-safety, which is fairly trivial.

I also contemplated using an array of deque/lists. An array of arrays of sorts. The priority can be used to access the relevant "bin" in O(1) and both these containers allow O(1) insertion and removal at their ends. std deque behaves better than list though, if I need to add 1 event and then remove it and it manages its memory using blocks of contiguous memory so there won't be constant allocations and deallocations except for the initial workload.

It is true that implementing an array of deques as a priority queue may be inflexible because the amount of keys is finite and small, but that isn't a real concern actually. That number can also be a template argument.

Any thoughts are welcome.

Share this post

Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this