Hacker News Reader

Comment by gpderetta | Hacker News Reader

I'm somewhat disappointed that rust is going with async style stackless continuations. I'm a huge fan of stackfull coroutines/continuations as they are much more elegant and flexible. The downside is that they need a full stack, but I strongly believe (but can't prove) that rust has enough annotations and lifetime capabilities that it should be able to guarantee single frame allocation (or even no allocation for fully scoped coroutines, like many generator use cases) in every situation that the async model would.

There is an ongoing discussion in the C++ world between traditional C# style async, a more extreme non-type erased version (similar to the rust implemation I think but unsafe) and stackfull coroutines. Some (like me) hope that an hybrid solution might be possible.

View on HN

This is already true with “tasks”; the chain of futures has a known stack size when you submit it to the event loop. It allocates the “stack” for the entire thing at once. So while the primitive may not have them, it’s still sorta there. This is only possible because the individual generators are stackless; if they were stack full, each future would get a stack individually.

You emphasize that stackfull coroutines could get down to a single allocation, but I'm not sure exactly what you mean. I could trivially get a stackfull coroutine down to a single allocation, the same way that systems thread do it: by allocating a defined stack size and raising a seg fault when you go over it.

The trick that "stackless coroutines" can achieve, and do achieve in Rust, is not just getting a single allocation, but getting a single perfectly sized alloc every time. It is exactly big enough to hold all the data it could ever need to hold, no more no less. You mention we have a lot of annotations, but the annotations that I know of that can achieve that are annotating every yield point so we can compute the stack space we need to store at that point, which is exactly what async/await notation is for.

By single stack frame I mean exactly that: a single perfectly sized (as it is known at compile time) allocation as opposed to a potentially runtime unbounded list of stack frames requuring a full stack (whatever form that mught take). I think that the optimization of converting the unbound stack to a fixed size stack frame can done for stackfull coroutines iff the continuation of the calling coroutine (i.e. the one that was suspended to activate the curren one) never escapes the coroutine function or any non-mutually recursive function called from the coroutine that the compiler can see though (either via inlineing or interprocedural optimization).

Interestingly this is similar to the analysis required to completely optimize a way the coroutine stack frame allocation. And because rust type system is good at tracking lifetimes and nested scopes, I think it might be possible to extend it ti guarantee this sort of optimization. Unfortunately this way beyond my pay grade.

We already have stackful coroutines. They're called threads. If for some reason you want M:N threading, we have that too, via the mioco library. (If you think mioco's M:N threading will provide far superior performance to regular 1:1 threads, though, you will probably be disappointed.)

If you look at the performance numbers of these approaches, you'll see why stackless coroutines are desired.

I want stackfull coroutines, with custom, fast user space scheduling and task switching with guaranteed optimisation to a single stack frame and no allocation where possible.

I also want the ability to convert internal iterators to internal iterators with no overhead and even (especially) if the internal iteration function has not been specifically marked (i.e. no red/blue functions).

Hey, a man can dream.

> guaranteed optimisation to a single stack frame and no allocation where possible

You are literally describing stackless coroutines. And the generator state transform is that optimization.

If you want to get this without using generators explicitly, it's still stackless coroutines just not how Rust supports stackless coroutines. There was some discussion about making it more implicit but no progress was made in the implicit direction.

Very much not. I want first class stackful continuation semantics that behave as stackless in at least all (but ideally more) scenarios where a stackless continuation would.

I would also mention https://github.com/edef1c/libfringe which pretty much solves context-switches (by replacing them with compiler-generated minimal stack spills/restores).

But as you might be able to tell from their APIs, you still have to allocate stacks somehow.

Undelimited continuations are memory sieves. Delimited continuations are better but a bit less useful.

Genuine question: aren't all one shot continuations (like the ones this thread is about) naturally delimited? Is there even such a thing as an undelimited one shot continuation?

Sure there is: take an undelimited continuation API, and restrict the resulting continuations to be called only once. Most use cases still work just fine, and I think it would be strange to call that anything other than "undelimited one-shot continuations".

Maybe what you have in mind, though, is the traditional argument, that there's no such thing as undelimited continuations. All continuations are naturally "delimited" by the boundary of the language runtime, operating system, etc, even with undelimited, multi-shot continuations. One-shot continuations make this argument more natural, because they have an obvious stack-based implementation for both delimited and undelimited continuations, and stacks are clearly delimited.

I guess that's what I have in mind. Any practical coroutine API has an explicit coroutine creation and yielding point that act as continuation delimiters.

Mm, not quite. Racket's greenthreads are incredible, and they don't use explicit yielding. I've always wanted something similar for JS.

Reply on news.ycombinator.com