Predictable Sized Function Stacks for Stackful Coroutine Optimization

[tothambrus11]

Yesterday I heard of an interesting way of how Rust knows the size of required stack for functions for its futures. They just calculate it. For this, the following requirements need to be upholded in the language:

• no alloca (arbitrary sized stack allocation)
• no recursion within asynchronous code

The latter requirement sounds very alarming for me, since recursion is never part of the API of the function but the compiler still keeps track of this information. Like function coloring, but you only see the color with a UV flashlight. However, recursion is not completely impossible to achieve here, we just need to start a new heap-allocated task. If someone doesn't want to do that, they can also rewrite the recursion as a loop (which probably also uses a stack data structure).

In Concurrency Hylomorphism, @lucteo talked about weakly structured concurrency, in which case the spawned task needs to allocate its stack on the heap, since it may complete after we escaped from the function.

I was wondering what the performance benefit would be in our case if we knew how much stack a function would be using at most. Then we could allocate potentially much smaller stacks in most cases, so maybe it could be used as an optimization, in the cases when we do have enough information (Hylo is not planning to require monomorphizing as aggressively as Rust does, so this technique is not always applicable). What are your thoughts?

Annotations like @tailrec or @norec could guarantee this optimization can always happen. This exposes some implementation details in the API but it's not something that cannot be worked around inside the function if they need to change those later.

[lucteo]

On determining the stack size of the functions:
We discussed this topic multiple times in our meetings. The general conclusion is that we can probably do something similar (considering the codegen limitations we might have), and we would want to do it as an optimization.

This is especially useful in cases in which we have many suspended coroutines and the stack size becomes problematic. On coroutines w/o suspensions, we consume roughly as much stack as we would if we would just create one thread per core.

On allocating the spawn frame on the heap:
Please note that the frame size is always known, and has nothing to do with the code that is being executed asynchronously. The spawned function will have its stack on a dedicated coroutine stack; this can be reused between multiple non-overlapping coroutines, and we might use the above technique to reduce its size (if needed)
The frame size is something that makes it possible to connect await to its corresponding spawn. If in structured concurrency we know that both await and spawn are living on the same stack, we can allocate this frame on the stack. However, on weakly structured concurrency, the stack at the spawn point may go away before we reach await, and thus we can't place that frame on the stack.