Crate bagpipe

Implements the BagPipe data structure, along with its core components.

A BagPipe is a concurrent pool data-structure optimized for throughput and not much else. The core idea is to have a large number of concurrent queues and stacks, along with a way of load-balancing them in a coordination-free way that avoids wasting resources and keeping contention low.

Example

For general-purpose use, the BagPipe has a somewhat low-level interface. Here is some simple example usage:

let bp = BagPipe::<GeneralYC<T>>::new();
for _ in 0..NUM_THREADS {
    let mut my_bp = bp.clone();
    thread::spawn(move || {
        // ... do work
        // loop until push is successful
        my_bp.push_mut()
        // ... more work
        if let PopResult::There(item) = my_bp.try_pop_mut() {
            // use item
        }
    });
}

If you are passing a word-sized type, it is possible to reduce allocation overhead by storing the data in-line. To do this, replace GeneralYC with YangCrummeyQueue in the type parameter for BagPipe: this will switch out the underlying backing data-structure.

The API currently supports try... versions of methods, allowing data-structures to signal lack of progress due to high contention. It also provides push and pop methods that will loop until they succeed (or do something more intelligent).

Guarantees

The data-structures given here are all non-blocking. The try methods using YangCrummeyQueue and GeneralYC will return in a bounded number of steps, but there is no guarantee they will succeed except if they execute in isolation (i.e. Obstruction Freedom when called in a loop). In constrast, those using FAAArrayQueue have a lock-free progress guarantee. In general, a BagPipe inherits its progress guarantees from its underlying SharedWeakBag, but it may return arbitrary values with respect to their ordering guarantees.

BagPipe's emptiness check is not currently linearizable, but I believe it is still serializable. In other words, it is possible to re-order the execution history of the data-structure to respect program order, but calls returning Empty may be re-ordered to a time before or after the real execution time of the operation. A marginally slower linearizable emptiness check would not be difficult to engineer, and it will hopefully be added to the API soon.

Modules

bag	Specification of best-effort bags and implementation for crossbeam data-structures.
queue	Implementation of two non-blocking queues.

Structs

BagPipe

A concurrent bag data-structure built from sharding requests over other bags.