concurrent-sharded-stack 0.4.1

A value-owning sharded concurrent stack backed by concurrent-intrusive-collections.
Documentation

concurrent-sharded-stack

CI crates.io docs.rs

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.

[dependencies]

concurrent-sharded-stack = "0.4"

Requires Rust 1.85 and T: Send + 'static. Values need not implement Sync or Clone.

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 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.