Stackful and Stackless Coroutines: Where Suspension Is Allowed

A coroutine is a computation that can be suspended and resumed. The definition says nothing about where the suspension may occur, and that omission hides the decision that separates the two families of implementations.

A stackful coroutine owns a stack. It can suspend from any point in any call chain, because its frames are on that stack and remain there while it is suspended. A stackless coroutine does not own a stack. The compiler rewrites each suspendable function into a state machine whose local variables live in a heap-allocated frame, and suspension is legal only at the points the rewrite marked. Between those points the function is an ordinary function with an ordinary stack frame, which disappears when it returns.

The two designs are both called coroutines and are not interchangeable. The choice determines the memory cost of a suspended task, the set of functions a task may call, and whether a language can adopt the feature without a compiler rewrite.

The state machine transform

Consider a function that awaits an operation and then uses the result. The compiler splits it at the await into a state enum, with one variant per suspension point, and a resume function that switches on the state.

use std::pin::Pin;
use std::task::{Context, Poll};

// What the compiler generates for an async fn that awaits twice:
// one enum variant per suspension point, all locals in the frame.
#[derive(Clone, Copy)]          /* the match below reads the discriminant by value */
enum Phase { First, Second, Done }

struct Frame {
    phase: Phase,
    inner: Pin<Box<dyn Future<Output = u32>>>,
    acc: u32,
}

impl Future for Frame {
    type Output = u32;

    fn poll(mut self: Pin<&mut Self>, cx: &mut Context<'_>) -> Poll<u32> {
        let this = &mut *self;
        loop {
            match this.phase {
                Phase::First => {
                    match this.inner.as_mut().poll(cx) {
                        Poll::Pending => return Poll::Pending,
                        Poll::Ready(v) => { this.acc = v; this.phase = Phase::Second; }
                    }
                }
                Phase::Second => {
                    this.acc += 1;
                    this.phase = Phase::Done;
                }
                Phase::Done => return Poll::Ready(this.acc),
            }
        }
    }
}

Two properties follow from this shape. The frame holds every local that is live at a suspension point, and the compiler’s liveness analysis decides which fields to keep, so the frame’s size is the maximum over all states. A local that is in scope across an await is held in the frame even if the code never reads it again, which is why a value that is expensive to keep alive, such as a locked buffer, should be dropped before the await rather than after it. A function with a large buffer and many branches produces a large frame even if most of the branches do not use the buffer concurrently. The frame is allocated when the future is created, before the first poll, so the allocation happens whether or not the future ever suspends.

The second property is that the resume function returns to its caller at every suspension. There is no stack to preserve, so the call stack is empty between polls; the runtime’s executor holds the frame and calls poll again later. The whole call chain from the task’s entry point to the suspension point has been flattened into the frame, which is why a stack trace of a suspended stackless task shows the executor and the frame but not the logical call chain.

Stackless designs therefore pay per-task heap memory proportional to the live variables, and they pay nothing for the call depth. A task that recurses a thousand levels before awaiting needs a frame that holds whatever the recursion keeps live, but not a thousand stack frames.

The stackful alternative

A stackful coroutine has a stack segment allocated when the coroutine is created, and a switch saves the register set and the stack pointer, then restores another. Suspension from inside a library call works because the library’s frames are on the coroutine’s stack; the switch does not need to know or care what they are.

The cost is the stack itself. Runtimes choose between a fixed size, a growable stack that copies on overflow, and segmented stacks. A fixed size must be chosen for the worst case the program might reach, and the worst case is not knowable for a general-purpose language; the usual compromise is a few tens of kilobytes per task and an overflow check that aborts. A growable stack costs a check in every function prologue and a copy when it grows, which requires the runtime to know every pointer into the stack so it can be adjusted, a requirement that forces precise stack maps and therefore cooperation from the compiler.

The second cost is that a stackful coroutine’s stack is a scarce resource the runtime must recycle. Creating and destroying a coroutine per request means allocating and freeing a stack per request; the usual optimisation is a free list of stacks, which turns the allocation into a pop from a per-thread list. That works when the stacks are all the same size, and it is why the fixed-size design, despite its overflow risk, is the one that appears in runtimes that create many short-lived tasks.

Suspension across foreign frames

