Skip to main content

Crate mpmc_resize

Crate mpmc_resize 

Source
Expand description

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.

Structs§

IntoIter
An iterator over a Resizable
Resizable
A dynamically resizable wrapper around a BoundedCollection.

Traits§

BoundedCollection
This trait is used to describe a collection that is wrapped by a Resizable.