Eight workers, one shared task queue. Every worker takes from the same place, so every worker contends on the same lock — eight cores fighting over one cache line, thousands of times per second.
And with recursive work it is worse than contention. A divide-and-conquer task spawns subtasks, which spawn subtasks, so the queue is hammered constantly.
The pattern
Give each worker its own double-ended queue. Two rules:
- A worker pushes and pops its own end. No synchronisation — nobody else touches that end.
- An idle worker steals from the far end of a random victim’s deque.
A has spawned five subtasks. B has nothing.
Cache locality is not an accident either
A worker pops the task it pushed most recently. That task’s data is the data the worker just touched, so it is still in L1.
This is depth-first locally — good for cache — and breadth-first when stealing — good for load balance. Getting both from one data structure is why the design has held up since Cilk introduced it in 1994.
Where you already use it
Java’s ForkJoinPool, which is also the default for parallel streams and
CompletableFuture.
Go’s scheduler. Each OS thread has a local run queue of goroutines and steals when empty. It also drains the global queue occasionally, so a goroutine cannot be starved by a busy local queue.
Rust’s Rayon and .NET’s thread pool. Tokio for async tasks.
If you use any of these, you are relying on work stealing already.
Where it is a poor fit
Uniform, independent tasks. If every task is the same size and nothing spawns subtasks, a plain shared queue is simpler and just as fast — the stealing machinery has nothing to exploit.
Tasks that block. A worker blocked on I/O holds its deque hostage. Java’s
ManagedBlocker exists to compensate by temporarily adding a thread, which
tells you how awkward the case is.