concurrent-sharded-stack
A value-owning concurrent sharded stack. Version 0.4 delegates its concurrent
algorithm to concurrent-intrusive-collections
and exposes only the ordinary ConcurrentShardedStack<T> API.
[]
= "0.4"
Requires Rust 1.85 and T: Send + 'static. Values need not implement Sync or Clone.
use ;
let stack = with_concurrency;
stack.push.unwrap;
stack.push.unwrap;
assert_eq!;
assert!;
assert_eq!;
assert_eq!;
let rejected = stack.push.unwrap_err.into_inner;
assert_eq!;
Semantics
new()selects available parallelism rounded up to a power of two, with a four-shard fallback.with_concurrency(n)requires a nonzero power of two.- Push targets a stable thread-local shard; pop probes local then XOR-ordered shards. LIFO applies within each shard, not globally. A busy shard can starve another.
Emptyreports a scan, not an atomic snapshot. Retry while producers are active.close()closes each shard and returns whether this call changed any shard. Multiple concurrent callers may return true. After return, later pushes fail. Existing values can be drained untilClosed;is_closed()observes closure.is_empty()observes empty shards during a scan; it is not a global snapshot.shard_count()reports the configured number of shards.
Ownership and safety
Each push allocates a private node. A successful pop immediately returns the original owned value. Only the now-empty node allocation awaits the default Crossbeam collector's grace period, so payloads may be reused immediately. Rejected pushes return the original value without publishing it.
The wrapper uses a private UnsafeCell<Option<T>>. Concurrent readers inspect
only the link; exactly one successful pop callback moves out the value while
pinned. The node is never exposed, and no shared payload reference is returned.
This is why Send values such as Cell<usize> remain supported without Sync.
The wrapper does not duplicate the shard/CAS/reclamation algorithm.
Drop drains remaining payloads synchronously, including continuing after one payload destructor panics. A second panic during unwinding aborts as usual. Retired empty node allocations may outlive the stack. Allocation, reclamation and payload destructors are not guaranteed lock-free; the underlying link algorithm is.
Migrating from 0.3
- Keep
ConcurrentShardedStack,push(T),pop(), close and shard-count calls. - Value types now require
Send + 'static; scoped borrows and non-Send values are no longer supported.T: Syncis not required. - The
intrusivefeature,intrusivemodule,IntrusiveShardedStack, adapters,Retiredand theintrusive_collectionsreexport have been removed entirely. Removefeatures = ["intrusive"]from dependency declarations. - For intrusive collections, depend directly on
concurrent-intrusive-collections0.3 and use itsSinglyLinked/Box<T>callback API. It does not reproduce the former adapter or retired-node-delivery API. PopErroris reexported from the shared core; match its variants rather than relying on previous error display strings.
Run cargo run --example buffer_recycling for a bounded buffer reuse example.
The surviving stack_bench compares value stacks; records under docs/benchmarks
are historical measurements of earlier releases, not performance claims for 0.4.
See CONTRIBUTING.md
for validation commands and CHANGELOG.md
for release history. Licensed under MIT OR Apache-2.0.
Optional worker-local object reuse
cargo run --example cached_buffer_recycling demonstrates bounded payload caches
using the existing safe value API. Each worker caches at most four buffers and
flushes every 64 requests and on exit. All workers join and return caches before
the owner closes the pool. The final check verifies every original buffer ID.
This example intentionally keeps its policy outside the public stack API. A
cached return is not yet visible to other workers. The policy needs enough spare
objects, is not suitable for work queues or scarce resources requiring fairness,
and provides no wall-clock fairness bound. A cache dropped after early close
destroys rejected payloads. flush returns ownership of its first rejected value;
remaining cached values stay owned by the cache. Nodes are never reused before
an epoch grace period; only independently owned payloads are reused.
Steady-state measurements
Compile cargo bench --bench steady --no-run, then run the resulting executable:
steady --mode shared --workers 4 --shards 4 --bytes 256 --ops 200000 --samples 9
steady --mode cached --workers 4 --shards 4 --bytes 256 --ops 200000 --samples 9
steady --mode shared --workers 4 --shards 4 --count
steady --mode cached --workers 4 --shards 4 --count
steady --mode empty --workers 4 --shards 32
steady --mode mpmc --workers 8 --producers 1 --shards 8 --bytes 256
Workers persist across samples; collector registration, pool creation and payload preallocation are outside timing. One full warmup is discarded. End-of-sample cache flush is timed. MPMC counts each transferred value once; object-pool modes count a take/return pair once. MPMC payload destruction is timed. Exact ID checks are outside timing. Failed shared pops yield and retry with a stall deadline.
Latency is sampled every 997 operations (coprime to the cache flush period), and includes the sampled operation's bookkeeping. MPMC latency combines push and pop samples; it is not end-to-end queue latency. Allocation-counting mode adds shared counters and must be run separately from throughput comparisons. Counts include EBR metadata allocations triggered during the timed phase. Outstanding EBR memory is not a peak-RSS measurement. CPU affinity, frequency, and allocator state are uncontrolled; use paired/reversed-order repeats and report variation and regressions. The original Criterion benchmark is retained for end-to-end workloads including startup and teardown.