HN Debrief

Girls just wanna have fast MPMC queues with bounded waiting

  • Programming
  • Infrastructure
  • Open Source
  • Hardware

The post presents a bounded MPMC queue in Rust and tries to make the case for fast operations with bounded waiting. The important update is that the author later added a disclaimer: this queue is not actually wait-free, because a stalled thread can still prevent another thread from making progress. That correction shaped most of the useful discussion. People did not treat it as a minor terminology nit. They treated it as the central property that determines whether the design solves the class of problems the title seemed to promise.

If you are choosing a concurrent queue, stop treating terms like wait-free and lock-free as marketing shorthand and match the structure to the exact failure and latency behavior you need. For most production systems, mature Vyukov-style bounded MPMC queues still look like the practical baseline, with cache behavior and progress trade-offs doing more work than novelty.

Discussion mood

Interested but corrective. People liked the writeup and the public disclaimer, but the dominant reaction was that mislabeling a queue as wait-free is a serious category error, and that the useful takeaway is understanding progress guarantees, prior art, and cache trade-offs rather than celebrating a new algorithm.

Key insights

  1. 01

    Bounded queues force uncomfortable trade-offs

    Bounded capacity puts hard limits on what progress guarantees you can honestly claim. Slow consumers will eventually block producers when the queue fills, and combining multiple producers with global FIFO means an interrupted producer can hold up consumers unless the design gives up separate reserve and commit or accepts other hazards like fixed-size payload constraints and ABA handling. That frames the post correctly. The difficulty is not implementation polish, it is that the guarantee set is internally expensive and sometimes incompatible.

    Write down your required guarantees before you pick a queue. If bounded memory, global FIFO, and producer isolation are all on your wish list, expect to compromise or absorb much more algorithmic complexity.

      Attribution:
    • nly #1
    • tialaramex #1
  2. 02

    Vyukov-style MPMC is still the practical baseline

    The queue family behind rigtorp/MPMCQueue was treated as the benchmark this post has to be compared against. One commenter flatly said this was the best bounded MPMC queue they knew years ago and that there may not be much headroom left within descendants of the Vyukov cyclic queue design. That puts the blog post in context. It is exploring a mature design space, not opening a new one.

    Start your evaluation with established implementations like rigtorp/MPMCQueue instead of assuming a fresh writeup implies a better primitive. Benchmark against known-good queue families before investing in a custom variant.

      Attribution:
    • platinumrad #1
    • rigtorp #1
  3. 03

    Cache-line layout can dominate queue performance

    Per-slot contention is not just an abstract memory-model issue. Adjacent slots can false-share when multiple threads touch neighboring entries, which means the slot layout may matter as much as the enqueue algorithm. Padding each slot to a cache line removes false sharing and can preserve stream prefetching for simple traffic patterns. Bijective hashing spreads accesses out and reduces contention without the memory blowup, but then predictable sequential access is gone so the hardware prefetcher stops helping.

    Inspect slot layout and cache-line traffic before chasing algorithm changes. If your workload is hot enough for MPMC tuning to matter, test padded slots versus hashed indexing on real hardware.

      Attribution:
    • rigtorp #1
    • RossBencina #1
  4. 04

    Research queues exist but complexity wins the argument

    LCRQ and newer follow-on work that avoids double-width compare-and-swap show there is still movement in the literature. The reaction was still that low-complexity wait-free queues are basically a spent search space, and newer papers have not changed the practical rule that stronger guarantees come with real implementation cost. The cited 2022 and 2023 papers were offered as evidence that the frontier is alive, but not simple.

    If you need stronger progress guarantees than mainstream bounded MPMC queues provide, expect to read papers and absorb complexity. Do not promise your team a drop-in implementation that keeps the simplicity and portability of the common designs.

      Attribution:
    • gavinray #1
    • yxhuvud #1
    • duped #1
    • platinumrad #1

Against the grain

  1. 01

    Partial wait-freedom can still be useful

    Producer-side progress guarantees can be enough for some systems even when the queue as a whole is not wait-free. Aeron’s MPSC and MPMC structures were cited as designs where one producer cannot block another, and simple intrusive node-based algorithms can deliver similar behavior. That narrows the problem in a useful way. Sometimes the requirement is not universal wait-freedom, it is protecting producers from each other under contention.

    Specify progress guarantees per role, not just for the whole data structure. If your bottleneck is producer latency, a queue that isolates producers may solve the real problem without chasing full wait-freedom.

      Attribution:
    • nly #1

In plain english

Aeron ↩
A high-performance messaging and transport library used for low-latency systems.
bijective hashing ↩
A one-to-one mapping that scrambles indices so nearby logical positions are spread out in memory without collisions.
cache line ↩
The small fixed-size block of memory that a CPU cache loads and tracks as one unit.
false sharing ↩
Performance loss caused when different threads modify nearby data that sits on the same CPU cache line, forcing unnecessary cache synchronization.
FIFO ↩
First in, first out, meaning items come out of the queue in the same order they went in.
LCRQ ↩
Linked Concurrent Ring Queue, a high-performance concurrent queue algorithm from the research literature.
lock-free ↩
A concurrency guarantee that the system as a whole keeps making progress, even if individual operations may starve.
MPMC ↩
Multi-producer, multi-consumer, meaning multiple threads can both push items into the queue and pop items out.
MPSC ↩
Multi-producer, single-consumer, meaning multiple threads can push items but only one thread removes them.
stream prefetcher ↩
Hardware in modern CPUs that detects sequential memory access patterns and preloads future data into cache.
wait-free ↩
A concurrency guarantee that every operation completes in a bounded number of steps, even if other threads are delayed or stop running.

Reference links

Queue implementations and prior art

Papers on advanced concurrent queues

Corrections and related writeups