Work-stealing deque

Deep dive

How it works

Parts:

• worker deque — ring buffer with two indices, top and bottom
• owner — the one thread that pushes and pops at bottom (LIFO)
• thieves — idle workers that steal at top (FIFO) with one CAS
• global injector — shared queue for tasks submitted from outside the pool (see Implementation notes)

Operations: push, pop, steal (steps below).

1. push(x): b = bottom; if b - top ≥ cap grow or fail; buf[b] = x; release fence; bottom = b + 1.
2. pop(): b = bottom - 1; bottom = b; fence(SeqCst); t = top. If t > b: empty, restore bottom. If t < b: take buf[b], no race possible. If t == b: last item, CAS(top, t, t+1) against thieves, then bottom = b + 1.
3. steal(): t = top (acquire); fence(SeqCst); b = bottom (acquire). If t < b: read buf[t], CAS(top, t, t+1); failure means another thief or the owner won: retry or give up.
4. The SeqCst fences prevent the owner and a thief from both seeing the last item as theirs (a store→load race on bottom/top).

             top (thieves CAS here)                bottom (owner only)
               v                                      v
 buf:  [ ... | T3 | T4 | T5 | T6 | ... ]   size = bottom - top
 owner: push/pop at bottom (LIFO)    thief: steal at top (FIFO)

Code

Chase-Lev deque in the C11 formulation of Lê et al., fixed capacity. Slots hold AtomicPtrs to boxed tasks so a stale thief's read is never a data race.

use std::cell::Cell;
use std::marker::PhantomData;
use std::sync::atomic::{fence, AtomicIsize, AtomicPtr, Ordering::{Acquire, Relaxed, Release, SeqCst}};
use std::sync::Arc;

#[repr(align(128))]
struct Pad<T>(T);

struct Inner<T> { top: Pad<AtomicIsize>, bottom: Pad<AtomicIsize>, buf: Box<[AtomicPtr<T>]>, mask: isize }
unsafe impl<T: Send> Send for Inner<T> {}
unsafe impl<T: Send> Sync for Inner<T> {}

pub struct Worker<T> { q: Arc<Inner<T>>, _not_sync: PhantomData<Cell<()>> } // one owner thread
pub struct Stealer<T> { q: Arc<Inner<T>> }
impl<T> Clone for Stealer<T> { fn clone(&self) -> Self { Stealer { q: self.q.clone() } } }
pub enum Steal<T> { Empty, Retry, Success(Box<T>) }

pub fn deque<T>(cap: usize) -> (Worker<T>, Stealer<T>) {
    let cap = cap.max(2).next_power_of_two();
    let buf = (0..cap).map(|_| AtomicPtr::new(std::ptr::null_mut())).collect();
    let q = Arc::new(Inner { top: Pad(AtomicIsize::new(0)), bottom: Pad(AtomicIsize::new(0)), buf, mask: cap as isize - 1 });
    (Worker { q: q.clone(), _not_sync: PhantomData }, Stealer { q })
}

impl<T> Inner<T> { fn slot(&self, i: isize) -> &AtomicPtr<T> { &self.buf[(i & self.mask) as usize] } }

impl<T> Worker<T> {
    pub fn push(&self, task: Box<T>) -> Result<(), Box<T>> {
        let q = &*self.q;
        let b = q.bottom.0.load(Relaxed);
        let t = q.top.0.load(Acquire);
        if b - t > q.mask { return Err(task); } // full; a growable deque would swap in a bigger buffer here
        q.slot(b).store(Box::into_raw(task), Relaxed);
        fence(Release); // slot (and task contents) visible before the new bottom
        q.bottom.0.store(b + 1, Relaxed);
        Ok(())
    }

    pub fn pop(&self) -> Option<Box<T>> {
        let q = &*self.q;
        let b = q.bottom.0.load(Relaxed) - 1;
        q.bottom.0.store(b, Relaxed);
        fence(SeqCst); // claim slot b before reading top (store -> load)
        let t = q.top.0.load(Relaxed);
        if t > b {
            q.bottom.0.store(b + 1, Relaxed); // was empty
            return None;
        }
        let p = q.slot(b).load(Relaxed);
        if t < b { return Some(unsafe { Box::from_raw(p) }); } // no thief can reach slot b
        // Last item: race the thieves for it.
        let won = q.top.0.compare_exchange(t, t + 1, SeqCst, Relaxed).is_ok();
        q.bottom.0.store(b + 1, Relaxed);
        if won { Some(unsafe { Box::from_raw(p) }) } else { None }
    }
}

impl<T> Stealer<T> {
    pub fn steal(&self) -> Steal<T> {
        let q = &*self.q;
        let t = q.top.0.load(Acquire);
        fence(SeqCst);
        let b = q.bottom.0.load(Acquire); // pairs with the owner's release fence in push
        if t >= b { return Steal::Empty; }
        let p = q.slot(t).load(Relaxed); // may be stale if t is old; then the CAS below fails
        if q.top.0.compare_exchange(t, t + 1, SeqCst, Relaxed).is_err() { return Steal::Retry; }
        Steal::Success(unsafe { Box::from_raw(p) })
    }
}

