Name Description Size
deque.rs 67060
lib.rs Concurrent work-stealing deques. These data structures are most commonly used in work-stealing schedulers. The typical setup involves a number of threads, each having its own FIFO or LIFO queue (*worker*). There is also one global FIFO queue (*injector*) and a list of references to *worker* queues that are able to steal tasks (*stealers*). We spawn a new task onto the scheduler by pushing it into the *injector* queue. Each worker thread waits in a loop until it finds the next task to run and then runs it. To find a task, it first looks into its local *worker* queue, and then into the *injector* and *stealers*. # Queues [`Injector`] is a FIFO queue, where tasks are pushed and stolen from opposite ends. It is shared among threads and is usually the entry point for new tasks. [`Worker`] has two constructors: * [`new_fifo()`] - Creates a FIFO queue, in which tasks are pushed and popped from opposite ends. * [`new_lifo()`] - Creates a LIFO queue, in which tasks are pushed and popped from the same end. Each [`Worker`] is owned by a single thread and supports only push and pop operations. Method [`stealer()`] creates a [`Stealer`] that may be shared among threads and can only steal tasks from its [`Worker`]. Tasks are stolen from the end opposite to where they get pushed. # Stealing Steal operations come in three flavors: 1. [`steal()`] - Steals one task. 2. [`steal_batch()`] - Steals a batch of tasks and moves them into another worker. 3. [`steal_batch_and_pop()`] - Steals a batch of tasks, moves them into another queue, and pops one task from that worker. In contrast to push and pop operations, stealing can spuriously fail with [`Steal::Retry`], in which case the steal operation needs to be retried. # Examples Suppose a thread in a work-stealing scheduler is idle and looking for the next task to run. To find an available task, it might do the following: 1. Try popping one task from the local worker queue. 2. Try stealing a batch of tasks from the global injector queue. 3. Try stealing one task from another thread using the stealer list. An implementation of this work-stealing strategy: ``` use crossbeam_deque::{Injector, Stealer, Worker}; use std::iter; fn find_task<T>( local: &Worker<T>, global: &Injector<T>, stealers: &[Stealer<T>], ) -> Option<T> { // Pop a task from the local queue, if not empty. local.pop().or_else(|| { // Otherwise, we need to look for a task elsewhere. iter::repeat_with(|| { // Try stealing a batch of tasks from the global queue. global.steal_batch_and_pop(local) // Or try stealing a task from one of the other threads. .or_else(|| stealers.iter().map(|s| s.steal()).collect()) }) // Loop while no task was stolen and any steal operation needs to be retried. .find(|s| !s.is_retry()) // Extract the stolen task, if there is one. .and_then(|s| s.success()) }) } ``` [`new_fifo()`]: Worker::new_fifo [`new_lifo()`]: Worker::new_lifo [`stealer()`]: Worker::stealer [`steal()`]: Stealer::steal [`steal_batch()`]: Stealer::steal_batch [`steal_batch_and_pop()`]: Stealer::steal_batch_and_pop 4159