Girls Just Wanna Have Fast MPMC Queues with Bounded Waiting

By Nahla | March 12, 2026

Disclaimer: An earlier iteration of this article described this structure as wait-free. This was inaccurate. To be truly wait-free, the failure or suspension of any single thread must not impede the progress of any other thread. While I have updated the section regarding wait bounds, some legacy references to "wait-free" may remain to avoid a total rewrite of the original text.

---

Introduction

Following my previous post, I embarked on a project to create a data structure that allows multiple threads to share a mutable buffer. This journey led me down a rabbit hole of lock-free programming, eventually sparking a desire to implement a wait-free bounded-waiting queue.

I'm quite pleased with the resulting performance and felt it was worth documenting. After the "novella" length of my last entry, I wanted this piece to be short and sweet.

To be clear: I am not claiming this is a groundbreaking discovery. Rather, this is an exercise in testing my own intuition regarding lock-free and wait-free concurrency. Consequently, I've kept external citations to a minimum. I did, however, benchmark my implementation against other queues using max0x7ba's atomic_queue repository, which provided a streamlined way to gather data on popular implementations.

I welcome feedback from concurrency experts!

---

Design Theory

The core logic of this queue mimics a ticket lock system.

The Analogy

Imagine a system with:

1. Two ticket dispensers (one for Producers, one for Consumers).
2. $N$ numbered boxes (indexed $0$ to $N-1$).
3. A display above each box showing a reservation number and a letter (P for Producer, C for Consumer).

Each ticket issued contains two pieces of information: the box number and the reservation number.

The Operational Flow:

• Step 1: Grab a ticket from your respective dispenser.
• Step 2: Locate the box matching the number on your ticket.
• Step 3: Wait until the display above that box matches your reservation number and type.
• Step 4: Perform the action (Producer $\rightarrow$ place item; Consumer $\rightarrow$ remove item).

The Invariant

The system ensures that for any specific box:

• It begins in an empty state.
• The first authorized access must be a Producer.
• Access types must strictly alternate (e.g., $P \rightarrow C \rightarrow P \rightarrow C$).

This guarantee ensures producers never overwrite data and consumers never read from an empty box.

---

Reality: Implementation

To translate this theory into code, we utilize two AtomicUsize counters and two ring buffers.

The Data Structure

The implementation uses NonNull pointers to prevent accidental dereferencing (which could lead to Undefined Behavior) and manual allocation to avoid drop being called on values we no longer own.

// Cache padding is utilized to prevent "false sharing" across CPU cores
pub struct WFQueue<T, const N: usize> {
    // NonNull pointers avoid accidental dereferencing and UB
    data: NonNull<[CachePadded<T>; N]>, 
    state: NonNull<[CachePadded<AtomicTicket>; N]>,
    prod_reserve: CachePadded<AtomicUsize>,
    cons_reserve: CachePadded<AtomicUsize>,
}

Technical Specifications

Assuming a system where usize is 8 bytes (64 bits).

The AtomicTicket is a wrapper around an AtomicUsize. It uses a bit-packing strategy to store both the ticket type and the sequence number:

1. The Most Significant Bit (MSB): Indicates the ticket type (Producer vs. Consumer).
2. The Lower 63 Bits: Store the actual reservation number.

Implications of this layout:

• Overflow: Reservation numbers wrap around at the $2^{63}$ boundary rather than $2^{64}$.
• Generation: Numbers are generated via fetch_add(1, Ordering::...).

Indexing and Optimization

To find the correct buffer index, we calculate the reservation number modulo $N$: $\text{index} = \text{reservation\_number} \pmod N$

Since division and modulo operations are computationally expensive, we enforce a constraint: $N$ must be a power of 2. This allows us to replace the modulo operation with a bitwise AND mask: index = reservation_number & (N - 1)

Figure 1: Conceptual mapping between the state buffer and data buffer.