Jump to content
  • Advertisement
Sign in to follow this  

Thoughts on which priority queue I need

This topic is 2807 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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
Sign in to follow this  

  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!