Lockless MPSC/SPMC/MPMC queues are not queues

Summary

Lockless queues let multiple cores communicate with each other without mutexes, typically to move work around for parallel processing. They come in four variants: {single,multi}-producer {single,multi}-consumer. A producer gives data to a consumer, each of which can be limited to a single thread (i.e. a single-{producer,consumer}) or shared across multiple threads. But only the single-producer single-consumer (SPSC) queue is actually a queue!This article is part of a series building Lockness, a high-performance blocking task executor.SPMC/MPMC queues are broken Consider the so-called SPMC queue. By definition, received messages cannot be processed in a total global order without additional external synchronization. First, the single, ordered input stream is arbitrarily split amongst each consumer. Then, each message is removed from the queue in the same order. But from this moment onwards, the consumer thread can be paused at any moment (even within the library implementation that is still copying the data into your code). Consequently, another thread can process an element from the future before your code has even had a chance to see that it claimed an element, now from the past.Acausality within consumers is the only upheld invariant: a consumer will not see any elements prior to the last element it has seen. This guarantee is almost certainly too weak to be useful as consumers have no control over which set of elements are seen, meaning arbitrary elements from the future may have been processed on other threads.An example SPMC queue where element B is processed on thread 2 acausally before A on thread 1Similar logic applies to MPMC channels with the additional weakening that different producer streams are processed in no particular order. To work around this, some implementations use many SPMC channels to make a MPMC channel. They introduce the concept of a token which lets consumers optionally choose a specific producer to consume. Were this token to guarantee e...