Lockless MPSC/SPMC/MPMC queues are not queues

The blog post gatekeeps the definition of "queue" to require a global processing order, (not just merely global dequeue order following the FIFO principle) when the vast majority of real life queues have no such constraint whatsoever.

If you go to the the city hall and they have multiple counters, you pull a ticket with your number. There is a global order of dequeue operations. The first person to pull a ticket will be the first to be assigned to a counter. If there is one counter, the second person has to wait for the first person. If there are two counters, then the second person can go to the second counter. If the second counter works faster than the first counter, then the third person will go to the second counter.

According to the blog post this violates a global processing order constraint (created by who?). The people at the second counter appear to be coming from the future from the perspective of a global processing order constraint.

This is a very strange way to look at queues, because the primary purpose of a queue is to temporarily buffer data when there is insufficient capacity to process incoming requests. Calling something broken because it fulfills its purpose is a very negative way to approach life.

As other comments note there are plenty of problems restricting queues to ordered execution. For most use cases that simply does not matter. What matters are related features like avoidance of starvation or execution bias. And those are perfectly possible to do with multiple consumers/producers.

> Lockless queues are slow

That particular implementation of a lockless queue may be slow, but that is not globally true for lockless queues. There are variants, for example BBQ, https://www.usenix.org/conference/atc22/presentation/wang-ji..., that have great performance.

Ignoring all the other problems with this article that have been pointed out around definitions, it also claims that lockless is slow anyway. Without giving literally any data.

Good news: it's not slow

Let's take rust, which has an oddly thriving ecosystem of lockless mpsc/mpmc/etc queues, and lots of benchmarks of them in lots of configurations.

The fastest ones easily do at least 30 million elements/second in most configurations. The "slowest" around 5-10.

So the fastest is doing 33ns per element and the slowest is 100ns.

Which is probably why the article offers no data. It's not actually slow. It's actually really fast when done well.

I don't know what others are reading.

The article basically says that when you have multiple suppliers or consumers, the "order" of the queue loses meaning. It turns into an "unordered" pool of data. Therefore focus should be shifted from maintain a "queue of data" to a "bag of data".

I took the article to be saying that mpmc queues are not queues so we can use bags instead because bags are faster. The second claim seems dubious to me though. I checked out the repo which led me to https://alexsaveau.dev/blog/opinions/performance/lockness/at... which proposes new CPU instructions to create atomic bitmasks. As the author notes, the bag structure breaks down a bit because you have to operate on the bit mask with atomic operations which will contend heavily with each other.