The decisive practical difference is what happens when a coroutine calls code the compiler did not compile.

A stackless coroutine cannot suspend inside a foreign function. The foreign function has an ordinary frame on the machine stack, and that frame vanishes when the function returns; there is no state machine to resume into. A stackless task that calls a blocking C function therefore blocks the carrier thread for the whole duration of the call, exactly as if it were a plain thread. This is not a performance issue that can be tuned away; it is a consequence of where the frame lives.

A stackful coroutine can suspend inside a foreign function if it can arrange for the call to be interruptible. In practice that means the foreign function must call back into the runtime at the point where it would block, which requires either a hook the runtime installs or a wrapper the programmer writes. A C library that calls read internally does not know about the runtime and cannot yield; the runtime can only prevent the damage by running the call on a separate thread.

This is the constraint that determines which languages can adopt which design. A language with its own compiler and its own runtime can implement stackful coroutines, because it can generate stack maps and grow stacks. A language whose functions are compiled to native code by an external toolchain can implement stackless coroutines more easily, because the transform is local to the compiler front end and needs no runtime support for stacks. A language that wants to call arbitrary C without blocking must either accept the blocking or use threads.

Resumption cost and the shape of a task

A stackless resumption is a call to poll, a switch on a small integer, and a branch into the appropriate arm. The state is in the frame, which the executor holds; the switch does not touch the machine stack beyond the call’s own frame. Cost is a few tens of instructions plus the branch misprediction that the state switch usually causes, because the executor calls poll for many different futures and the indirect branch predictor has no stable history for any of them.

A stackful switch is a save and restore of the callee-saved registers and a stack pointer swap, followed by a return into the resumed coroutine. On x86-64 that is around a dozen register moves and no kernel involvement. The cost is comparable to the stackless call, and the difference in practice comes from cache behaviour rather than instruction count: a stackful switch touches a different region of stack memory each time, while a stackless resume touches the frame the executor just handled.

The deeper difference is in what a task can express. A stackful task can suspend inside a for loop, inside a try block with cleanup, inside a callback invoked by a library, and inside a recursive descent parser. A stackless task can do all of these only if every one of those constructs was compiled by the same compiler with the transform applied, and only if the suspension point is syntactically reachable from an async context. Loops and recursion are fine; foreign callbacks are not.

Memory per task, measured in orders of magnitude

A stackless task’s frame is the size of its live variables. For a task that reads a small request and writes a small response, that can be a few hundred bytes. A task that holds a 64 KiB buffer across an await pays 64 KiB whether or not the await ever suspends, and a runtime that creates a million such tasks pays 64 GiB.

A stackful task pays for its stack. A fixed 8 KiB stack for a million tasks is 8 GiB, and the actual usage is likely a few hundred bytes per task, so most of that memory is reserved and untouched: virtual address space rather than resident pages, which matters for the 32-bit case and not much for 64-bit. A growable stack pays a small initial stack plus a copy on growth, so the resident cost tracks usage at the price of the check.

Neither design is uniformly cheaper. Stackless wins when tasks are numerous and shallow; stackful wins when tasks are deep or call into code that cannot be transformed. The relevant question for a runtime is the distribution of task depths, which is a property of the application rather than the language.

Hybrid designs and their seams

Several runtimes mix the two. A stackful runtime may expose a stackless-looking API by generating state machines at the boundary; a stackless runtime may run blocking calls on a pool of stackful threads. The seams are where the problems live: a stackless task that hands work to a blocking pool must copy its data out of the frame, because the frame may move and the pool thread has no way to know when it is safe to touch it. A stackful task that calls a stackless API must have its own stack, so the runtime cannot elide the stack for tasks that never call such an API.

The choice also interacts with cancellation. A stackless task is cancelled by dropping its frame, which runs destructors for the live locals in the current state; a stackful task is cancelled by unwinding its stack or by abandoning it, and abandoning leaks whatever the frames owned. That interaction is the subject of cancellation and drop at suspension points, and it is the place where the memory model of the coroutine becomes visible to the programmer.

The stack question also decides how many tasks a runtime can hold. A runtime that allocates a fixed stack per task must choose the size before it knows the workload, while a runtime that stores frames must size them from the code. The scheduling consequences of the choice, including what a blocked task costs, are worked out in green threads and user-space switching.