What are the benefits of stackful vs. stackless coroutines?

Question

Many languages that use async nowadays are implemented via stackless coroutines. That is, in a language like Python or Javascript, when you await an expression, that await returns to the caller, returning the minimal amount of information needed to resume the function later. The caller can, in turn, await that, creating a sort of "async stack" separate from the traditional call stack.

Some languages, such as Lua, have stackful coroutines. The coroutine has its own call stack, possibly distinct from its creator. At any point during the coroutine's execution, the whole coroutine can be suspended, which returns to the original creator an object (including the coroutine's call stack) with information about how to resume the entire thing. In Lua, a function need not be marked as async, and an await call will suspend the entire coroutine, not just the enclosing function.

What are the pros and cons of these two approaches?

Answer 1

Stackful

Here are some pros:

1. More control. There is more control over the execution state which lets us have more flexible coroutine interactions and more complicated control structures.
2. Compatibility. They can more easily integrate with another codebase. This allows sychronized programming much easier.

Here are some cons:

1. Complexity and learning. They are more complex and as such harder to learn. It can also make maintenance and debugging more challenging.
2. Bad performance. The need for stack preservation and manipulation can deal a hit to your performance.

Stackless

Here are some pros:

1. Simplicity. The code is much cleaner and more readable.
2. Performance. They rarely cause performance issues and in some cases help performance by reducing suspension overhead and making more efficient scheduling.

Here are some cons:

1. Less control. There is less control over your execution state because you are relying on a (generally external) event loop or scheduler to manage it. This can restrict you from certain things.
2. Compatibility problems. A bunch of codebases don't work with stackless and require extensive work in order to make it compatible.

Answer 2

Disclaimer: There are multiple implementation techniques for both stackful and stackless coroutines, each with their own strengths/weaknesses. I do not promise to consider all possible implementations.

Memory Allocation

A separate stack typically needs to be allocated for each coroutine; this is fine for a long-lived one, but costly for rapid-fire one-off coroutines. It's even worse for languages where each stack frame is allocated separately.

On the other hand, no memory allocation is necessary for stackless coroutines, though certain implementations do allocate regardless (C#, for example).

Memory Consumption

A separate stack generally consumes more memory.

• Go: the compiler does not "prune" a stack frame before calling the next function, so "junk" accumulates at each frame, and the stack also typically features some "excess" capacity, to avoid constantly allocating/deallocating.

On the other hand, stackless coroutines tend to boil down to (nested) state machines, and only variables required across suspension points are saved, naturally trimming them down on the go.

Memory Cache (Misses)

A separate stack is less likely to have its current stack frame in cache, whereas a stackless coroutine reuses the existing (already in cache) stack.

Suspension/Resumption Performance

Suspending or resuming a stackful coroutine is generally O(1), though not lightweight:

• Go: registers need be saved, then the stack pointer switched to that of the new coroutine, and its own registers restored.

On the other hand, suspending or resuming a stackless coroutine is generally O(N) where N is the number of stack frames to suspend or resume. Each step is typically lightweight, but combined they may outweigh the heavier O(1) cost of a stackful coroutine.

Different situations will favor one strategy over another.

Suspension/Resumption FFI

A stackful coroutine may be FFI compatible. For example, it is possible to call C code from Go code, then call Go code from the C code, and suspend there, thus suspending the C stack frames even though the C compiler was not even aware that suspension was a possibility.

It is not typically possible to suspend a stackless coroutine with foreign stack frames in the middle, as the compiler of the stackless coroutine language does not know how to pack the state of those frames.

Debugging

It is trivial for a debugger to display the stack of a stackful coroutine, as it's usually just a regular stack as far as the language implementation is concerned.

On the other hand, it is nigh impossible to do so for a stackless coroutine. Any stack information prior to the last resumption is generally lost -- they did not survive the transformation to state machine and back -- and the caller of the resumption may be a completely different caller from the original one, possibly even on a different thread.

Optimization

Stackful coroutines are lightweight threads, and typically not optimized away, but each individual stack can be optimized to the full extent of the compiler capabilities.

Stackless coroutines implemented as (nested) state-machines in the front-end are trivially optimized away -- when possible -- via the regular inlining/constant propagation passes of an optimizer. On the other hand, the fact that the front-end performs the lowering may inhibit optimizing each stack frame (across suspension points) such as introducing temporary variables (CSE) or vectorizing.

Stackless coroutines implemented as (nested) state-machines in the back-end (C++) are harder to optimize away -- due to the presence of user-defined dynamic code -- though the possibility has been demonstrated, on the other hand each stack frame may be optimized fully (on its own).

Different situations will favor one strategy over another.

Answer 3

"Stackful" coroutines, as implemented to today in Go and Java, are a generally superior technology that requires lower-level control over the execution environment.

They have two huge advantages over stackless:

• You don't need to have 2 kinds of functions in your program (the red/blue function problem)
• All the overhead is associated with suspending + resuming. They perform significantly better than stackless when a fair amount of code is executed between suspensions, because with stackless coroutines, your code is transformed into a slower form, and you pay for the ability to suspend, even when you don't suspend.

If you can't copy/move stacks around, or significantly change how they work, then stackless coroutines are your only choice. You'll have to do violence to your language by introducing async/await, and they will be a lot slower in most cases. There are a couple advantages, though:

• you can call C-style functions that might block or call-back into your code. This causes problems for stackful coroutines, because when a function like this is on the stack, anything may have valid pointers to stack-based objects, so you can't suspend and resume later with the stack in different memory. There are ways around this in language design, but it's a hard problem.

• Stackless coroutines can actually be faster if they suspend a lot, because even though your code runs slower overall, there is less overhead for each suspend/resume. Generator functions that don't do a lot of work for each item can be like this.