Work Stealing and the Cost of Task Granularity

A fixed partition of work across cores is optimal until the work turns out to be uneven. One partition holds a thousand items that each take a microsecond and one that takes ten milliseconds, and every other core is idle while one finishes. The imbalance is invisible at the moment the partition is computed and unavoidable in general, because the duration of a task is not known until it runs.

Work stealing is the standard resolution. Each worker keeps a deque of tasks it has created but not yet started. When a worker runs out, it takes a task from another worker’s deque and runs it. No global scheduler, no central queue, no static assignment. The design’s properties come almost entirely from two choices: which end of the deque the owner uses, and which end the thief takes.

Owner at one end, thief at the other

A worker pushes new tasks and pops tasks to run from the same end, conventionally the bottom. A thief takes from the opposite end, the top. This is not an arbitrary convention; it is what makes the common case cheap and the rare case correct.

The owner’s operations touch the end of the deque it most recently modified. That entry is in the owner’s cache, and the deque’s bottom pointer is written only by the owner, so push and pop need no atomic operation on the fast path, only a release store when publishing. The thief’s operation touches the other end, which the owner has not accessed recently. A thief that takes the oldest task also tends to steal a large task, because the oldest tasks are the ones closest to the root of the computation and therefore have the most work beneath them. Stealing large tasks means the thief stays busy for a long time and does not come back often.

The alternative, both ends at the same point, is what a flat LIFO stack with theft would do, and it fails on both counts: owner and thief contend on the same cache line, so every operation needs a compare-and-swap, and the thief gets the newest task, which is likely the smallest. The two-ended design is the entire trick.

/* Owner side: non-atomic push/pop at the bottom; thief takes from the top. */
struct deque {
    atomic_size_t top;      /* thieves modify */
    size_t        bottom;   /* owner only */
    atomic_size_t size;     /* published for thieves */
    task_t       *slots;
};

int owner_pop(struct deque *d, task_t **out) {
    size_t sz = atomic_load_explicit(&d->size, memory_order_relaxed);
    if (sz == 0) return 0;
    size_t b = d->bottom - 1;          /* private: no CAS needed */
    if (atomic_load_explicit(&d->top, memory_order_relaxed) == b) {
        /* last element: a thief may be racing for it */
        if (!atomic_compare_exchange_strong_explicit(&d->top, &b, b + 1,
                memory_order_seq_cst, memory_order_relaxed))
            return 0;                  /* thief won; deque is empty */
    }
    d->bottom = b;
    *out = d->slots[b];
    atomic_store_explicit(&d->size, b - atomic_load(&d->top), memory_order_release);
    return 1;
}

The special case for the last element is the part that is wrong in most hand-written implementations. When one task remains, owner and thief genuinely race, and the owner must perform a compare-and-swap on the shared top index to claim it. The size field is what lets a thief check emptiness without reading two indices that may be mid-update.

Termination is a distributed property

With no central queue, no worker knows whether the computation is finished. A worker that finds its own deque empty and finds no victim with work available cannot conclude that the work is done: another worker might be about to push a new task.

The usual termination protocol is a sense-reversing barrier combined with a flag. When a worker finds nothing to steal after probing every other deque, it signals that it is idle and enters the barrier. If every worker reaches the barrier, the computation is over. If the barrier is released by one worker finding a task, the idle workers resume probing. The correctness argument is that any task must have a parent that either is still executing or has been pushed to some deque; a worker with nothing to do and no task available anywhere means every task is complete.

The consequence for behaviour is a probabilistic idle pattern. A worker does not go idle once and stay idle; it retries, sleeps a short randomised interval, and retries. The randomised interval matters because without it all idle workers probe the same victim at the same instant.

The task-stealing measurement that follows is that the number of steals is roughly proportional to the number of imbalance events, not to the number of tasks. A computation with a million tasks and ten workers may perform a few thousand steals, each of which costs a lock or a compare-and-swap on the victim’s deque plus the transfer of a task descriptor. That overhead is negligible against the work performed, provided the tasks are large enough.

