mpmc-resize

A construction that transform a bounded collection into a resizable collection.

This crate implements a generic construction which allows dynamically resizing a wrapped datastructure, while preserving some key properties.

Property Preservation

Progress Guarantees:

• Lock Freedom: if the wrapped collection is lock-free, all corresponding operations on Resizable are also lock-free.
• Obstruction Freedom: if the wrapped collection exposes obstruction-free methods, all corresponding operations on Resizable are also obstruction-free.

Resizable::resize may block on the allocator.

Ordering and Consistency Guarantees:

• Relaxed FIFO: if the wrapped collection has FIFO ordering, Resizable has k-FIFO ordering.
• Linearizability: if the wrapped collection is linearizable, all operations on Resizable are also linearizable with respect to its relaxed FIFO specification.
• Empty-Linearizability: if the wrapped collection is linearizale, all operations on Resizable are empty-linearizable with respect to the wrapped collections specification.

Specifically, for any item x, its rank displacement is bounded by:

rank_errorx ≤ K

And its delay by:

delayx ≤ P

where

• K is the number of concurrent calls to try_push
• P is the number of concurren calls to try_pop overlapping with the $K$ executions

For the reasoning behind this bound consult the document docs/Relaxation.md.

If no call to Resizable::resize happens, or in steady-state, Resizable has strict FIFO ordering and is strictly linearizable, given the same holds for the wrapped collection.

Limitations

Overhead

Preserving lock-free progress guarantees and linearizability across dynamic epoch shifts introduces some operational overhead:

• Steady-State: In a single-producer single-consumer (SPSC) scenario with no active resizes, wrapping a queue (e.g., Resizable<ArrayQueue>) achieves roughly 40% of the throughput of the raw underlying queue.
• Active Resizing: Dynamically triggering resizes under load reduces throughput by an additional ~30% during migration bursts. However, the throughput gained from higher buffer capacity can offset this cost over time.
• Reordering in practice: Item reordering is rare in practice and depends strongly on the number of threads concurrently invoking BoundedCollection::try_pop and BoundedCollection::try_push during an active Resizable::resize.

Benchmarks can be found in benches/main_benchmarks.rs.

Resizing Frequency

The maximum frequency of successful resizes is currently bounded by the speed with which stale accesses get processed. Before a second resize can happen, all items of the old raw collection must be removed and all accesses must be concluded.

If a thread gets permanently preempted while accessing a stale raw collection, no further items get removed, then no resize can happen again.

Usage

To use Resizable on your type, you must implement BoundedCollection for it.

// Create a Resizable wrapping your datastructure
let container = Resizable::<MyQueue<i32>>::with_capacity(2);

// It implements all operations of a BoundedCollection
assert!(container.try_push(42).is_ok());
assert!(container.try_push(10).is_ok());
assert!(container.is_full());

// The container can now be dynamically resized, even if the wrapped datastructure cannot
assert!(container.resize(4));
assert!(!container.is_full());

assert!(container.try_push(30).is_ok());
assert_eq!(container.try_pop(), Some(42));

For more info on how to implement BoundedCollection, refer to its documentation.

Platform Support

All platforms supporting native atomic operations are supported.

The feature atomic-fallback may be used, if no native atomic operations are available.

Feature Flags

• std: Enables std support.
• atomic-fallback: Uses the portable-atomic fallback feature if native atomics are missing. It is discouraged to use this feature, as fallback atomics internally rely on locks.
• default: None

Testing

Currently testing is based on:

• Miri - to validate pointer arithmetic and catch undefined behavior.
• Loom and Shuttle - to test for race conditions and non-blocking invariants.
• ASan - to check for memory corruption.