# concurrent-sharded-stack
[](https://github.com/zhongyi51/concurrent-sharded-stack/actions/workflows/ci.yml)
[](https://crates.io/crates/concurrent-sharded-stack)
[](https://docs.rs/concurrent-sharded-stack)
A value-owning concurrent sharded stack. Version 0.4 delegates its concurrent
algorithm to [concurrent-intrusive-collections](https://crates.io/crates/concurrent-intrusive-collections)
and exposes only the ordinary `ConcurrentShardedStack<T>` API.
```toml
[dependencies]
concurrent-sharded-stack = "0.4"
```
Requires Rust 1.85 and `T: Send + 'static`. Values need not implement `Sync` or `Clone`.
```rust
use concurrent_sharded_stack::{ConcurrentShardedStack, PopError};
let stack = ConcurrentShardedStack::with_concurrency(4);
stack.push(String::from("first")).unwrap();
stack.push(String::from("second")).unwrap();
assert_eq!(stack.pop().unwrap(), "second");
assert!(stack.close());
assert_eq!(stack.pop().unwrap(), "first");
assert_eq!(stack.pop(), Err(PopError::Closed));
let rejected = stack.push(String::from("rejected")).unwrap_err().into_inner();
assert_eq!(rejected, "rejected");
```
## 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.
- `Empty` reports 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 until `Closed`; `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: Sync` is not required.
- The `intrusive` feature, `intrusive` module, `IntrusiveShardedStack`, adapters,
`Retired` and the `intrusive_collections` reexport have been removed entirely.
Remove `features = ["intrusive"]` from dependency declarations.
- For intrusive collections, depend directly on `concurrent-intrusive-collections`
0.3 and use its `SinglyLinked`/`Box<T>` callback API. It does not reproduce the
former adapter or retired-node-delivery API.
- `PopError` is 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](https://github.com/zhongyi51/concurrent-sharded-stack/blob/main/CONTRIBUTING.md)
for validation commands and [CHANGELOG.md](https://github.com/zhongyi51/concurrent-sharded-stack/blob/main/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:
```text
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.