Lockless queue - sorting?

1) what is the reason for the sorting? maybe there is overall a better design.
2) can you just:

while ( 1 ){msg = popcheck timestamp ( msg )if ( timestamp < X ){   Process msg   break}else   discard? or pushback msg}

The objects in the queue are units of a biological simulation meant to be processed at a certain frequency, hence the timestamp. I've got a number of worker threads that pull these units off the queue and process them, placing them back on the queue to be next processed at prev_time + frequency^-1. The idea is to get scalability, since there could be anywhere between 10 and 10,000 items within this queue. Having each object in its own thread isn't practical (as we found when we implemented that avenue in RTAI - realtime linux). More cores = more worker threads, and having a general queue can keep idle cores and context switching to a minimum.

Sorting the queue is required to ensure that no starvation occurs for the units that need to operate at high frequencies. While that approach will work well when there are few units, as you increase the number of units you increase the risk of taking more time to go through the entire queue and processing units that take a lot of CPU time than the time between 1/Hz.

It definitely sounds to me like you should be using a heap, NOT a list. In fact, the other name for a heap is a priority queue, and you're even using the term 'queue' in describing this, and your items are certainly not FIFO, therefore a priority queue (a heap) is exactly what you're after.
Heaps are great for this because:

They have zero per-item overhead.
The lowest timestamped item can be removed in O(log n) time.
An item can be inserted back into the heap in O(log n) time.
No sorting step is required.

Even with locking, this should be plenty fast enough for 10000 items!

Since you're using C++, using heaps is dead-easy. The SC++L provides functions make_heap, push_heap, and pop_heap, or you can just use the priority_queue adapter and it's even easier. Take a look here, and here for example, and let us know if you need a hand using them.

Knowing which operating system you're targeting would help, btw. For example if you're targeting Windows, then you should be using a more lightweight type of a lock called a "critical section", whereas a mutex might be the right thing if you're using linux.

Perfect!

That's exactly what I'm looking for! Helps out with the sorting issue: you don't need to, hence less cpu time in the critical section, and elps out with the insertion/deletion times. I'll look into other forms locking. The program is supposed to be multiplatform, but I have no problem doing platform-dependent "#define"s to eek out performance for platform-specific things.

Sorry for the delay, I got ahead of myself and actually implemented it. Switching to a critical section, heap, and building all the code in release mode (the STL is quite slow in debug mode) and it looks like it helped significantly.

Thanks!

If I'm reading that right, then having one queue per frequency of update sounds like it could speed it up even more, as long as there's a reasonable quantity of things with that share update frequencies. That way you either update the whole queue, or don't update it at all at each time step, and no sorting is needed within the queues.

For example lets say you have both a 1Hz queue and a 3Hz queue. The update goes something like:

Uppdate3Hz();

Uppdate3Hz();

Uppdate3Hz();
Uppdate1Hz();

Uppdate3Hz();

Uppdate3Hz();

Uppdate3Hz();
Uppdate1Hz();

Quote:

Original post by skyfire360 That's exactly what I'm looking for! Helps out with the sorting issue: you don't need to, hence less cpu time in the critical section, and elps out with the insertion/deletion times. I'll look into other forms locking. The program is supposed to be multiplatform, but I have no problem doing platform-dependent "#define"s to eek out performance for platform-specific things.

If you want scalability, you need a way to avoid locks altogether.

Right now, you are not guaranteed proper ordering. An event with higher priority may get processed before event with lower priority, since you don't keep track of events currently being processed.

For example, let's say you have two items I1(3Hz) and I2(1Hz). Each time I2 gets updated, I1 must be updated 3 times.

But if you have 2 worker threads, T1 takes off I1, and T2, knowing nothing about other items, must process I2. So they are updated at same rate.

There's two question that are relevant to this:
- Do you need strict ordering?
- Does frequency of individual items change?

Let's not forget that the standard C++ library contains std::priority_queue, which maintains a heap on top of the container it's adapting (by default vector, but does support other random access containers like deque). See 23.2.3.2 in the standard.