Crate bagpipe [] [src]

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.


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


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.



Specification of best-effort bags and implementation for crossbeam data-structures.


Implementation of two non-blocking queues.



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