- Author
- Nahla
- Published
- 10 July 2026
- Kind
- Personal blog post with a Rust design and throughput benchmarks
- Original
- nahla.dev/blog/waitfree_queue/
- Subject
- Systems and hardware
- Themes
- Close to the machine
What it is
Nahla built a queue to test their intuition about lock-free programming. The author claims no breakthrough and asks experts for feedback.
What it says
- A correction states that the queue is not wait-free after all.
- Producers and consumers take tickets from atomic counters and wait their turn on a slot.
- Each state entry packs a 63-bit reservation number and one turn bit.
- The design has no CAS loops, so waiting threads only read a shared slot.
- Dropping a drivable operation drives it to completion, or the slot stays disabled.
- The author says the queue lags in the one producer, one consumer case.
- The author reports an odd pattern where the equal-thread test peaks at N = 4.
What evidence it gives
The post gives throughput tables from a Criterion benchmark on one Ryzen 7 7800x3D machine. Each run moves 2^24 items. Source code and unit tests are in a linked repo. Results for other queues are not printed in the post.
Interests and limits
The author has no stated commercial interest. The post says an earlier version wrongly called the queue wait-free. The tests are synthetic and run on a single machine. Comparisons with other queues are not shown, and the author did not examine their internals. The post names a rare undefined behaviour risk at huge item counts. The waiting bound holds only while producers and consumers both keep running.
Connections
These links are this wiki's own reading, not claims the sources make.
- Linearizability! Refinement! Prophecy!. Nahla's post carries a correction: the queue is not wait-free after all. Hochstein walks through what proving a related property takes, on a small queue. Would a model have caught the slip sooner?