impl<T> Drop for Inner<T> {
    fn drop(&mut self) {
        let (t, b) = (*self.top.0.get_mut(), *self.bottom.0.get_mut());
        for i in t..b { unsafe { drop(Box::from_raw(self.slot(i).load(Relaxed))) } }
    }
}

Complexity and constants

• Push: two loads, one store, a release fence (free on x86). Order of 1-5 ns.
• Pop: one SeqCst fence (mfence or a locked op on x86, dmb ish on ARM), order of 5-20 ns; a CAS only when one item is left.
• Steal: reads two lines owned by the victim plus the task line, then a CAS: order of 100-300 ns cross-core. Steals are rare when tasks are plentiful.
• Expected steal attempts for fork-join with span T∞ on P workers: O(P·T∞).

Efficiency

• Cost: push is order of 1-5 ns (two loads, one store, a release fence that is free on x86). Pop is order of 5-20 ns (one SeqCst fence), with a CAS only for the last item. A steal is order of 100-300 ns cross-core (victim's two lines plus the task line, then a CAS) and is rare while tasks are plentiful. Memory: one pointer per slot per worker. Bound: coherence traffic on top and the thief's cache misses.
• Levers:
  • steal half of the victim's queue per CAS-protected batch (Go, Tokio) — the thief does not come straight back — long queues
  • LIFO slot for the newest task (Tokio, Go runnext) — cache-hot message-passing ping-pong — async runtimes (cap its use for fairness)
  • limit spinning thieves, then park on a futex or condvar — no CPU burn when idle — bursty load
  • fixed-size local ring with overflow to a global queue (256 slots in Go and Tokio) — no buffer growth or reclamation on the hot path — most workloads
  • random victim start, scan all workers once — spreads steal pressure — many workers
• Naive → standard → state of the art:
  • one shared MPMC queue · every task pays a contended CAS on the shared counter (order of 50-100 ns)
  • Chase-Lev deque, steal one task per CAS · order of 1-20 ns for the owner, 100-300 ns per steal
  • steal-half, LIFO slot, bounded local ring plus global injector · fewer steals per task and cache-hot local runs

Implementation notes

• Growth: when full, allocate a buffer twice as large, copy [top, bottom), publish the new buffer pointer; the old buffer must be freed with epoch-based reclamation because thieves may still read it (crossbeam-deque does this).
• Steal half (Go, Tokio): a thief takes about half the victim's tasks in one CAS-protected batch into its own queue, so it does not come back immediately.
• LIFO slot (Tokio, Go runnext): the most recently spawned task runs next on the same worker for cache locality (message-passing ping-pong); cap how often it is used to keep fairness.
• Global injector: tasks from outside the pool go to a shared queue; workers check it every N local tasks (Go: every 61 schedule ticks) to avoid starvation.
• Idle workers: limit spinning thieves (Go and Tokio allow at most about half of the busy workers to search), then park on a futex/condvar; wake one sleeper when new work appears and nobody is searching.
• Victim selection: random start index, then scan all workers once.

Pitfalls

• Dropping the SeqCst fence in pop or steal: owner and thief both take the last task (double execution), mostly visible on ARM but also possible on x86 (store→load reordering).
• Unsigned indices: bottom - 1 underflows at 0; use signed isize as above.
• Reading a plain (non-atomic) slot in steal with a fixed buffer: a stale thief races with the owner's overwrite; atomic slots or per-slot sequence numbers avoid it.
• Stealing one task at a time from a long queue: thieves contend on the victim's top line.
• LIFO-only execution of a task that spawns itself forever starves the rest of the queue.
• Blocking calls inside tasks stall a worker and its deque; offload blocking work (Tokio spawn_blocking).

Variants and alternatives

In production

Language runtimes and libraries: Rayon and crossbeam-deque (Rust, Chase-Lev with epoch-reclaimed growth), Tokio multi-threaded runtime (fixed 256-slot local queues, steal half, LIFO slot), Go runtime scheduler (per-P run queue of 256 + runnext, steal half), Java ForkJoinPool, smol's async-executor. Databases: HyPer's morsel-driven execution. Game engines: Bevy (via async-executor). Task libraries: Intel oneTBB, Taskflow, Cilk/OpenCilk.

Implementations

Sources

• David Chase, Yossi Lev, Dynamic Circular Work-Stealing Deque, SPAA 2005. paper
• Nhat Minh Lê, Antoniu Pop, Albert Cohen, Francesco Zappa Nardelli, Correct and Efficient Work-Stealing for Weak Memory Models, PPoPP 2013. paper
• Robert D. Blumofe, Charles E. Leiserson, Scheduling Multithreaded Computations by Work Stealing, Journal of the ACM 46(5), 1999. paper
• Matteo Frigo, Charles E. Leiserson, Keith H. Randall, The Implementation of the Cilk-5 Multithreaded Language, PLDI 1998. paper