When a task in a parallel runtime spawns a subtask, the runtime can either keep running the parent and leave the subtask to be stolen, or immediately run the subtask and leave the rest of the parent to be stolen. Describe both strategies and the consequences of choosing one over the other.

seniornice to knowfreq 17%

answer

who keeps the thread: parent or child?
child stealing = help-first, library-friendly
continuation stealing = work-first, sequential order
deque grows with spawn width vs depth
continuation may resume on another thread

basics

~20 s

Child stealing: the spawned subtask goes on the deque, the spawning thread keeps running the parent. Continuation stealing: the thread jumps straight into the subtask and puts the parent's remainder (its continuation) on the deque. Continuation stealing matches sequential order and bounds outstanding tasks, but needs runtime or compiler support to capture a continuation, so libraries usually do child stealing.

solid answer

~60 s

Child stealing (help-first). On spawn, the child task is pushed onto the local deque and the parent thread carries on. A thief may take the child. This is what a plain library can implement — a task object on a queue — but a loop that spawns N children before executing any of them puts all N on the deque, so outstanding tasks (and memory) grow with the loop's width rather than the recursion depth.

Continuation stealing (work-first). On spawn, the thread immediately executes the child, and what goes on the deque is the parent's continuation — the rest of the parent after the spawn point. Now a single worker running with no steals executes in exactly sequential order, outstanding tasks are bounded by depth, and the spawn fast path is close to a function call. The catch: capturing and resuming a continuation requires compiler support, CPS transformation, segmented/heap-allocated stacks, or coroutines, and the parent may resume on a different thread — which breaks any code assuming thread affinity or thread-local state across the spawn.

**Child stealing (help-first).** On spawn, the child task is pushed onto the local deque and the parent thread carries on. A thief may take the child. This is what a plain library can implement — a task object on a queue — but a loop that spawns N children before executing any of them puts all N on the deque, so outstanding tasks (and memory) grow with the loop's width rather than the recursion depth. **Continuation stealing (work-first).** On spawn, the thread *immediately* executes the child, and what goes on the deque is the parent's continuation — the rest of the parent after the spawn point. Now a single worker running with no steals executes in exactly sequential order, outstanding tasks are bounded by depth, and the spawn fast path is close to a function call. The catch: capturing and resuming a continuation requires compiler support, CPS transformation, segmented/heap-allocated stacks, or coroutines, and the parent may resume on a *different* thread — which breaks any code assuming thread affinity or thread-local state across the spawn.

code

text · 13 lines

text

task Parent():
    spawn Child()      # <-- decision point
    rest_of_parent()

CHILD STEALING (help-first)
  this thread: rest_of_parent()      deque: [Child]

CONTINUATION STEALING (work-first)
  this thread: Child()               deque: [rest_of_parent]

Loop spawning N children:
  child stealing        -> deque holds up to N pending tasks
  continuation stealing -> deque holds 1 item ("rest of loop")

go deeper

for a junior

Know that after a spawn one of the two pieces stays on the current thread and the other becomes stealable, and be able to say which is which for each strategy.

for a middle

Explain that child stealing puts the child on the queue and keeps running the parent, continuation stealing does the reverse, and note the queue-growth difference for wide loops.

for a senior

Add why continuation stealing gives sequential-order and space bounds, why it needs runtime support, and which real code it breaks (thread-locals, locks, thread-bound context).

for a principal

Reason about it as a platform choice: what capability the runtime must expose, what programming model contract you can then promise users, and how it interacts with granularity limits and affinity assumptions.

The decision point

When a task executing on a worker says "spawn X, then continue with Y", there are two pieces of runnable work at that instant: the new child X, and the remainder of the current task Y (its continuation). One of them keeps the current thread; the other goes on the deque where a thief can take it. Which one goes where is a real design fork with observable consequences.

Child stealing (also called help-first)

The spawn packages the child as a task object, pushes it on the local deque, and returns immediately; the current thread continues executing the parent. If nobody steals, the child is eventually popped by the same worker when the parent reaches a join or runs out of other work.

Properties:

