concurrent-sharded-stack
Lock-free sharded stacks for unordered object recycling. Requires Rust 1.85+.
Both variants use Treiber stacks and crossbeam-epoch; neither uses a shard mutex.
| Type | Node storage | Result of pop() |
|---|---|---|
ConcurrentShardedStack<T> |
Allocates a wrapper on each push | Immediately returns T |
IntrusiveShardedStack<A> |
Uses the object's embedded atomic link | Returns Retired<A>; delivers the pointer after an epoch grace period |
Install
[]
= "0.3"
The intrusive feature is enabled by default. To use only the original value
stack, without the intrusive-collections dependency:
= { = "0.3", = false }
Values
use ConcurrentShardedStack;
let pool = with_concurrency;
pool.push.unwrap;
let mut buffer = pool.pop.unwrap;
buffer.clear;
pool.push.unwrap;
Intrusive nodes
use ;
use ;
intrusive_adapter!;
// SAFETY: the generated stateless adapter and Box preserve node ownership
// and address until the collector restores the original pointer.
unsafe
let stack = with_concurrency;
stack.push.unwrap;
stack.pop.unwrap.defer;
A popped node stays claimed until callback delivery; immediately returning a
Box or reusing its link would invalidate concurrent readers. Retirement is
batched: call intrusive::collect() on each retiring thread before it waits or
becomes idle, and periodically while awaiting callbacks. Another thread cannot
flush that thread's pending batch; thread exit also flushes it. Collection is
not a synchronous barrier; a pinned thread can indefinitely delay delivery.
Dropping Retired schedules destruction instead. Epoch bookkeeping and large
callbacks may allocate, although the stack never allocates wrapper nodes.
See the intrusive guide for trait contracts and tradeoffs, or run the complete recycling example:
Shared contracts
- Shards must be a nonzero power of two. Ordering is LIFO per shard, not global.
pop()scans in XOR order.Emptyis retryable, not an atomic snapshot.close()closes shards gradually. Rejected pushes return the original value; stored nodes remain drainable. Its boolean reports whether this call closed any shard, so multiple callers may returntrue.PopError::Closedmeans all shards are closed and drained. Intrusive callbacks may still be pending; neitherclose()nor stack destruction waits for them.
Benchmarks and profiling measure completed delivery, including the epoch cost. Validation and contribution guide. Changelog. Licensed under Apache-2.0 or MIT, at your option.