Lock-free queues for Nim. Bounded queues are ring buffers; unbounded queues are linked segments reclaimed via DEBRA. All variants cover SPSC, SPMC, MPSC, and MPMC.
API documentation: https://elijahr.github.io/lockfreequeues
If two threads need to hand items to each other and you cannot afford a mutex,
the answer is a lock-free queue. Picking the right one is the hard part: do you
have one producer or many, one consumer or many, a fixed capacity or not? Each
choice changes the algorithm and the cost. lockfreequeues ships eight queues
covering every cell of that grid, with a uniform API and verified ordering
guarantees.
A short vocabulary first.
- Wait-free: every thread completes its operation in a bounded number of steps, regardless of what other threads do. The strongest progress guarantee.
- Lock-free: at least one thread makes progress on every step. Individual threads may retry, but the system never stalls.
Wait-free is preferable when you can get it; lock-free is what you get with contended CAS loops. Both are stronger than mutex-based code, which can stall the whole system if a holder is preempted.
nimble install lockfreequeuesimport options
import lockfreequeues
# Bounded single-producer, single-consumer queue, capacity 16
var queue = initSipsic[16, int]()
discard queue.push(42)
discard queue.push(123)
let item = queue.pop() # some(42)
assert item == some(42)The simplest setup — the queue auto-creates a private DebraManager and
threads auto-register on first getProducer() / getConsumer() call:
import options
import lockfreequeues
var queue = newUnboundedMupmuc[64, int, 4]()
var producer = queue.getProducer()
var consumer = queue.getConsumer()
producer.push(42)
let item = consumer.pop() # some(42)
assert item == some(42)For multi-queue setups that share a manager, pass it explicitly. Threads
that touch multiple queues should also share a single ThreadHandle to
avoid burning a slot per queue:
import options
import debra
import lockfreequeues
var manager = initDebraManager[4]()
var queueA = newUnboundedMupmuc[64, int, 4](addr manager)
var queueB = newUnboundedMupmuc[64, int, 4](addr manager)
let handle = manager.registerThread()
var producer = queueA.getProducer(handle)
var consumer = queueB.getConsumer(handle)
producer.push(42)
let item = consumer.pop()See examples/ for full multi-threaded examples and patterns
(audio buffer, job scheduler, event collector, task fan-out).
| Queue | Producers | Consumers | Push | Pop |
|---|---|---|---|---|
Sipsic |
1 | 1 | wait-free | wait-free |
Sipmuc |
1 | many | wait-free | lock-free |
Mupsic |
many | 1 | lock-free | wait-free |
Mupmuc |
many | many | lock-free | lock-free |
Bounded queues are ring buffers with compile-time capacity. None require a DebraManager or per-thread handles.
| Queue | Producers | Consumers | Push | Pop | DebraManager |
Per-thread handle |
|---|---|---|---|---|---|---|
UnboundedSipsic |
1 | 1 | wait-free | wait-free | not needed | not needed |
UnboundedSipmuc |
1 | many | wait-free | lock-free | required | consumer side |
UnboundedMupsic |
many | 1 | lock-free | wait-free | required | producer side |
UnboundedMupmuc |
many | many | lock-free | lock-free | required | both |
UnboundedSipsic is special: with one producer and one consumer the consumer is the only thread freeing segments, so it does not need DEBRA. Every other unbounded variant does, because multiple threads can race to detach a segment.
Bounded queues are ring buffers with compile-time capacity. Use them when:
- memory usage must be predictable;
- you are working in embedded or real-time systems;
- producer and consumer counts are known at compile time.
Unbounded queues are linked segments that grow as needed. Use them when:
- workload is bursty or unpredictable;
- producer or consumer threads are created dynamically;
- some memory growth is acceptable in exchange for never blocking on a full queue.
debra>= 0.3.0for epoch-based reclamation in the unbounded multi-thread queues.nim-debrais a general-purpose DEBRA+ implementation; nothing about it is specific to this library, and it can be reused as the reclamation backend for any lock-free data structure you build.typestates>= 0.3.1for the slot-ownership state machines that back push and pop.
| Flag | Default | Effect |
|---|---|---|
-d:allowNonLockFreeQueueItems |
off | Disable the arc/orc compile-time check that rejects ref item types. |
-d:nimEnforceLockFreeAtomics |
off | Nim flag; fail compilation if any atomic operation falls back to spinlocks. |
-d:LockFreeQueuesAdvanceEvery=N |
64 | DEBRA epoch-advance cadence for unbounded queues' Eager reclamation per-pop fast path. |
By design, lockfreequeues rejects queues whose item type is ref T under arc, orc, or atomicArc. This is intentional: a queue holding ref items is not safe under our concurrency model.
Slots are stored in a plain array[S, T] and shared across threads. When a producer writes seg.data[i] = item and a consumer reads seg.data[i], those assignments fire Nim's =copy/=sink hooks for ref types, which mutate the refcount on the same object that other threads are reading or writing concurrently. That race exists regardless of whether the underlying refcount itself is atomic — arc's refcount is non-atomic, and even orc/atomicArc's atomic refcount can't make a torn read/write of the slot value safe.
Use a value type, a ptr T, or, if you accept the trade-off, compile with -d:allowNonLockFreeQueueItems to disable the check.
The full safety model — slot-ownership typestates, why the queue itself is lock-free even when items are not, and the matrix of MM x sanitiser combinations under CI — lives in docs/guide/safety-model.md. The typestate transitions are documented in docs/guide/slot-ownership-typestates.md.
The numbers below are a hand-curated summary of the four bounded
lockfreequeues variants on ubuntu-latest (4 vCPU, x86_64) at one
representative shape each. They are updated at release prep, NOT on
every devel push, and may lag the live data by up to one release
cycle. The "always-fresh" view lives at the chart page below.
Headline: Mupmuc (MPMC, bounded) sustains 18,209 ops/ms at 4p4c on
ubuntu-latest, against 1,723 ops/ms for Nim's stdlib Channel at the
same shape — about 10.6x faster under heavy multi-producer multi-consumer
contention.
| Variant | Topology | Shape | Throughput (ops/ms) | vs system/Channel (same shape) |
|---|---|---|---|---|
Sipsic |
SPSC | 1p1c | 7,592 | — (no SPSC Channel adapter) |
Sipmuc |
SPMC | 1p2c | 22,399 | — (no SPMC Channel adapter) |
Mupsic |
MPSC | 4p1c | 13,667 | 3.7x (3,667 ops/ms) |
Mupmuc |
MPMC | 4p4c | 18,209 | 10.6x (1,723 ops/ms) |
Numbers are pulled from docs/assets/bench-results/example.json, the
checked-in ubuntu-latest snapshot used as the chart's offline fallback.
Live updating chart: https://elijahr.github.io/lockfreequeues/latest/benchmarks/.
See benchmarks/ for the full suite, methodology, the
hand-curation procedure, and adapter implementations.
Examples are in examples/ and can be run with:
nimble examplesnimble testCI (see .github/workflows/build.yml) runs the
suite on:
- Runners:
ubuntu-24.04(x86_64),ubuntu-24.04-arm(native arm64),macos-latest(arm64). - Memory managers:
arc,orc,refc,atomicArc. - Backends: C and C++.
- Sanitisers: ThreadSanitizer (TSAN) on
atomicArc, AddressSanitizer (ASAN). - Lock-free atomic enforcement:
-d:nimEnforceLockFreeAtomicslane onarcandorc.
192 tests across the bounded, unbounded, threaded, and lock-free-check suites.
Pull requests and issues welcome. See CONTRIBUTING.md for the contribution workflow.
See CHANGELOG.md. The current release is 3.2.0.
- Juho Snellman, "I've been writing ring buffers wrong all these years" (alt).
- Mamy Ratsimbazafy, research on SPSC channels for weave.
- Henrique F. Bucher, "Yes, You Have Been Writing SPSC Queues Wrong Your Entire Life" (alt).
- Maged M. Michael and Michael L. Scott, "Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms" (PODC 1996).
- Dmitry Vyukov's writings on bounded MPMC ring buffers and CAS-based coordination patterns.
- Trevor Brown, "Reclaiming Memory for Lock-Free Data Structures: There has to be a Better Way" (DEBRA, the reclamation scheme used by the unbounded queues).
Many thanks to Mamy Ratsimbazafy for reviewing the initial release and offering suggestions.
MIT — see LICENSE.