Implementable as a plain library. A task is just an object with a run method; nothing in the language runtime needs to know about it. This is why nearly all library-level fork-join frameworks use it.
Deque growth follows the spawn width. A parent that spawns N children in a loop pushes N task objects before executing any of them. Memory for outstanding tasks is therefore proportional to the width of the spawn, and in a nested loop this can blow up. With deep recursion it is still fine, because each level only pushes one or two.
Order is inverted relative to sequential execution. The parent races ahead; children run later, possibly elsewhere.
The child is the stealable unit, and children near the leaves are small — so the thief may get a modest amount of work per steal.

Continuation stealing (also called work-first or parent stealing)

The spawn does the opposite: the current thread dives straight into the child, and the parent's continuation is what becomes stealable.

Properties:

A steal-free execution is exactly the sequential execution. If no thief ever intervenes, the program runs in the same order as the equivalent serial program: into the child, back out, on to the next statement. That is a strong debugging and reasoning property, and it is what makes the classic space bound (space on P workers within a constant factor of P times sequential space) hold.
Outstanding tasks are bounded by recursion depth, not spawn width. The loop that spawns N children never has N pending items: it spawns one, runs it, comes back, spawns the next. The stealable item is always "the rest of the loop".
The spawn fast path is nearly a function call, which lets the runtime tolerate much finer granularity.
The parent can resume on a different thread. Whoever steals the continuation is the thread that finishes the parent. Any code that assumed "the same thread runs this function from start to finish" — thread-local state, thread affinity, a lock held across the spawn, thread-bound identity such as a security or transaction context, stack-based bookkeeping — is now wrong.
It needs machinery. Capturing a continuation means either compiler support (Cilk-style), a CPS transformation, coroutines, segmented or heap-allocated stacks, or an interpreter/VM feature. A library that can only allocate objects and push them on a queue cannot do it. This is precisely why child stealing dominates library frameworks and continuation stealing appears in language- or runtime-level schedulers.

How to choose, and what it changes for the caller

If you are using a runtime rather than writing one, three practical consequences follow.

Under child stealing, spawn shape matters. Prefer recursive binary splitting over a flat loop that spawns thousands of tasks up front, because the recursive shape keeps the deque shallow and gives thieves large subtrees near the root.
Under continuation stealing, thread identity is not stable across a spawn. Do not stash state in thread-locals across spawn points and do not hold a thread-owned lock across one.
Both are still greedy schedulers. The completion-time argument is unchanged; what differs is memory behavior, the size of the stealable unit, and how faithfully a run resembles the sequential program.

A useful mental check

Ask: "after the spawn statement, which piece of work does this thread execute next?" Child stealing answers "the parent's next statement"; continuation stealing answers "the child's first statement". Everything else — deque growth, sequential-order equivalence, thread-affinity hazards, implementation cost — falls out of that one answer.

