Pre-RFC: CPS transform for generators

[rpjohnst]

I’m not sure what you mean by that- could you clarify? There is currently no allocation or stack copying at suspension points, and we don’t want any- one of the core features of Rust’s futures design is that the whole tree of nested futures all gets put in one value and thus one allocation.

In fact, that’s probably why we ended up with this “rebuild and tear down the stack every time” problem- all previous async/await implementations* have been in languages with garbage collection, and so they “by default” allocate each generator separately, making this CPS transform much more natural for them. (I singled out Kotlin because it actually uses the “continuation” terminology and is fairly principled about it.)

* Except C++, which also allocates each generator separately, but for different reasons.

[bbatha]

There is currently no allocation or stack copying at suspension points, and we don’t want any- one of the core features of Rust’s futures design is that the whole tree of nested futures all gets put in one value and thus one allocation.

Oh absolutely, this is an extremely important property of rust generators and the raison-detre over more ergonomic stackful coroutine designs.

I’m not overly familiar with the exact structure of Rust generators, my terminology may have been off. The idea would be that instead of returning impl Generator on the stack a Generator function could be placement new’ed into a location such as a box. So while the Generator itself may not be moveable, how common is it to move it after it has been allocated somewhere? It seems like we mostly just need the ability to decide if the Generator is on the stack or on the heap.

[rpjohnst]

Ah, I see. That’s solved independent of what I describe here- the result of the Pin work is that you can move the impl Generator around, and it only becomes immovable once you resume it. So we don’t actually need Place, it’s just an optimization around the usual idiom of returning the impl Generator by move when it’s first created.

The downside you quoted is that, while currently the only immovable generators are ones that take references to “stack” variables, with this CPS transform that would grow to include generators that await inner generators, because awaiting would create a reference to the “stack” itself

[skade]

I’d like to note that this post uses CPS but doesn’t explain what the acronym is for those that don’t know.

(I assume you mean Continuation Passing Style)

[rpjohnst]

Ah, thanks! I’ve tweaked the post to clarify a couple things.

[aturon]

The entire call stack is (de)serialized for every call to poll, including frames that won’t be used that time.

I don’t understand what this means; to make this all work, the data needs to live in the heap at the start, and never move. AFAIK there’s no “serialization” involved.

[GolDDranks]

I think it means to say ”traversed”; in the sense that if an event unparks a task, the nested futures have to call the inner ones, one “nesting” a time, instead of jumping directly to the instruction where the blocking call originated. Compare this to a call stack that can be “ frozen in time”, and jumped directly back into without any traversal.

[aturon]

But that’s not the case when using generators (i.e. async/await): they compile down to a flat state machine.

[rpjohnst]

AFAIK there’s no “serialization” involved.

What I mean by “serialization” is that every generator has two forms it can take: When it is running, its state is encoded in the instruction pointer, the registers, and the host thread’s stack. When it is suspended, its state is encoded in its state block.

Before it suspends, it “serializes” itself- the instruction pointer determines the state number to be written into the state block, and live values are saved into the state block.

When it resumes, it “deserializes” itself- it switches on the state number to restore the instruction pointer, and it reloads live values from the state block.

Some values may remain in the state block, like values behind references and especially immovable ones like nested generators’ state blocks, but the key is the conversion back and forth between state number and instruction pointer.

they compile down to a flat state machine.

This is not quite true, and that’s the case where the (de)serialization becomes a problem. A single generator is a flat state machine, yes. But a generator awaiting another generator is two state machines in the same allocation- the inner generator’s state block is one of the outer generator’s “live values.”

When a generator is resumed in the middle of an await, it restores its instruction pointer into a loop where it calls resume on the inner generator again. This call pushes the restored instruction pointer onto the stack as a return address, and then the inner generator restores its own instruction pointer.

Thus, for each active await, the task switches on a state number to restore the instruction pointer and pushes it onto the stack, and then later returns to it and converts it back to a state number.

[rpjohnst]

To put it another way, resume ends either by yielding or completing, and we currently require both go to the same place- the return address on the host thread’s call stack, which points into the awaiting caller generator’s resume method.

But really we want yielding to go directly out to the executor, and completing to go back to the awaiting caller generator. So we need to save that return address (or rather something equivalent that will last until we complete) in the suspending callee generator’s state block, just like any live value.

