Most efficient way to make a general-purpose queue


#1

I need to make a queue of (pointers or references to) objects that need processing. The objects are owned by other data structures so I don't want the queue to delete them. I don't need to store any other information, just which objects.

 

If I make a "Queue" class, is there any more efficient way to do it than with Array<ObjectType*>, with Array::ensureStorageAllocated() set sufficiently large? I'm assuming I don't want to be removing items, since that will shift everything, but replacing them with nullptrs, and keeping my own queue head and tail variables. Is there a better way?


#2

Everything happening on the same thread?   FIFO processing?  Performance or clarity more important?

Maybe look at: 

std::queue<ObjectType *> 

Good summary here: 

https://stackoverflow.com/questions/1262808/which-stl-container-should-i-use-for-a-fifo

Have you tried it with Array<ObjectType *> and decided it's too slow? 


#3

Yes, the queue itself will only be accessed by one thread, though the objects pointed to may be changed by other threads--I'm assuming that's not a problem (as long as they're not being deleted). Yes, only FIFO, no insertions in the middle. Performance most important, up to several thousand pushes/pops per frame at 30 fps. Since the contents are only pointers, I may end up just having it allocate memory on initialization to hold the worst case of all objects possible--even 10,000 pointers should still be 40kB or 80kB--then it won't ever have to move data around at runtime.

I didn't try anything yet, but I'll have a shot with std::deque<ObjectType*>. The reason I asked is (as a Juce newbie) I didn't know what standard classes we should stay away from, since Juce redoes so many of them. My code has to be portable, at least among the three desktop OSes.


#4

If you can work with a fixed sized buffer then I wonder if using a fixed memory size circular buffer is actually going to be the fastest possible solution.  You could look at AbstractFIFO from the JUCE classes.

(Modern processes seem to make the most direct approach as fast as faffing around with fancy optimisations, but if you made memory buffer a power-of-two big, there's probably a way of doing the FIFO without the comparison for overflow.  However - probably not needed.)