A (mostly) lock-free concurrent work-stealing deque
This module contains an implementation of the Chase-Lev work stealing deque described in "Dynamic Circular Work-Stealing Deque". The implementation is heavily based on the implementation using C11 atomics in "Correct and Efficient Work Stealing for Weak Memory Models".
The only potentially lock-synchronized portion of this deque is the occasional call to the memory allocator when growing the deque. Otherwise all operations are lock-free.
use deque; let (worker, stealer) = deque::new(); // Only the worker may push/pop worker.push(1); worker.pop(); // Stealers take data from the other end of the deque worker.push(1); stealer.steal(); // Stealers can be cloned to have many stealers stealing in parallel worker.push(1); let stealer2 = stealer.clone(); stealer2.steal();
The stealing half of the work-stealing deque. Stealers have access to the
opposite end of the deque from the worker, and they only have access to the
Worker half of the work-stealing deque. This worker has exclusive access to
one side of the deque, and uses
When stealing some data, this is an enumeration of the possible outcomes.
Allocates a new work-stealing deque.