Growable Stacks and Reduction Budgets in Coroutine Runtimes

A coroutine needs its own control context: its own stack of pending calls, its own notion of where execution resumes. The straightforward implementation gives each coroutine a native thread, which makes context switching the kernel’s problem and each coroutine cost a full thread stack, which on common systems means megabytes of virtual address space reserved per thread by default. A language that wants a hundred thousand coroutines cannot afford that, so implementations either allocate a small stack per coroutine and grow it on demand, or avoid a stack per coroutine entirely by keeping the coroutine’s state on the heap. The two approaches have different costs at suspension, at growth, and at the boundary where a coroutine calls into native code.

Segmented stacks

A segmented stack is a linked list of fixed-size stack segments. A coroutine starts with one small segment, typically a few kilobytes. When a function’s prologue would exceed the current segment, the runtime allocates a new segment, links it to the current one, and continues executing on it. When the function returns, the runtime detects that the current segment is no longer needed and unlinks it.

The detection is the hard part. A return has to know whether it is returning past the start of the current segment, which means the segment’s bounds must be checked at every return, or the code must be compiled so that returns into a previous segment are recognizable. Implementations use a guard page: the segment’s end is followed by a page the kernel marks inaccessible, and touching it raises a signal. The signal handler then allocates a new segment and resumes execution at the faulting instruction, with the stack pointer now pointing into the new segment.

+-----------+     +-----------+     +-----------+
| segment 0 | --> | segment 1 | --> | segment 2 |   (grows downward, links to parent)
+-----------+     +-----------+     +-----------+
     ^ current sp

The guard-page approach makes the overflow check free on the fast path, since an ordinary call that fits needs no check at all. The cost is a signal on every segment transition, and signals are expensive: the kernel must save and restore state, and the handler runs on an alternate stack. For code that crosses segments frequently, the cost dominates. The other cost is that a segmented stack is not contiguous, so any operation that needs a contiguous view, such as passing a pointer to a native function that walks the stack, cannot have one.

The Go runtime’s historical implementation of growable stacks used a variant of this design and later moved to a copying scheme precisely because the segment-crossing cost and the pointer invalidation problems were worse than the alternative. The relevant property is that a stack that can move invalidates every pointer into it, which means the runtime must find and adjust them, which in turn means the compiler must describe them.

Copied stacks

A copied stack keeps the stack contiguous and grows it by allocating a larger region and copying the old contents into the new one. The pointer adjustment is the same problem a moving collector faces: the runtime knows the layout of every frame from the stack maps, so it can walk the copied region and rewrite the pointers that referred to the old stack.

old: [ frame A ][ frame B ][ frame C ]        capacity 4 KiB
                    |
                    v  grow
new: [ frame A ][ frame B ][ frame C ][ free ]  capacity 8 KiB, pointers rewritten

The advantage over segments is that the fast path is a single bounds check against a limit held in a register or a thread-local, and the slow path is rare. The disadvantage is the copy: growing a stack that is already large copies all of it, so the cost of growth is proportional to the current depth, and repeated growth in a deep recursion is quadratic in the final depth. Implementations mitigate this by doubling the capacity, which makes the total copying work linear in the final size.

The deeper disadvantage is that pointers into the stack cannot escape to code the runtime does not control. A native function that receives a pointer to a stack-allocated buffer will see that pointer become stale after a growth. This is why runtimes with movable stacks forbid passing stack pointers to native code, or pin the stack for the duration of the call. Languages that expose the address of a local to a foreign function must either accept the restriction or disable stack movement for the frames involved.

One stack per coroutine versus one stack total

An alternative avoids per-coroutine stacks altogether. The coroutine’s state, including the values of its locals at the suspension point, is stored in a heap-allocated object, and the coroutine runs on the same native stack as everything else when it is resumed. Suspending copies the live part of the native stack into the coroutine object and restores it on resume.

This is the “one stack, copied on switch” design. Its cost per switch is proportional to the live stack depth, which is small when coroutines suspend near the top of their call chain and large when they suspend deep. It has the advantage that the number of coroutines is limited only by heap, and that no coroutine reserves address space while suspended. It has the disadvantage that a suspension point must be a point the runtime can describe, since the copy needs to know the frame layout, and that the copy itself is a memory-to-memory operation on every switch.

