| 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 |
|
| 100 |
#[cfg(feature = "std")] |
| 101 |
mod deque; |
| 102 |
#[cfg(feature = "std")] |
| 103 |
pub use crate::deque::{Injector, Steal, Stealer, Worker}; |