Girls Just Wanna Have Fast MPMC Queues with bounded waiting · Nahla

The Wayback Machine - http://web.archive.org/web/20260709172822/https://nahla.dev/blog/waitfree_queue/ Thu, Mar 12, 2026 Design Theory Reality Advantages Technical Limitations, Notable Behaviors Benchmarks Methodology Results Analysis/Conclusions Source Code

Disclaimer: An earlier version of this post claimed the structure is wait-free, this is incorrect. Being wait-free requires that failure or suspension of any thread can’t cause failure or suspension of another thread. This queue in fact does not fulfill that requirement. The main section which discusses the wait bounds of queue operations has been amended to reflect this, but other parts of this article have not been. As such there may parts of the text which refer to this as a wait-free queue, which it is not. I chose to keep those sections to avoid rewriting chunks of this post after it was already posted. Thanks for the correction Reddit user matthieum! After my last post I started working on writing a data structure to facilitate sharing a buffer mutably between multiple threads. One tangent lead to another and that lead to me getting really into lock-free data structures so I decided I wanted to make a wait-free queue. This thing seems decently fast to me and I’m proud of it so I figured its worth writing about it. I also wanted to 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 my intuition of lock-free/wait-free programming. To that end, I’ve kept cross-referencing of other works to a minimum, only going so far as to benchmark some other queue implementations* on my machine without peeking at their internals. I’m hoping to get some feedback from people who know 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 max0x7ba’s excellent atomic_queue repository.

It has a set of scripts and make files that made it very easy to get a solid collection of benchmarks for various popular queue implementations. Design Theory The queue works based off a ticket lock wait system. Imagine that there are two ticket dispensers, one for producers and one for consumers, as well as a set of N boxes next to each other that are labeled from 0 to N-1. Above each box is a display keeping track of whose turn it is, it shows a reservation number and a letter to indicate whether it is the consumer or producer’s turn. Each ticket will have two numbers printed on it, one is the box number, the other is the reservation number. The flow for either consumer or producer is simple: take a ticket from the appropriate dispenser, find the box with the number shown on the ticket and wait for the reservation number on the ticket to display above the box. Once the reservation number is displayed, one can perform the action 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 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 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 this system. For that, we will be using two AtomicUsize counters, one for producers and one for consumers, along with two ring buffers. One buffer (the “data” buffer) is used for actually passing items to/from the queue, and the other buffer (the “state” buffer) keeps track of who owns each entry in the data buffer. Here the counters are the ticket dispensers, the data buffer entries are 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 2 3 4/// A wait-free array-based bounded queue 5pub struct WFQueue<T, const N: usize> { 6 // NonNull pointers are used instead of boxes to avoid accidental dereferencing which can cause 7 // UB. Manual allocation is used to avoid accidental calling of drop on values that we no longer 8 // have ownership of which Box does on drop. 9 data: NonNull<[CachePadded<T>; N]>, 10 state: NonNull<[CachePadded<AtomicTicket>; N]>, 11 prod_reserve: CachePadded<AtomicUsize>, 12 cons_reserve: CachePadded<AtomicUsize>, 13}

Note: Unless otherwise specified, I assume a system with a usize type that is 8 bytes/64 bits. While the ideas here work regardless of the size of the system’s usize type, it is much easier to discuss when given a concrete size. Plus, saying things like “on a system with a usize type that is N bits, the lower N-1 bits are used for blah blah blah” gets old real fast and I’m lazy. The AtomicTicket type is a mere thin-wrapper around an AtomicUsize. AtomicTicket uses the least significant 63 bits to store a ticket/reservation number, and uses the most significant bit to represent the type of the ticket (consumer/producer). A state buffer entry’s value is interpreted to mean that whoever has the corresponding reservation number and ticket type has exclusive read/write privileges over the data buffer entry with the same index as the state buffer entry.

Note: since we use the most significant bit to store the status of the ticket (as described above). This means that reservation numbers would overflow at the \(2^{63}\) boundary rather than \(2^{64}\) Reservation numbers are produced by atomic counters when incremented by 1 using a fetch add. The state and data buffer indices, which the reservation number corresponds to, are obtained by taking the reservation number modulo N, with N being the size of the buffers.

