concurrent-sharded-stack
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. The steal walk uses a
tree-like probe: shards are visited in the XOR-mask order
start, start^1, start^2, start^3, ..., which is the same order a BFS visits a
binary tree of N leaves — shard start is the root, the next bit
corresponds to the next tree level, and so on. Locality first, distant shards
last.
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 ;
use Arc;
use thread;
let stack = new;
let mut handles = Vecnew;
for t in 0..4
for h in handles
let mut popped = Vecnew;
while let Ok = stack.pop
assert_eq!;
API highlights
ConcurrentShardedStack::new()— shard count derived fromavailable_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; distinguishesEmptyfromClosed.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).
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.
Changelog
0.2.0
- Refactored the shard scan in
popto a tree-like probe.
0.1.0
- Initial release.
License
Licensed under either of
- Apache License, Version 2.0 (LICENSE-APACHE)
- MIT license (LICENSE-MIT)
at your option.