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:

1. Increment the producer counter by 1 with a fetch add, storing the value from before the operation as the reservation number.
2. 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.
3. Store the desired value in the corresponding data buffer slot.
4. 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:

1. Increment the consumer counter by 1 with a fetch add, storing the value from before the operation as the reservation number.
2. 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.
3. Read the value from the corresponding ring buffer slot.
4. 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. As we’ll see later we do provide “drivable” operations. Such operations, if not driven periodically, will cause deadlock.

** Not accounting for cache contention and overhead created by multiple cores/thread accessing the same memory.

Minimize Head of Line Blocking

This implementation also minimizes head of line blocking by allowing consumers and producers to race ahead of each other. Due to the structure of the state buffer, a consumer, or producer, which experiences a slow down, will only impact their own slot. For example, if 2 producers were enqueuing items, and the first one slows down or temporarily hangs on the first enqueue operation, the second producer could still freely enqueue up to \(N - 1\) items* before being blocked. The second producer will only be blocked on the \(N\)th operation if the first producer’s enqueue hasn’t finished, or if it finished but the item hasn’t been consumed by a dequeue.

Similarly, if there were 2 consumers running and the first, for whatever reason, slows down or stops, then the other will remain unaffected, for \(N - 1\) operations*.

* We assume a completely empty queue for the producer’s case, and a completely full queue in the consumer’s case.

Drivable Enqueue/Dequeue Operations

By default an enqueue or dequeue operation will spin and wait until its turn, after which it will perform the desired operation. This isn’t always desirable. As an alternative, a drivable version of each operation is provided. The drivable version returns a struct which borrows from the queue and has one method, drive, that takes an argument, num_attempts, which is the number of times to attempt the operation before giving up and returning to the caller.

Since the effects of head of line blocking are minimized, it is possible to use this feature in an event loop or some other kind of async processing without heavily impacting other queue operations. The extent to which this may disrupt other queue operations of course varies depending on the amount of actors performing queue operations and the frequency of driving/polling.

Technical Limitations, Notable Behaviors

Possible (but Unlikely) Undefined Behavior

While the queue is designed to work even when integer overflow occurs, there is technically a risk of undefined behavior present. Long story short: Given a system with a usize type that is \(n\) bits large, if you attempt to enqueue \(2^{n-1} + 1\) items, and the first enqueue operation hasn’t finished by the time the last runs, there will be a race condition.

This occurs at the \(2^{n-1}\) boundary because, as mentioned earlier, we mask the highest bit of the reservation number and use it to indicate the ticket type. As such, the reservation number overflows earlier than a usize type normally would. This overflow causes the reservation number for the \(2^{n-1} + 1\) enqueue operation to be 0, the same as the number for the first operation. This triggers a race condition as both producers attempt a non-atomic write to the same memory address.

This problem is also relevant if the data type the queue is transmitting can’t be copied more than once. Dequeue operations are bitwise copies of data buffer entries, which for types such as a Box or Vec is problematic. The existence of two or more bitwise identical copies of such types could cause various errors and undefined behaviors such as double-frees and accessing invalid memory. As such, attempting to dequeue \(2^{n-1} + 1\) items all at once also risks a race condition between the first and last operation.

This behavior is obviously extremely unlikely. It would require spawning \(2^{n-1} + 1\) many threads and having them all attempt to enqueue at the same time, or creating \(2^{n-1} + 1\) drivable operations then proceed to drive the first and last operation at the same time.

For a systems where the usize type is 32 bits large, this would be a little over 2 billion items. Most systems these days however have a usize type that is 64 bits large. On such systems, you would need around 9.22 quintillion items to even have a chance at triggering this behavior.

Costly Drivable Operation Drops

A problem with the design of this structure is that dropping the drivable operation structs is not cheap. In fact, the drop operation simply drives the operation to completion. The state buffer only keeps track of who’s turn it is, and each producer/consumer only knows to wait until its turn before performing its operation and advancing the state buffer slot to the next consumer/producer. Thus drivable operation must wait until their turn to complete their operation and advance the state buffer slot lest the queue lock up.

This means that once one commits to performing an operation by incrementing either one of the counters, they must fully drive that operation to completion. Otherwise, that buffer slot becomes permanently disabled, and any subsequent operations which land on that spot will be stuck forever as they wait for the dropped operation to complete.

Benchmarks

Methodology

To test the throughput of this system, a synthetic benchmark was designed to measure the time it takes to enqueue and dequeue \(2^{24}\) items. The items are of type usize, which on my system has a size of 64 bits. The benchmark had three categories:

1. N consumers N producers, from N = 1 to N = 8.
2. 1 consumer N producers, from N = 2 to N = 15 producers.
3. 1 producer N consumers, from N = 2 to N = 15 consumers.

For cases 2 and 3 measuring N = 1 is obviously unnecessary as that is covered by case 1.

The criterion crate/framework was used for obtaining benchmark results, measurements were taken with a minimal number of programs running*. The system used to make the measurements has the following (relevant) specs:

CPU: Ryzen 7 7800x3D

Memory: 32GiB DDR5, factory overclocked to 6000 MT/s

Operation System: Fedora Linux 44, kernel 7.0.4

Rust version: Stable 1.95.0

* Restricted to system background processes/services, the Gnome desktop environment (ver. 50), and a terminal running the benchmark

Results

N Consumers N Producers

1 Producer, N Consumers

1 Consumer, N Producers

Analysis/Conclusions

Compared to other queues I’ve benchmarked, this queue’s performance seems to be pretty good. It does lag behind in the 1 consumer 1 producer case due to needing to manage the state buffer since it lacks a specialized implementation. However, as the number of consumers and producers starts to go up, it certainly seems to scale well. While the results I got from benchmarking other queues aren’t presented in this post, as comparison isn’t the point, they are still linked below as part of the repo in the “Source Code” section. The file will be titled atomic_queue_personal_results.txt for those wanting to cross reference those results with the tables from above.

There does exist a strange pattern in the N consumers N producers test where performance peaks at N = 4, sharply degrades, then slowly improves. I was originally under the impression that the reason behind performance dipping past N = 4 was due to the fact that my processor only has 8 physical cores. However, once I added the other two cases to my benchmark it became apparent that is not necessarily true as the performance peaks for either case occur when using all available logical cores. I believe that a different ratio of consumers to producers would yield greater maximum throughput than I found in my testing, but I’d like to set this project aside for now, so I’ll leave that for another day.

Source Code

The source code for my implementation, along with unit tests and benchmarking code can be found below.

https://github.com/nahla-nee/wfqueue