LLVM Talks Related to Coroutines

[Ron Pressler]

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.