And, since the caller generator may have more state on the host thread stack below that return address, including another return address, it needs to save it and clean up after itself before resuming the callee generator- which makes that call to resume a tail call.

[withoutboats]

This is not quite true, and that’s the case where the (de)serialization becomes a problem. A single generator is a flat state machine, yes. But a generator awaiting another generator is two state machines in the same allocation- the inner generator’s state block is one of the outer generator’s “live values.”

This (the core of your motivation) seems like it ignores inlining optimizations. Inlining these generators into one generator seems like the obvious solution to this problem to me.

[rpjohnst]

Inlining is great, and definitely helps, but it’s not a complete solution. (It also helps this proposal, as I mentioned in the first post.)

First, unless it’s done before state machine generation (i.e. on MIR), or LLVM gets extremely lucky and is able to combine the state numbers and simplify the resulting control flow, there will still be multiple nested state machines.

Second, inlining doesn’t always happen. Sometimes it’s better to leave a function out of line, like when it’s large and/or called from many different locations. (Technically, because generators can’t be recursive, we could just always fully inline them, so maybe “doesn’t” should be “shouldn’t.”)

Third, generators aren’t the only things you might want to await. Hand-written futures cannot be inlined the same way, because they’re already state machines. Hand-written futures could still take part in a CPS transform if we specify the interface right.