Lua’s coroutines use a different structure: each coroutine has its own stack, allocated from the runtime’s own stack pool, and a switch swaps the runtime’s notion of the current stack rather than copying. Because the Lua stack is the VM’s value stack rather than the host’s call stack, as the register bytecode article describes, and because the VM’s call frames are explicit structures, the switch is a pointer swap plus the restoration of the saved register state. The cost per switch is constant and small, and the cost per coroutine is the initial stack allocation, which the implementation can size and reuse.

The design is available because the interpreter does not use the host stack for Lua calls. A tree-walking interpreter written in C would use the host stack, and a coroutine implemented on top of it would have to copy or switch host stacks, which is what the ucontext family of functions does. Those functions save and restore the machine’s register state, including the stack pointer, and they are the portable way to implement a user-level context switch in C. Their cost is a system call on some platforms and a signal-based implementation on others, and the POSIX specification marks them as obsolescent, which is why runtimes that care about portability implement their own assembly.

Reduction budgets and preemption

A scheduler that runs coroutines on one thread must decide when to switch. A coroutine that loops forever without suspending would starve every other coroutine, so the runtime needs a way to take control back.

The mechanism is a countdown. Each coroutine is given a budget of “reductions”, where a reduction is an abstract unit of work such as one function call or one loop iteration. The interpreter decrements the counter as it executes, and when the counter reaches zero, it yields to the scheduler, which resets the counter and picks the next runnable coroutine. The budget is not a wall-clock timeout; it is a bound on the amount of work, which makes the schedule deterministic given the same program and the same initial budgets.

/* Interpreter loop with a reduction countdown. */
while (1) {
    if (--state->reductions <= 0) {
        state->reductions = REDUCTIONS_PER_SLICE;
        if (yield_to_scheduler(state) != RESUMED)   /* may switch to another coroutine */
            break;
    }
    dispatch_next_instruction(state);
}

The placement of the decrement determines what counts as work. Decrementing per instruction makes the budget fine-grained and the counter hot; decrementing only at calls makes the budget coarse and lets a single long loop run unbounded, because nothing inside the loop decrements. Decrementing at calls and at loop back edges bounds the work between two decrements to the length of one loop body, and that is the placement most interpreters choose. The counter’s update is a subtract and a compare, which is cheap enough to sit in the interpreter’s dispatch path, though it is not free: it adds an instruction to a loop that might otherwise be three.

A compiled tier has a harder problem. The compiler must insert the same check, which means it must know where the loop back edges are and must not optimize the check away. Since the counter lives in a structure the compiled code can address, the check is a load, a subtract, a store, and a branch. The optimizer must treat the load as volatile in effect, or it will hoist the check out of the loop and lose preemption entirely.

What preemption costs the language

A preemption point is a safepoint in the collector’s sense and a yield point in the scheduler’s sense, and the two requirements interact. At a preemption point the runtime must be able to suspend the coroutine, which means its state must be describable, which means the same stack maps that the collector uses must also serve the scheduler. A runtime that can suspend a coroutine at an arbitrary instruction must be able to save and restore the full machine state, which is why preemptive coroutines usually run on separate native threads or use a signal-based mechanism.

The alternative is cooperative scheduling: the coroutine yields only at explicit suspension points, and the programmer is responsible for not monopolizing the scheduler. This is simpler and cheaper, and it is what most coroutine libraries offer. Its failure mode is a coroutine that calls into a blocking operation or runs a long computation without yielding, which stalls everything else. The budget mechanism exists to convert that failure into a bounded delay, at the cost of a check in the interpreter’s hot path.

The final interaction is with the collector. A suspended coroutine’s stack is a root set, and the collector must scan every suspended stack as well as the running one. For a runtime with many coroutines, that means the root set is large and the collector’s pause time scales with the total number of live stacks, not with the running program’s depth. Implementations that support very large coroutine counts usually pair the design with an incremental or concurrent collector, so that scanning the suspended stacks does not stop the world.