Lock-Free Queue

High-performance lock-free concurrent queues for Rust.

Features

• SPSC Queue: Single-Producer Single-Consumer bounded queue (~10-20ns/op)
• MPMC Queue: Multi-Producer Multi-Consumer bounded queue (~30-50ns/op)
• Zero dependencies in core (only crossbeam-utils for cache-line padding)
• Thoroughly tested with multi-threaded stress tests

Usage

SPSC Queue

use lockfree_queue::SpscQueue;// Create queue with capacity 1024 (rounded to power of 2)let(tx, rx) = SpscQueue::<u64>::new(1024).split();// Producer thread
std::thread::spawn(move || {for i in0..1000{while tx.push(i).is_err(){
std::hint::spin_loop();}}});// Consumer thread
std::thread::spawn(move || {for _ in0..1000{while rx.pop().is_none(){
std::hint::spin_loop();}}});

MPMC Queue

use lockfree_queue::MpmcQueue;use std::sync::Arc;let queue = Arc::new(MpmcQueue::<u64>::new(1024));// Multiple producersfor _ in0..4{let q = Arc::clone(&queue);
std::thread::spawn(move || {for i in0..100{while q.push(i).is_err(){}}});}// Multiple consumersfor _ in0..4{let q = Arc::clone(&queue);
std::thread::spawn(move || {whileletSome(val) = q.pop(){// process val}});}

Implementation Details

SPSC Queue

Uses a ring buffer with cache-line-padded head/tail indices:

• Producer writes data, then updates head with Release ordering
• Consumer reads head with Acquire ordering, reads data, updates tail
• Power-of-2 capacity enables fast modulo via bitwise AND
• Cache-line padding prevents false sharing between producer/consumer

MPMC Queue

Based on Dmitry Vyukov's bounded MPMC queue algorithm:

• Each slot has a sequence number for coordination
• Producers/consumers use CAS on head/tail to claim slots
• Sequence numbers provide proper synchronization without locks
• Lock-free progress guarantee: at least one thread always makes progress

Benchmarks

Run benchmarks with:

cargo bench

Typical results on modern hardware:

Queue Type	Scenario	Throughput
SPSC	Single-threaded push/pop	~15 ns/op
SPSC	Producer-Consumer threads	~25 ns/op
MPMC	1P-1C	~35 ns/op
MPMC	4P-4C	~50 ns/op

Safety

This crate uses unsafe for:

• UnsafeCell access (properly synchronized via atomics)
• Implementing Send/Sync for queue types

All unsafe code has been carefully reviewed for correctness:

• No data races: atomic operations provide synchronization
• No use-after-free: Arc prevents premature deallocation
• No undefined behavior: proper memory ordering guarantees visibility

References

• Dmitry Vyukov's MPMC Queue
• Rust Atomics and Locks by Mara Bos
• crossbeam-queue for production use