concurrent-sharded-stack 0.1.0

A lock-free concurrent stack that shards a Treiber stack per thread and reclaims memory with epoch-based GC.
Documentation

concurrent-sharded-stack

CI crates.io docs.rs

A lock-free concurrent stack that reduces contention by sharding a classic Treiber stack across multiple per-thread shards, reclaiming memory safely with epoch-based garbage collection (via crossbeam-epoch).

Why sharding?

A single Treiber stack funnels every push/pop through one atomic head pointer, so under heavy multi-threaded load the CAS loop becomes a contention bottleneck. This crate keeps N independent shards (each a Treiber stack on its own cache line) and routes each thread to a shard derived from its thread id. A coarse atomic bitmap hints which shards are non-empty so that pop can steal from other shards when the local one is empty.

Trade-off: the structure is a bag-like LIFO. Ordering is only LIFO within a shard; across shards there is no global ordering guarantee.

Example

use concurrent_sharded_stack::{ConcurrentShardedStack, PopError};
use std::sync::Arc;
use std::thread;

let stack = Arc::new(ConcurrentShardedStack::new());

let mut handles = Vec::new();
for t in 0..4 {
    let stack = Arc::clone(&stack);
    handles.push(thread::spawn(move || {
        stack.push(t).unwrap();
    }));
}
for h in handles {
    h.join().unwrap();
}

let mut popped = Vec::new();
while let Ok(v) = stack.pop() {
    popped.push(v);
}
assert_eq!(popped.len(), 4);

API highlights

  • ConcurrentShardedStack::new() — shard count derived from available_parallelism().
  • with_concurrency(n) — exact shard count (must be a non-zero power of two, <= usize::BITS).
  • push(value) -> Result<(), PushError<T>> — fails only if the stack is closed.
  • pop() -> Result<T, PopError> — non-blocking; distinguishes Empty from Closed.
  • close() / is_closed() — graceful shutdown; existing elements remain poppable until drained.

Safety

The implementation is unsafe-heavy by nature (lock-free + manual memory reclamation). Correctness is checked under Miri in CI using the Tree Borrows aliasing model, including dedicated tests that detect double-drops and leaks of non-Copy payloads.

Benchmarks

The benchmarks in benches/ compare three implementations on the same workload:

  • this crate's ConcurrentShardedStack,
  • lockfree::stack::Stack — a popular single lock-free stack on crates.io,
  • a Mutex<Vec<T>> baseline.

Two workloads model real usage under heavily oversubscribed thread counts (8 → 256 threads, i.e. far past the core count, as in web servers and thread pools):

  • object_pool — a fixed pool where every worker repeatedly acquires (pop) and releases (push) an object (connection/buffer pool pattern).
  • mpmc — dedicated producer and consumer threads (fan-out work queue).
cargo bench

Sharding keeps throughput roughly flat as threads pile up, whereas a single lock-free stack degrades under CAS contention — that gap is the whole point of the crate.

License

Licensed under either of

at your option.