(Edit I: Fourth, there’s also debugging. If you’re running your program in a debugger and have to repeatedly step in and out of an unoptimized stack of generators, that will get old fast. There’s also the problem of debug builds being too slow to be useful. Reducing await's reliance on the optimizer will help both these cases.)

(Edit II: Fifth, a CPS transform would work across dynamically-dispatched generator calls while inlining wouldn’t. I don’t know how common e.g. async trait object method calls will be, but it would be great not to have to do the dynamic dispatch on every resume!)

I expect both situations 2 and 3 will be relatively common- larger functions that wouldn’t be inlined in synchronous code (including functions that are only large after a round of inlining), and hand-written combinators that generators await (e.g. for things like awaiting multiple futures in parallel).

If we truly want to call async/await a zero-cost abstraction, it ought to compile down to something that doesn’t have the “(de)serialize nested generators” problem.

[aturon]

If we truly want to call async/await a zero-cost abstraction, it ought to compile down to something that doesn’t have the “(de)serialize nested generators” problem.

Out of curiosity, do we have any evidence of the performance impact here?

I had some similar concerns when we were designing futures, since if you use a large tree of combinators, you end up with a nested enum representation, and on each resumption go through a cascade of matches. I spent some time trying to measure the overhead, and had to create ridiculous levels of nesting to measure any overhead at all.

[aturon]

Oh, one other question: I don’t fully grasp what you’re proposing here, but I think that the most pressing question is whether you think that async/await syntax based on the current design is forward compatible with such an interpretation later. We are pushing hard to land async/await for the 2018 edition, and definitely aren’t in a position to consider a change of this magnitude to make that schedule.

[rpjohnst]

Out of curiosity, do we have any evidence of the performance impact here?

It’s hard to fairly measure the performance of something that isn’t implemented. We do know that C#, Kotlin, and Javascript all use CPS, while Python uses nested resumption, so we may be able to learn something there.

But really, zero-cost abstraction doesn’t just mean nested resumption is “fast enough” for most use cases- after all, people write async code in all of those languages just fine. Zero-cost abstraction means you will never need to replace it with a hand-written equivalent, because its output is the same (or better!).

So while I don’t know what scenarios you used to test combinator performance, or what you compared them to, those benchmarks aren’t really my motivation. I want to avoid the scenario where someone builds something on generators, and then finds a scenario where that overhead does matter, but they can’t do anything about it other than a rewrite. This is the sort of thing that happens to game developers using C# and its GC, for example- it’s not that GC is “too much overhead” (in fact it’s often faster than naive malloc/free), but that it’s not a zero-cost abstraction.

To be more specific, today the focus for async/await is entirely on its use for networking. The conventional wisdom is that networking code is IO bound- again, people use much slower languages than Rust just fine in this space. But networking isn’t the only application for generators. They could potentially be great for GUIs, for games, for kernels, for embedded. These new domains certainly have different performance characteristics where the cost of resumption could easily matter much more.

This is about future-proofing the language and the applications written in it, at least as much as it is about performance.

(I have to head to work, but I have a response to the timing question as well.)

[rpjohnst]

I don’t fully grasp what you’re proposing here

Can I clarify anything in particular? Here is a quick sketch of the actual changes I’m proposing:

• Generators are constructed with and save a caller: *mut dyn Generator.
• In the generated resume methods, replace return GeneratorState::Return(x) with (conceptually) become self.caller.resume(x).
• Replace this (approximation of await!) in the generator source:

  let f = f(args..);
  loop {
      match f.resume() {
          GeneratorState::Yielded(x) => yield x,
          GeneratorState::Complete(x) => break x,
      }
  }
  

  with this code in the generated resume method:

  self.f = F::new(self, args..);
  self.state = next; // also save live values, etc.
  become self.f.resume();
  next:
  

• Use only a single Future to wrap an entire stack of generators. The leaf generator yields a reference to itself as a *mut dyn Generator, and poll saves that and resumes it on its next invocation. Generators awaiting Futures (as opposed to directly awaiting other generators) keep using the loop technique (and thus keep (de)serializing that stack frame every time).

I think that the most pressing question is whether you think that async/await syntax based on the current design is forward compatible with such an interpretation later.

Based on the changes above, I don’t believe it is forward compatible as-is, but it could be made compatible with some tweaks and selective stabilization. I believe there are two things to address:

• The interface and calling convention between awaiters and awaitees needs to remain an implementation detail of the compiler. If we switch to the “single Future per stack of generators” model that seems doable- forbid directly invoking a generator without awaiting it, and instead provide a standard library API to drive a whole stack of them.
• The generator-driving Future needs to be !Unpin, as it would eventually hold a reference into the generator. Generators that await other generators also need to be !Unpin, as they would also eventually hold references to their caller generators.

The idea that generators directly await other generators without going through a Future doesn’t have to make awaiting Futures much more cumbersome. Give Future an async method that contains the polling loop and await that, instead of baking the loop into the definition of await.

Interestingly, this is how Kotlin works- their generators are also not possible to invoke directly without awaiting, they also provide standard library APIs to drive whole stacks of them at once because they don’t pass through their Future interface at every level, and they also provide helper async methods on Futures for when you do want to await one from within a coroutine. Then, because you can’t ever invoke a generator without also awaiting it, they drop the await keyword altogether.

Thus, instead of this:

async fn foo() -> Result<T, E> {
    // ...
    await some_other_generator()
    // ...
    await some_future
    // ...
}

fn main() {
    let the_future = foo();
    tokio::run(the_future);
}

you write this:

async fn foo() -> Result<T, E> {
    // ...
    await some_other_generator()
    // ...
    await some_future.poll_wait()
    // ...
}

fn main() {
    let the_future = future_from_generator(foo);
    tokio::run(the_future);
}

(Or leave off the awaits if you like, because some_other_generator() on its own is meaningless).

This also neatly sidesteps the question of “but if foo() really returns a Future why isn’t Future in its type signature!?” by making foo() not return a Future.

[rkruppe]

In the generated resume methods, replace return GeneratorState::Return(x) with (conceptually) become self.caller.resume(x).

Does this mean this proposal is blocked on become or something morally equivalent? (I would expect so, since CPS transform leads to tons of tail calls.)

[rpjohnst]

Not at the source level, but yes. We would need a way for the generated resume methods to jump to other resume methods without growing the stack.

Fortunately, I don’t believe this is necessary for the forward-compatible version of the current implementation- tail calls can wait until we actually go to implement the CPS transform.

[rkruppe]

That’s unfortunate because there are some serious implementation challenges (LLVM…) and some serious inherent problems (calling conventions) with the general form of become. Maybe the latter are not relevant here but if we’ll never the general source-level feature because of it, solving all the implementaton challenges just for generators is still a tough pill to swallow.

[rpjohnst]

One angle is that, if it turns out not to be a big enough perf win to bother fighting LLVM over it, at least we’ll be compatible with a CPS implementation such that another backend or compiler could support it. That would involve keeping the calling convention for await unstable semi-permanently, but I’m not sure that’s an issue.