nblf-queue 0.1.0

Lock-free, non-blocking MPMC queues.

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