## The decision point When a task executing on a worker says "spawn X, then continue with Y", there are two pieces of runnable work at that instant: the new child X, and the remainder of the current task Y (its **continuation**). One of them keeps the current thread; the other goes on the deque where a thief can take it. Which one goes where is a real design fork with observable consequences. ## Child stealing (also called help-first) The spawn packages the child as a task object, pushes it on the local deque, and returns immediately; the current thread continues executing the parent. If nobody steals, the child is eventually popped by the same worker when the parent reaches a join or runs out of other work. Properties: - **Implementable as a plain library.** A task is just an object with a run method; nothing in the language runtime needs to know about it. This is why nearly all library-level fork-join frameworks use it. - **Deque growth follows the spawn width.** A parent that spawns N children in a loop pushes N task objects before executing any of them. Memory for outstanding tasks is therefore proportional to the *width* of the spawn, and in a nested loop this can blow up. With deep recursion it is still fine, because each level only pushes one or two. - **Order is inverted relative to sequential execution.** The parent races ahead; children run later, possibly elsewhere. - **The child is the stealable unit,** and children near the leaves are small — so the thief may get a modest amount of work per steal. ## Continuation stealing (also called work-first or parent stealing) The spawn does the opposite: the current thread dives straight into the child, and the parent's continuation is what becomes stealable. Properties: - **A steal-free execution is exactly the sequential execution.** If no thief ever intervenes, the program runs in the same order as the equivalent serial program: into the child, back out, on to the next statement. That is a strong debugging and reasoning property, and it is what makes the classic space bound (space on P workers within a constant factor of P times sequential space) hold. - **Outstanding tasks are bounded by recursion depth, not spawn width.** The loop that spawns N children never has N pending items: it spawns one, runs it, comes back, spawns the next. The stealable item is always "the rest of the loop". - **The spawn fast path is nearly a function call**, which lets the runtime tolerate much finer granularity. - **The parent can resume on a different thread.** Whoever steals the continuation is the thread that finishes the parent. Any code that assumed "the same thread runs this function from start to finish" — thread-local state, thread affinity, a lock held across the spawn, thread-bound identity such as a security or transaction context, stack-based bookkeeping — is now wrong. - **It needs machinery.** Capturing a continuation means either compiler support (Cilk-style), a CPS transformation, coroutines, segmented or heap-allocated stacks, or an interpreter/VM feature. A library that can only allocate objects and push them on a queue cannot do it. This is precisely why child stealing dominates library frameworks and continuation stealing appears in language- or runtime-level schedulers. ## How to choose, and what it changes for the caller If you are *using* a runtime rather than writing one, three practical consequences follow. 1. **Under child stealing, spawn shape matters.** Prefer recursive binary splitting over a flat loop that spawns thousands of tasks up front, because the recursive shape keeps the deque shallow and gives thieves large subtrees near the root. 2. **Under continuation stealing, thread identity is not stable across a spawn.** Do not stash state in thread-locals across spawn points and do not hold a thread-owned lock across one. 3. **Both are still greedy schedulers.** The completion-time argument is unchanged; what differs is memory behavior, the size of the stealable unit, and how faithfully a run resembles the sequential program. ## A useful mental check Ask: "after the spawn statement, which piece of work does *this* thread execute next?" Child stealing answers "the parent's next statement"; continuation stealing answers "the child's first statement". Everything else — deque growth, sequential-order equivalence, thread-affinity hazards, implementation cost — falls out of that one answer.

Why do library-level task frameworks almost always use child stealing?
Because a library can create an object representing a child task and push it on a queue, but it cannot capture the middle of an executing function and hand it to another thread. Doing that requires compiler transformation, coroutines, or non-standard stack management, which is a language-runtime capability rather than a library one. Child stealing trades the space and ordering benefits for being implementable in ordinary code.
What kind of code breaks specifically under continuation stealing but not under child stealing?
Anything that assumes one thread runs a function from beginning to end. Thread-local variables read after a spawn may belong to a different thread; a lock acquired before the spawn and released after may be released by a thread that never acquired it; thread-bound context such as a request, transaction, or security principal silently changes identity. These bugs are invisible in steal-free runs and appear only under load, which makes them hard to reproduce.

saying these in an interview costs you the question

Treating the two as a micro-optimization with no observable difference to user code
Saying continuation stealing is always better without mentioning that it needs runtime or compiler support
Missing that child stealing makes pending-task memory scale with how many children a loop spawns
Assuming the parent always resumes on the thread that spawned the child
Confusing this choice with the LIFO/FIFO deque-end choice — they are independent decisions

When a task in a parallel runtime spawns a subtask, the runtime can either keep running the parent and leave the subtask to be stolen, or immediately run the subtask and leave the rest of the parent to be stolen. Describe both strategies and the consequences of choosing one over the other.

§ answer

basics

solid answer

code

§ go deeper

▾level notes4 levels

▾deep dive~4 min

The decision point

Child stealing (also called help-first)

Continuation stealing (also called work-first or parent stealing)

How to choose, and what it changes for the caller

A useful mental check

▾common follow-ups2 questions

▾red flags5 flags

§ context

▾related questions4 questions

▾related topics4 topics

The decision point

Child stealing (also called help-first)

Continuation stealing (also called work-first or parent stealing)

How to choose, and what it changes for the caller

A useful mental check

answer

go deeper

context