Skip to content

lockfreequeues

Lock-free queues for Nim, implemented as ring buffers (bounded) and linked segments (unbounded).

Overview

v5 exposes two unified, cardinality-parameterized queue types — BQueue (bounded) and Queue (unbounded). Each covers all four producer/consumer combinations, selected at compile time via the ccProd / ccCons parameters.

Bounded BQueue (Fixed Capacity)

Ring buffer with compile-time capacity. Best for predictable memory usage and embedded systems. BQueue covers:

Cardinality Producers Consumers Push Pop
SPSC Single Single Wait-free Wait-free
SPMC Single Multiple Wait-free Lock-free
MPSC Multiple Single Lock-free Wait-free
MPMC Multiple Multiple Lock-free Lock-free

Unbounded Queue (Dynamic Capacity)

Linked segments that grow as needed. The MP/MC shapes use DEBRA+ epoch-based reclamation (via nim-debra) for safe memory deallocation; the SPSC shape frees retired segments inline (no manager). Queue covers:

Cardinality Producers Consumers Push Pop
SPSC Single Single Wait-free Wait-free
SPMC Single Multiple Wait-free Lock-free
MPSC Multiple Single Lock-free Wait-free
MPMC Multiple Multiple Lock-free Lock-free

Compatibility

Requirement Supported
Nim >= 2.2.10
Memory managers orc (default), arc, refc, atomicArc
Backends C, C++
Threads --threads:on required (default in Nim 2.2+)
Platforms (CI-verified) Linux x86_64, Linux arm64, macOS arm64
Sanitisers (CI-verified) ThreadSanitizer (under atomicArc), AddressSanitizer
Dependencies typestates >= 0.12.0 (DEBRA reclamation is bundled in-tree as lockfree/smr/nebr)
License MIT

Item types. Value types and ptr T are stored directly in the slot array. ref T, string, and seq are admitted through Path-C: each slot holds an 8-byte ManagedRef / ManagedSlice token (distinct uint) rather than the payload, so no refcount or buffer mutation races against the concurrent slot read/write. No opt-in flag is required. The unbounded MPMC arm (Queue[T, ccMulti, ccMulti, …]) requires supportsCopyMem(T) AND sizeof(T) <= 8 (strict-LCRQ migration); for wider or move-only T, use BQueue[T, ccMulti, ccMulti, …] or wrap as ptr T. See ManagedRef — ref T payloads and From lockfreequeues v5.

Atomics. All atomics route through debra/atomics, which statically rejects any Atomic[T] instantiation that would fall back to libatomic spinlocks. Enforcement is on by default; opt out with -d:debraAllowNonLockFreeAtomics (per-call-site warning fires).

Installation

nimble install lockfreequeues

Quick Start

Bounded Queue

import lockfreequeues

# Single-producer, single-consumer bounded queue with capacity 16.
var queue = newSpscQueue[int, 16]()

discard queue.push(42)
discard queue.push(123)

let item = queue.pop()  # some(42)

Unbounded Queue (single-producer, single-consumer)

The SPSC Queue shape does not need DEBRA reclamation: the producer and consumer each hold their own segment pointer and the consumer-side advance is the only freer.

import lockfreequeues

# Unbounded SPSC queue with segment size 64.
var queue = newQueue(Queue[int, ccSingle, ccSingle, stEager, 64, 1])

var p = queue.getProducer()
p.push(42)              # never fails — grows as needed
let item = queue.pop()  # some(42)

Unbounded Queue (multi-producer, multi-consumer)

The MP/MC unbounded shapes use a DebraManager for safe segment reclamation. The auto-create constructor heap-allocates a private manager; each operating thread then attach()es its view on the thread that will push/pop through it (DEBRA registration is thread-affine):

import lockfreequeues

# Auto-create MPMC: segment size 64, registry capacity 4.
var queue = newQueue(Queue[int, ccMulti, ccMulti, stEager, 64, 4])

var producer = queue.getProducerHere()  # registers this thread
producer.push(42)                       # may raise DebraRegistrationError

var consumer = queue.getConsumerHere()
let item = consumer.pop()               # some(42)

The *Here templates are sugar for getProducer() + attach() (and getConsumer() + attach()) when the calling thread is also the operating thread. For the producer-to-worker handoff pattern (a parent thread obtains the view and hands it off to a worker thread that does the push/pop), use the explicit getProducer() + attach() pair so the debra registration lands on the worker thread. See the Queue API reference for details.

Choosing a Queue

Use bounded queues when:

  • Memory usage must be predictable
  • Working in embedded or real-time systems
  • Producer/consumer counts are known at compile time

Use unbounded queues when:

  • Workload is bursty or unpredictable
  • Producer/consumer threads are created dynamically
  • Memory growth is acceptable

Examples

Examples are in the examples directory:

nimble examples

References