nblf-queue

Non-Blocking Lock-Free Queue

An atomic lock-free MPMC queue based on the NBLFQ algorithm.

This repository provides multiple queue implementations with different storage and allocation strategies.

All queues in this repository are safe to use in a concurrent context and will never block the calling thread.

Queue variants

Static queues: fixed-capacity queues backed by static storage
Allocated queues: fixed-capacity queues backed by dynamically allocated storage, only available on feature alloc
Dynamic queues: dynamically growable queues, only available on feature dynamic
Pooled Queues: variants of other queues, which may store arbitrary types, only available on feature pool

Non-pooled queues store items in atomically updated slots, restricting the stored items to small, pointer-like values.

Usage

nblf_queue::StaticQueue:

  use nblf_queue::{StaticQueue, MPMCQueue};

  let q: StaticQueue<_, 2> = StaticQueue::new();

  assert!(q.push(&42).is_ok());
  assert!(q.push(&1).is_ok());
  assert!(q.push(&4242).is_err());

  assert_eq!(q.pop(), Some(&42));
  assert_eq!(q.pop(), Some(&1));
  assert!(q.pop().is_none());

nblf_queue::PooledStaticQueue:

  #[cfg(feature = "pool")]
  fn run() {
    use nblf_queue::{PooledStaticQueue, MPMCQueue};

    let q: PooledStaticQueue<_, 2> = PooledStaticQueue::new();

    assert!(q.push(42).is_ok());
    assert!(q.push(1).is_ok());
    assert!(q.push(4242).is_err());

    assert_eq!(q.pop(), Some(42));
    assert_eq!(q.pop(), Some(1));
    assert!(q.pop().is_none());
  }

  #[cfg(feature = "pool")]
  run();

Choosing a queue type

StaticQueue and Queue may only store small values and are optimized for this use case.

PooledStaticQueue and PooledQueue may store arbitrary types, at the cost of higher memory usage and runtime cost.

DynamicQueue and PooledDynamicQueue may be grown dynamically, at the cost of higher total memory usage and runtime cost. This is cost is even higher for PooledDynamicQueue.

Platform Support

Multiple storage types are available, dependent on platform:

Tagged64 - platforms with native 64-bit atomic operations or feature atomic-fallback
Tagged128 - platforms with native 128-bit atomic operations or feature atomic-fallback

Storage types will be chosen automatically, unless sepcified explicitly.

[!NOTE] ABA Safety & Storage Selection If it is plausible that other threads could perform (2^15 - 1) * queue_size pop and push operations while a single thread is paused/preempted in pop/push, Tagged128 slots should be used to ensure ABA safety.

Feature Flags

std: Enables std and alloc support
alloc: Enables alloc support, allowing usage of some dynamically allocated queues
pool: Enables pooled queues, which may store any type
dynamic: Enables dynamic queues, which may dynamically grow
atomic-fallback: Uses portable-atomic fallback feature for atomics if necessary. It is discouraged to use this feature, as fallback internally uses locks
default: pool

Python Bindings

Python bindings backed by PooledQueue and PooledDynamicQueue are available for concurrent applications. Core operations detach from the GIL to allow parallel execution.

[!NOTE] The Python bindings strictly use Auto slots without feature atomic-fallback. As a result, these bindings are only supported on platforms with native 64-bit or 128-bit atomic operations.

  from nblf_queue import Queue, DynamicQueue

  q: Queue[int] = Queue(10)

  q.push(42)
  item = q.pop()
  assert item == 42

  dq: DynamicQueue[str] = DynamicQueue(5)
  dq.push("hello")

  dq.grow()

Testing

The core test-suite of this crate was adapted from crossbeam-queue.

Current testing is based on:

Miri - to validate pointer arithmetic and catch UB
Loom and Shuttle - to test for race conditions
ASan - to check for memory corruption and leakage

References

Alexandre Denis, Charles Goedefroit. NBLFQ: a lock-free MPMC queue optimized for low contention. IPDPS 2025 - 39th International Parallel & Distributed Processing Symposium, IEEE, Jun 2025, Milan, Italy. hal-04851700v2

nblf-queue 0.1.12