Granularity is the whole decision

The cost of a steal is on the order of the cost of a contended atomic operation plus a wakeup if the thief had to sleep: a few hundred nanoseconds to a few microseconds. The benefit of a steal is that a worker receives a task that would otherwise have waited.

If a task takes 100 nanoseconds, a steal that moves one task performs 100 nanoseconds of work for a few microseconds of overhead. The computation spends almost all its time in the scheduler. The break-even point is a task that takes tens of microseconds or more; the practical guidance is that tasks should be large enough that the work per task is at least two orders of magnitude above the steal cost, and the specific value depends on the machine.

This gives the rule for decomposing work: do not divide to the leaves. A recursive decomposition should stop at a threshold and process the remaining subrange with a loop, because the recursion’s purpose is to create enough tasks for every worker and no more. Beyond the point where the task count exceeds the worker count by a healthy factor, additional tasks buy no further parallelism and cost scheduling overhead on every task.

Task duration	Steals per unit work	Effect
~100 ns	thousands	Scheduler dominates; parallel slowdown
~10 µs	hundreds	Stealing visible but tolerable
~1 ms	tens	Negligible overhead; imbalance absorbed
~100 ms	few	Poor imbalance absorption; long tail

The last row is the other failure. Tasks that are too large make stealing too rare to help: the thief takes one task and the imbalance remains, now distributed differently. A single task that takes 100 milliseconds dominates the total runtime, and if it starts at the end of the computation, every other worker is idle for that time. The available parallelism is a function of task count, and granularity must be small enough that the largest task is a small fraction of the total.

Where the locality assumption breaks

The design assumes that a task’s data was last touched by the worker that created it, or by an ancestor of that worker, and that executing the task on the same core reuses those cache lines. The assumption is mostly right, and it is why the owner end is used for popping.

It breaks in two places. First, a stolen task runs on a different core than its data, so its memory accesses are remote. The cost is not merely a cache miss; the line may be modified in the victim’s cache and must be transferred. For a task with a working set that fits in the victim’s L2, the transfer cost can exceed the task’s compute time, which means stealing small locality-sensitive tasks is worse than leaving the core idle. This is an argument for granularity again, from a different direction.

Second, the deque structure itself has a coherence cost. The owner writes the bottom index and the size; thieves read the size and write the top. If the top and bottom indices share a cache line, every owner push invalidates the thieves’ copy of the size, and every thief read forces the owner’s line clean. The indices must be padded apart, and the structure is one of the most common places where false sharing costs more than the algorithm saves.

A third effect appears on machines with more workers than hardware threads. A thief that finds work must wake a sleeping worker or take the task itself, and the scheduler’s choice interacts with the affinitised locality. Simpler implementations let any idle worker steal for itself, which avoids the wakeup entirely and keeps the work local to whatever core is currently running.

When stealing beats a shared queue

The alternative to work stealing is a single shared queue from which all workers take tasks. It is simpler and it balances better, and it has one decisive disadvantage: every take is a contended operation on one data structure, which serializes at a rate of one dequeue per atomic operation. With a global queue, throughput is capped by the queue’s cost, and every worker competes for the same cache line whenever it looks for work.

Work stealing distributes the point of contention across as many deques as there are workers, and the common case touches only the local deque. Contention appears only when a worker is idle, and idle workers are by definition not consuming capacity. The design trades a rare expensive operation for a common free one, which is generally the right trade in a scheduler.

The technique composes with batching: a stolen task is a batch of work, which is what makes the steal cost negligible. It also composes with the backpressure question, since a deque per worker with no bound is a queue per worker with no bound, and a computation that generates tasks faster than it consumes them will grow deques without limit. Where tasks can be generated in unbounded quantity, the bound belongs on the generator, in the sense described in Bounded Queues and Backpressure as Throughput Control. The lock-free structures that make stealing cheap under contention are treated in Compare-and-Swap Retry Loops Under Contention.