Girls Just Wanna Have Fast MPMC Queues with bounded waiting · Nahla
Nahla
hi there ^~^
© 2026. All rights reserved.
Girls Just Wanna Have Fast MPMC Queues with bounded waiting
Thu, Mar 12, 2026
Disclaimer: An earlier version of this post claimed the structure is wait-free, this is incorrect.<br>Being wait-free requires that failure or suspension of any thread can’t cause failure or<br>suspension of another thread. This queue in fact does not fulfill that requirement. The main<br>section which discusses the wait bounds of queue operations has been amended to reflect this, but<br>other parts of this article have not been. As such there may parts of the text which refer to this<br>as a wait-free queue, which it is not. I chose to keep those sections to avoid rewriting chunks<br>of this post after it was already posted.<br>Thanks for the correction Reddit user matthieum!
After my last post I started working on writing a data structure to facilitate sharing a buffer<br>mutably between multiple threads. One tangent lead to another and that lead to me getting really<br>into lock-free data structures so I decided I wanted to make a wait-free queue. This thing seems<br>decently fast to me and I’m proud of it so I figured its worth writing about it. I also wanted to<br>write something short and sweet after the novella that was my last post.
To be clear, I am not claiming this data structure is ground-breaking in any way. This is me testing<br>my intuition of lock-free/wait-free programming. To that end, I’ve kept cross-referencing of other<br>works to a minimum, only going so far as to benchmark some other queue implementations* on my<br>machine without peeking at their internals. I’m hoping to get some feedback from people who know<br>more about this stuff than me, so if that’s you, please feel to give your thoughts!
* When ever I mention benchmarks for “other queues” I’m referencing benchmarks I got through<br>max0x7ba’s excellent atomic_queue repository. It has a<br>set of scripts and make files that made it very easy to get a solid collection of benchmarks for<br>various popular queue implementations.
Design
Theory
The queue works based off a ticket lock wait system. Imagine that there are two ticket dispensers,<br>one for producers and one for consumers, as well as a set of N boxes next to each other that are<br>labeled from 0 to N-1. Above each box is a display keeping track of whose turn it is, it shows a<br>reservation number and a letter to indicate whether it is the consumer or producer’s turn. Each<br>ticket will have two numbers printed on it, one is the box number, the other is the reservation<br>number.
The flow for either consumer or producer is simple: take a ticket from the appropriate dispenser,<br>find the box with the number shown on the ticket and wait for the reservation number on the ticket<br>to display above the box. Once the reservation number is displayed, one can perform the action<br>permitted by their ticket, either taking (consuming), or placing (producing) an item.
It’s worth noting that the reservation system here would ensure that for any one box the following<br>holds true:
The box starts off being empty
The first ticket called is a producer’s ticket number
The same ticket type is never called twice in a row (e.g. producer followed by producer).
This ensures that producers always have an empty box to place an item into, and consumers always<br>have a full box from which they can take an item out of.
Reality
While that is all nice in theory, we need to step back down to the real world and actually implement<br>this system. For that, we will be using two AtomicUsize counters, one for producers and one for<br>consumers, along with two ring buffers. One buffer (the “data” buffer) is used for actually passing<br>items to/from the queue, and the other buffer (the “state” buffer) keeps track of who owns each<br>entry in the data buffer. Here the counters are the ticket dispensers, the data buffer entries are<br>the boxes, and the state buffer entries are the displays atop each box.
The struct we will be working with looks like this:
1// cache padding added to prevent false sharing<br>4/// A wait-free array-based bounded queue<br>5pub struct WFQueueT, const N: usize> {<br>6 // NonNull pointers are used instead of boxes to avoid accidental dereferencing which can cause<br>7 // UB. Manual allocation is used to avoid accidental calling of drop on values that we no longer<br>8 // have ownership of which Box does on drop.<br>9 data: NonNull[CachePaddedT>; N]>,<br>10 state: NonNull[CachePaddedAtomicTicket>; N]>,<br>11 prod_reserve: CachePaddedAtomicUsize>,<br>12 cons_reserve: CachePaddedAtomicUsize>,<br>13}
Note: Unless otherwise specified, I assume a system with a usize type that is 8 bytes/64 bits.<br>While the ideas here work regardless of the size of the system’s usize type, it is much easier<br>to discuss when given a concrete size. Plus, saying things like “on a system with a...