1//! Concurrent work-stealing deques.
2//!
3//! These data structures are most commonly used in work-stealing schedulers. The typical setup
4//! involves a number of threads, each having its own FIFO or LIFO queue (*worker*). There is also
5//! one global FIFO queue (*injector*) and a list of references to *worker* queues that are able to
6//! steal tasks (*stealers*).
7//!
8//! We spawn a new task onto the scheduler by pushing it into the *injector* queue. Each worker
9//! thread waits in a loop until it finds the next task to run and then runs it. To find a task, it
10//! first looks into its local *worker* queue, and then into the *injector* and *stealers*.
11//!
12//! # Queues
13//!
14//! [`Injector`] is a FIFO queue, where tasks are pushed and stolen from opposite ends. It is
15//! shared among threads and is usually the entry point for new tasks.
16//!
17//! [`Worker`] has two constructors:
18//!
19//! * [`new_fifo()`] - Creates a FIFO queue, in which tasks are pushed and popped from opposite
20//! ends.
21//! * [`new_lifo()`] - Creates a LIFO queue, in which tasks are pushed and popped from the same
22//! end.
23//!
24//! Each [`Worker`] is owned by a single thread and supports only push and pop operations.
25//!
26//! Method [`stealer()`] creates a [`Stealer`] that may be shared among threads and can only steal
27//! tasks from its [`Worker`]. Tasks are stolen from the end opposite to where they get pushed.
28//!
29//! # Stealing
30//!
31//! Steal operations come in three flavors:
32//!
33//! 1. [`steal()`] - Steals one task.
34//! 2. [`steal_batch()`] - Steals a batch of tasks and moves them into another worker.
35//! 3. [`steal_batch_and_pop()`] - Steals a batch of tasks, moves them into another queue, and pops
36//! one task from that worker.
37//!
38//! In contrast to push and pop operations, stealing can spuriously fail with [`Steal::Retry`], in
39//! which case the steal operation needs to be retried.
40//!
41//! # Examples
42//!
43//! Suppose a thread in a work-stealing scheduler is idle and looking for the next task to run. To
44//! find an available task, it might do the following:
45//!
46//! 1. Try popping one task from the local worker queue.
47//! 2. Try stealing a batch of tasks from the global injector queue.
48//! 3. Try stealing one task from another thread using the stealer list.
49//!
50//! An implementation of this work-stealing strategy:
51//!
52//! ```
53//! use crossbeam_deque::{Injector, Stealer, Worker};
54//! use std::iter;
55//!
56//! fn find_task<T>(
57//! local: &Worker<T>,
58//! global: &Injector<T>,
59//! stealers: &[Stealer<T>],
60//! ) -> Option<T> {
61//! // Pop a task from the local queue, if not empty.
62//! local.pop().or_else(|| {
63//! // Otherwise, we need to look for a task elsewhere.
64//! iter::repeat_with(|| {
65//! // Try stealing a batch of tasks from the global queue.
66//! global.steal_batch_and_pop(local)
67//! // Or try stealing a task from one of the other threads.
68//! .or_else(|| stealers.iter().map(|s| s.steal()).collect())
69//! })
70//! // Loop while no task was stolen and any steal operation needs to be retried.
71//! .find(|s| !s.is_retry())
72//! // Extract the stolen task, if there is one.
73//! .and_then(|s| s.success())
74//! })
75//! }
76//! ```
77//!
78//! [`new_fifo()`]: Worker::new_fifo
79//! [`new_lifo()`]: Worker::new_lifo
80//! [`stealer()`]: Worker::stealer
81//! [`steal()`]: Stealer::steal
82//! [`steal_batch()`]: Stealer::steal_batch
83//! [`steal_batch_and_pop()`]: Stealer::steal_batch_and_pop
84
85#![doc(test(
86 no_crate_inject,
87 attr(
88 deny(warnings, rust_2018_idioms),
89 allow(dead_code, unused_assignments, unused_variables)
90 )
91))]
92#![warn(
93 missing_docs,
94 missing_debug_implementations,
95 rust_2018_idioms,
96 unreachable_pub
97)]
98#![cfg_attr(not(feature = "std"), no_std)]
99
100use cfg_if::cfg_if;
101
102cfg_if! {
103 if #[cfg(feature = "std")] {
104 use crossbeam_epoch as epoch;
105 use crossbeam_utils as utils;
106
107 mod deque;
108 pub use crate::deque::{Injector, Steal, Stealer, Worker};
109 }
110}
111