lockfree/bqueue128

Concurrency Topology: 128-Bit DWCAS Bounded MPMC Queue (BQueue128)

Dimension	Specification
Topologies	MPMC, MPSC, SPMC, SPSC (fully multi-producer multi-consumer safe)
Algorithm	Double-Word CAS (DWCAS) Bounded MPMC Ring Buffer
Capacity	Fixed compile-time capacity N (must be a power of two)
Atomic Substrate	128-Bit Hardware DWCAS (CMPXCHG16B on x86_64, CASP on ARM64)
Slot Geometry	16-Byte Aligned Pair[uint64, T] (Sequence + Value in 1 Word)
Cacheline Isolation	head and tail isolated on distinct CacheLineBytes lines
Progress Guarantee	Lock-Free / Wait-Free Slot Publication
Memory Reclamation	Zero heap allocation at runtime, in-place slot reuse, zero SMR

Algorithmic Foundations

In Dmitry Vyukov's classical bounded queue (BQueue), publishing an item requires two separate phases:

1. Producer claims the slot turn by advancing tail.
2. Producer writes data non-atomically, then stores the updated sequence.

If the producer is descheduled between steps 1 and 2, the slot remains in a half-written intermediate state, forcing downstream consumers to spin.

BQueue128 solves this via hardware 128-Bit Double-Word Compare-And-Swap:

• Each slot is an Atomic[Pair[uint64, T]] (16 bytes aligned to 16 bytes).
• The turn sequence and the 64-bit payload reside inside the same atomic word.
• Enqueue: Simultaneously advances sequence from pos to pos + 1 and installs the payload in a single atomic bus transaction (cmpxchg16b / casp).
• Dequeue: Simultaneously reads the payload and recycles sequence to pos + N.
• Cache Density: With 16-byte slots, 4 slots pack into a single 64-byte line (or 8 on Apple Silicon 128-byte lines), reducing memory footprint by up to 75% compared to cache-padded cell structures.

Types

BQueue128Slot

BQueue128Slot[T] = Atomic[Pair[uint64, T]]

16-byte slot holding monotonic sequence counter (Pair.first) and payload (Pair.second) in a single hardware DWCAS-able atomic word.

BQueue128

BQueue128[T; N] = object
  head* {.align: 128.}: Atomic[uint64]
  tail* {.align: 128.}: Atomic[uint64]
  cells* {.align: 128.}: array[N, BQueue128Slot[T]]

Bounded lock-free MPMC queue utilizing 128-bit atomic DWCAS for instantaneous slot publication without intermediate partial-write states.

Constants

BQueue128MaxWaitForPublishSpins

BQueue128MaxWaitForPublishSpins {.intdefine.}: int = 1024

Bounded spin budget for a consumer waiting on an in-flight producer that has claimed the slot turn (tail advanced past pos) but has not yet completed its 128-bit atomic slot publication (or vice versa for a producer waiting on an in-flight consumer). After this many cpuPause spins, the operation surrenders and returns false to prevent deadlocking on preempted peers.

Procedures & Functions

initBQueue128

proc initBQueue128[T: uint64 | int64 | pointer | int; N: static int](): BQueue128[
    T, N]

Initializes a value-type BQueue128 with compile-time power-of-two capacity N. Inlined storage owns array[N, BQueue128Slot[T]].

allocAlignedBQueue128

proc allocAlignedBQueue128[T: uint64 | int64 | pointer | int; N: static int](): ptr BQueue128[
    T, N]

Allocates a heap-allocated BQueue128 instance guaranteed to be aligned to at least CacheLineBytes (64 bytes on x86_64, 128 bytes on Apple Silicon). Free with freeAlignedBQueue128.

freeAlignedBQueue128

proc freeAlignedBQueue128[T: uint64 | int64 | pointer | int; N: static int](
    q: ptr BQueue128[T, N])

Releases a heap-allocated BQueue128 instance previously created by allocAlignedBQueue128.

=copy

proc `=copy`[T, N](dest: var BQueue128[T, N]; src: BQueue128[T, N]) {.error: "BQueue128 contains inlined atomic storage and cannot be copied. Pass by `var` or `ptr`.".}

tryPush

proc tryPush[T: uint64 | int64 | pointer | int; N: static int](
    self: var BQueue128[T, N]; val: T): bool {.inline.}

Enqueues val into the queue.

Returns true if enqueued successfully. Returns false immediately if the queue is full.

Uses 128-bit hardware DWCAS (cmpxchg16b / casp) to atomically advance the slot turn and publish the payload in a single instruction.

tryPop

proc tryPop[T: uint64 | int64 | pointer | int; N: static int](
    self: var BQueue128[T, N]; val: var T): bool {.inline.}

Dequeues an item from the queue, storing it in val.

Returns true if an item was dequeued. Returns false immediately if the queue is empty.

pop

proc pop[T: uint64 | int64 | pointer | int; N: static int](
    self: var BQueue128[T, N]): Option[T] {.inline.}

Dequeues an item from the queue returning some(item) or none(T) if empty.

tryPeek

proc tryPeek[T: uint64 | int64 | pointer | int; N: static int](
    self: BQueue128[T, N]; val: var T): bool {.inline.}

Optimistically inspects the item at the head of the queue without dequeuing.

Note: In concurrent multi-consumer environments, peek is inherently racy.

peek

proc peek[T: uint64 | int64 | pointer | int; N: static int](
    self: BQueue128[T, N]): Option[T] {.inline.}

Optimistically inspects the item at the head of the queue returning Option[T].

len

proc len[T, N](self: BQueue128[T, N]): int {.inline.}

Returns an approximate snapshot of the number of items currently in the queue.

capacity

proc capacity[T, N](self: BQueue128[T, N]): int {.inline.}

Returns the maximum fixed capacity of the queue (N).

isEmpty

proc isEmpty[T, N](self: BQueue128[T, N]): bool {.inline.}

Returns true if the queue is approximately empty.

isFull

proc isFull[T, N](self: BQueue128[T, N]): bool {.inline.}

Returns true if the queue is approximately full.

clear

proc clear[T, N](self: var BQueue128[T, N])

Drains all elements from the queue until empty.

drain

proc drain[T, N](self: var BQueue128[T, N]): seq[T]

Drains all elements from the queue into a seq.

Templates

push

template push[T, N](self: var BQueue128[T, N]; val: T): bool

Convenience alias for tryPush.

Iterators

items

iterator items[T, N](self: var BQueue128[T, N]): T

Warning: Destructively drains the queue until empty, yielding each element.