Lockless MPSC/SPMC/MPMC queues are not queues

> Acausality within consumers is the only upheld invariant: a consumer will not see any elements prior to the last element it has seen.

This is simply not true. A standard multi-consumer queue is ordered on the consumer side so long as consumers synchronize with each other. This could be as simple as one consumer setting a global flag after receiving message A and another consumer observing that flag before receiving message B. A lockless bag will not have this property.

Similarly, any of these queues have the nice property that, even if no one synchronizes anything, they’re fair: even under heavy load such that the queue never comes close to emptying, every push attempt will be fairly serviced by a pop without any other synchronization needed.

Attempting to relax either of these could be problematic, especially as a drop-in replacement of the data structure. I suspect that quite a lot of software that uses queues pushes special tokens to indicate changes of global state, and safety and correctness may be violated by reordering. For example, an MPMC system could have a producer push a special “I’m done” token when it’s all done, and the consumers could collectively count the “I’m done” tokens and assume (correctly on a standard MPMC queue) that no more messages will be in the queue once one “I’m done” per producer have been globally seen. If those tokens come out a bag too early, then a different synchronization mechanism would be needed.

The author has a point, but the global ordering of an MPMC queue is not entirely pointless. Assuming the queue marks the messages with the order, the ordering might be used at a later stage in the pipeline to reorder the processed messages and recover the total order.

Also there are implications for fairness. A queue implemented as a stack might means that messages pushed during a spike might never be processed or experience very high latency.

Finally it is actually possible to implement a decent lock free MPSC queue in top of a node-based stack: the consumer would pop all elements on one operation, then reverse the list. This N cost is amortized over N pops so it is actually not bad.

Imagine standing in line at the supermarket, or municipality, or anywhere where you stand in line.

The front of the line is near service desk 1. When it’s your turn, you have to walk to service desk 10. As you’re walking to it, service desk 1 frees up, and the person who was behind you in line walks to service desk 1. They arrive in seconds, while you’re still halfway to being served, a few meters away.

Op is pointing out that (programming) queues without locking lack a certain purity which is also lacking in real life queues.

If you want a exotic operation to make this better, then you would want a uninterruptible two-instruction sequence of: "atomic modify, then use old value as index for indexed store". So that would be a instruction with 4 parameters: memory location for atomic, atomic modify argument, base memory location for store, register value to store; and the instruction itself would encode the operation and store scale/stride. Importantly, the indexed store does not need to be atomic with respect to the first, it merely needs to be ordered after it with a guarantee that a context switch or interrupt can not result in partial completion. This is a much weaker requirement than making multiple cache-line loads/stores fully atomic with respect to each other.

Such a operation would improve multi-producer queues with fixed-size elements smaller than a word and would likely be fairly trivial to implement, merely requiring fusion of two existing instructions in a way that prevents interruption between them.

It's only terrible if it actually matters?

Also it doesn't look like you are using any of the optimized lockless implementations like crossfire/etc, so not sure what this actually proves?