LLVM Talks Related to Coroutines

[Ron Pressler]

One thing I neglected to explain in my previous email is why it is that the
"backend strategy" is at odds with inlining the continuation into the caller.

In the frontend strategy, continuations are explicitly compiled into special
continuation code, and they explicitly maintain their state. So if the
continuation is inlined into the caller, the combined code will continue to
correctly maintain the continuation state. But in the backend strategy, code is
oblivious to whether it is running inside a continuation or not, and state is
managed at the lower machine stack level. Therefore, to allow this implicit
management of the continuation's state, entering a continuation requires
entering a new physical stack frame, and so we cannot inline.

This, however, is no loss, because when continuations are mostly used to
implement fibers, the continuation's caller is usually the scheduler, and the
call is megamorphic, so no inlining would take place, anyway.

Ron




On February 12, 2019 at 7:41:21 PM, Ron Pressler (ron.pressler at oracle.com(mailto:ron.pressler at oracle.com)) wrote:

> There are two general approaches to implementing one-shot delimited
> continuations, AKA coroutines. I’ll call them the frontend approach and the
> backend approach. The frontend approach tries to express continuations using
> primitive constructs available by the compiler frontend, be it a programming
> language, LLVM IR, or bytecode -- namely subroutines, switch expressions etc. --
> and it works regardless of how the compiler's backend generates machine code. It
> requires compiling continuations into subroutines that explicitly implement a
> state machine. The backend approach works by manipulating the stacks and/or
> instructions at the machine-code level, and it works regardless of whatever
> existing constructs are provided by the language/IR/bytecode; in a way, it adds
> a new primitive construct. When using the frontend approach, it is usually
> (though not necessarily) the case that a coroutine requires some explicit
> syntactic expression in the language, i.e., some piece of code must be marked as
> a continuation in the language. When using the backend approach, continuations
> are implicit, and any existing subroutine, even ones that have already been
> compiled, can be used on the continuation stack. They rely on the fact that all
> subroutines are necessarily *already* compiled into state machines in order to
> run on, say, Intel processors, as that is required to allow subroutines to
> return to their caller (i.e. the caller's state must be saved in some resumable
> state), and continuations created using this approach use the same mechanism
> used by the processor to return to the caller to implement continuations.
>  
> Kotlin, Quasar, C# and the LLVM continuations described in the talk use the
> frontend strategy; Go, Scheme and Loom, at least in its current prototype, use
> the backend strategy. BTW, the name "coroutine" has recently gained the
> connotation of syntactically-delineated continuations associated with the
> frontend strategy, and that's one of the reasons why we are using the more
> general term "continuations" (although this may change).
>  
> Given similar development efforts, the frontend approach may well be more
> optimal (in terms of performance) when continutations are very small and local
> (e.g. generators), because the compiler could then, e.g., automatically optimize
> away allocations of the continuation's state storage or inline continuation code
> into the caller, while the backend approach may be more optimal for more
> heavyweight, less local, continuations (e.g. fibers), because this automatically
> supports arbitrary code, and rather efficiently. Because we believe that the
> most generally useful application of continuations is fibers, we favor the
> backend approach (although this may change). Moreover, as the backend approach
> requires no changes to the compiler (or interpreter) -- and we have quite a few
> of them: C1, C2, Graal, as well as the interpreter -- this is cheaper for us to
> try first. In fact, the number of backends we support is smaller than the number
> of compilers+interpreter that we have, so the backend strategy is a natural
> choice (not to mention that the backends are very similar to one another, unlike
> the compilers+interpreter). In addition, the JVM has its own peculiar
> characteristics that can both help or hurt. E.g., heap allocations are very
> cheap, we have world-class GCs (so stack resizing is not much of an issue),
> debuggers/profilers are under our control, and use of native code is uncommon
> (outside of built-in JDK usage, which we also control) so we don't need to worry
> much about interop with native code. On the other hand, the GC does impose some
> severe limitations on how we store state. Languages with just one compiler, and
> with less control over the entire tooling, will find the frontend approach
> easier.
>  
> The current implementation in the prototype is relatively slow, but that's
> because we've so far done the simplest things possible. We are now starting to
> look into improving performance. We currently have no reason to believe that the
> backend strategy will be a significant hindrance in terms of performance, even
> without changing any of the compilers -- and if it turns out it is, we can
> switch -- even though we do lose, say, the ability to inline the continuation
> into its caller (which won't happen anyway if your common use-case is fibers,
> where your caller is always the scheduler, and it calls a great many number of
> different continuations). But as we care more about fibers than, say,
> generators, it is likely that our continuation implementation will not be as
> efficient for generators as others that optimize for that use-case.
>  
> Anyway, our approach is much more along the lines of what the speaker mentions
> in the last minute of the video than anything that precedes it. :)
>  
> Ron
>  
>  
>  
> On February 7, 2019 at 9:38:04 PM, Volkan Yazıcı (volkan.yazici at gmail.com(mailto:volkan.yazici at gmail.com)) wrote:
>  
> > Hello,
> >
> > Swift and LLVM developer John McCall's 2018 LLVM Developers’ Meeting
> > “Coroutine Representations and ABIs in LLVM” talk
> > has recently
> > been made available on YouTube .
> > (Still waiting for slides to get published.) Gor Nishanov's 2016 "LLVM
> > Coroutines: Bringing resumable functions to LLVM" talk
> > , mentioned in John's intro, was
> > already available for a long time, including slides. Given there is still
> > not a conclusive path on the implementation of fibers in OpenJDK, I thought
> > you might find these material useful.
> >
> > Best.