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.

Under FIFO ordering the relaxation is bounded as folows:

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

[!NOTE] All ordering claims and relaxation bounds are made in the context of collections with FIFO ordering or no ordering. Wrapping collections with different specifications may result in unbounded relaxation of those specifications.

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

If no call to Resizable::resize happens, or in steady-state, Resizable preserves the ordering specification of the wrapped data structure strictly 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§

Drain
An iterator that drains all remaining items from multiple collections.
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.