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(missing_docs, missing_debug_implementations, rust_2018_idioms)] 93 #![cfg_attr(not(feature = "std"), no_std)] 94 // matches! requires Rust 1.42 95 #![allow(clippy::match_like_matches_macro)] 96 97 use cfg_if::cfg_if; 98 99 cfg_if! { 100 if #[cfg(feature = "std")] { 101 use crossbeam_epoch as epoch; 102 use crossbeam_utils as utils; 103 104 mod deque; 105 pub use crate::deque::{Injector, Steal, Stealer, Worker}; 106 } 107 } 108