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.
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 |
queue |
Implementation of two non-blocking queues. |
Structs
BagPipe |
A concurrent bag data-structure built from sharding requests over other bags. |