However, as division/mod operations are expensive, we employ the common optimization of forcing the buffer size to be a power of 2. By forcing N to be a power of 2 we can use N - 1 as a bitwise mask so that for any integer x the following holds true: (x & (N - 1)) == x % N. In reality the “tickets” don’t have both a box number and a reservation number, the lower N bits of a reservation number give us the box number (state/data buffer index) which we obtain via the bitwise-and operation. The process for a producer to enqueue an item is as follows:

Increment the producer counter by 1 with a fetch add, storing the value from before the operation as the reservation number. Wait until the state buffer entry’s value corresponds to the reservation number (lower 63 bits only) and has a status bit value indicating that it is the producer’s turn. Store the desired value in the corresponding data buffer slot. Toggle the status bit in the state buffer’s entry to indicate that it is now the consumer’s turn on this slot.

And the process for a consumer to dequeue an item is:

Increment the consumer counter by 1 with a fetch add, storing the value from before the operation as the reservation number. Wait until the state buffer entry’s value corresponds to the reservation number (lower 63 bits only) and has a status bit value indicating that it is the consumer’s turn. Read the value from the corresponding ring buffer slot. Set the state buffer entry’s value to the reservation number reservation_number + N, and a status bit value indicating that it is the producer’s turn. Here reservation_number is the number obtained from step 1.

The figure below shows how one entry in the state buffer relates to its corresponding entry in the data buffer, as well as the breakdown of the state buffer’s bitfield.

1+---+---+---+-----+-------+-------+-------+ 2| 0 | 1 | 2 | ... | n - 3 | n - 2 | n - 1 | <-- data buffer 3+---+---+---+-----+-------+-------+-------+ 4 ^ ^ ^ ^ ^ ^ ^ Having the value that matches 5 | | | | | | | <-- a state buffer's entry implies 6 | | | | | | | ownership of the data buffer slot. 7+---+---+---+-----+-------+-------+-------+ 8| 0 | 1 | 2 | ... | n - 3 | n - 2 | n - 1 | <-- state buffer 9+---+---+---+-----+-------+-------+-------+ 10 / \ 11 / \ 12 / \ 13 +------------------------------+ 14 | 63 | 62:0 | 15 +------------+-----------------+ 16 | status_bit | reservation_num | 17 +------------+-----------------+ Advantages No CAS Loops, Minimal Cache Contention One big advantage of this system is the lack of CAS loops. Waiting for one’s turn by repeatedly reading from the state buffer allows for that slot’s cache to be kept under a shared state (assuming a MESI cache model), which minimizes contention. The ownership state only ever changes when an actor has finished their operation, in which case they write to the state buffer slot corresponding to the data buffer slot they operated on, advancing it to the next reservation number. Bounded Waiting Short of thread suspension or failure, any operation on this structure has an upper bound on the time that it may take. This means that we guarantee that no consumer or producer will experience starvation, and that all enqueue and dequeue operations will finish, eventually. This however, comes with the caveat that you must have both consumers and producers running, and that the upper bound does not account for waiting caused by OS thread suspension or some form of failure.

For example, if a queue is full, and has no consumers running, then no further enqueue operations can ever finish regardless of how long one waits. As the system is turn based through the reservation number ordering. The wait time for some type of actor (producer or consumer) is dependent on its position in the turn queue, and the number of active* actors of the opposite type. Take for example a queue with \(N = 64\). If we were to attempt to enqueue 128 items into it, the first 64 would enqueue with no delay. The subsequent 64 however would have to wait until the first 64 items are consumed. For the 128th enqueue operation, this means waiting until the 64th item is consumed. Due to the structure of the state buffer, there is an “early exit” condition of sorts. The 65th enqueue operation from this example would only have to wait for the first dequeue operation to finish as they both map to the first slot. In general, if our position in the queue is \(kN + l\) (where \(k \geq 0\) and \(0 \leq l < N\)) away from the start, then we will wait for \((\max(k - 1, 0) \cdot N) + kl\) operations. For the example from above, we were 65th in the queue. Substituting for \(k = 1\), \(l = 1\) and \(N = 64\), we can see that our predicted wait time was \(0 \cdot 64 + 1 \cdot 1 = 1\), which is exactly how many dequeue operations took place before it was our turn. This can be trivially shown to work the same way for consumers. Additionally, this cost will scale down linearly** with the number of actors of the opposite type as the waiting one. This means that the upper bound on our wait time can be expressed as \(((max(k - 1, 0) \cdot N) + kl) / j\) where \(j\) is how many active actors of the opposite type to our waiting one there are.

* Active is taken to mean an actor that is working on their operation.