Crate crossbeam_deque [−] [src]

A concurrent work-stealing deque.

The data structure can be thought of as a dynamically growable and shrinkable buffer that has two ends: bottom and top. A Deque can push elements into the bottom and pop elements from the bottom, but it can only steal elements from the top.

A Deque doesn't implement Sync so it cannot be shared among multiple threads. However, it can create Stealers, and those can be easily cloned, shared, and sent to other threads. Stealers can only steal elements from the top.

Here's a visualization of the data structure:

                   top
                    _
   Deque::steal -> | | <- Stealer::steal
                   | |
                   | |
                   | |
Deque::push/pop -> |_|

                 bottom

Work-stealing schedulers

Usually, the data structure is used in work-stealing schedulers as follows.

There is a number of threads. Each thread owns a Deque and creates a Stealer that is shared among all other threads. Alternatively, it creates multiple Stealers - one for each of the other threads.

Then, all threads are executing in a loop. In the loop, each one attempts to pop some work from its own Deque. But if it is empty, it attempts to steal work from some other thread instead. When executing work (or being idle), a thread may produce more work, which gets pushed into its Deque.

Of course, there are many variations of this strategy. For example, sometimes it may be beneficial for a thread to always steal work from the top of its deque instead of calling pop and taking it from the bottom.

Examples

use crossbeam_deque::{Deque, Steal};
use std::thread;

let d = Deque::new();
let s = d.stealer();

d.push('a');
d.push('b');
d.push('c');

assert_eq!(d.pop(), Some('c'));
drop(d);

thread::spawn(move || {
    assert_eq!(s.steal(), Steal::Data('a'));
    assert_eq!(s.steal(), Steal::Data('b'));
}).join().unwrap();

References

The implementation is based on the following work:

  1. Chase and Lev. Dynamic circular work-stealing deque. SPAA 2005.
  2. Le, Pop, Cohen, and Nardelli. Correct and efficient work-stealing for weak memory models. PPoPP 2013.
  3. Norris and Demsky. CDSchecker: checking concurrent data structures written with C/C++ atomics. OOPSLA 2013.

Structs

Deque

A concurrent work-stealing deque.
Stealer

A stealer that steals elements from the top of a deque.

Enums

Steal

Possible outcomes of a steal operation.