没有JVM支持的JVM语言中，协程是如何实现的？

Question

在阅读描述使用Java编程语言实现协程的方法的Loom提案后，我产生了这个问题。

具体来说，该提案表示为了在语言中实现该功能，需要额外的JVM支持。

据我所知，已经有几种语言在JVM上具有协程作为其特性集，例如Kotlin和Scala。

那么，在没有额外支持的情况下，该功能是如何实现的，且能否有效地实现？

- marknorkin

Answer 1

简短总结：

特别地，这个提案表示为了在语言中实现该功能，需要额外的JVM支持。

当他们说“需要”时，他们是指“需要以一种既具有性能又可以在各种语言之间互操作的方式来实现”。

那么如果没有额外的支持，如何实现这个功能？

有很多方法，最容易理解的可能是用自己的语义在JVM上实现自己的虚拟机。（请注意，这不是实际操作的方式，这只是为什么可以这样做的直觉。）

不使用额外支持是否可以高效实现？

不太可能。

稍长解释：

请注意，Project Loom的一个目标是纯粹作为库引入这个抽象。这有三个优点：

• 引入新库比更改Java编程语言要容易得多。
• 库可以立即被在JVM上编写的每种语言的程序使用，而Java语言特性只能由Java程序使用。
• 可以实现具有相同API但不使用新JVM特性的库，这将使您能够编写在旧JVM上运行的代码，只需进行简单的重新编译（虽然性能较低）。

但是，将其实现为库会排除巧妙的编译器技巧将协程转换为其他内容的可能性，因为没有涉及编译器。没有巧妙的编译器技巧，要获得良好的性能就变得更加困难，因此“需要”JVM支持。

较长解释：

一般来说，所有通常的“强大”控制结构在计算意义上都是等效的，并且可以使用彼此来实现。

最著名的“强大”通用控制流结构之一是备受推崇的GOTO，另一个是Continuations。此外还有线程和协程，同样等效于GOTO但人们不经常考虑的一个是例外。

另一个可能性是可实例化的调用堆栈，这样程序员可以访问调用堆栈对象并且可以被修改和重新编写。（例如，许多Smalltalk方言就是这样做的，而且在C和汇编中也有类似的方式）。

只要您拥有其中之一，您就可以通过在其上实现一个来拥有所有这些功能。

JVM有其中两个：Exceptions和GOTO，但JVM中的GOTO不是通用的，它非常有限：它只在单个方法内起作用（基本上只用于循环）。因此，这留下了我们使用Exceptions。

所以这是您问题的一个可能答案：您可以在Exceptions之上实现co-routines。

另一个可能性是完全不使用JVM的控制流，而是实现自己的堆栈。

然而，当在JVM上实现co-routines时，通常不采取这条路。大多数情况下，实现co-routines的人会选择使用Trampolines并部分实例化执行上下文作为对象。例如，这就是在CLI上实现生成器的方式（不是JVM，但挑战是相似的）。C♯中的生成器（基本上是受限半co-routines）是通过将方法的局部变量提升为上下文对象的字段，并将方法拆分为该对象上每个yield语句的多个方法来实现的，将它们转换为状态机，并仔细地通过上下文对象上的字段将所有状态更改线程化。在async/await成为一种语言功能之前，一个聪明的程序员也使用了同样的机制来实现异步编程。

然而，这正是您提到的文章可能指的：所有这些机制都是昂贵的。如果您实现自己的堆栈或将执行上下文提升为单独的对象，或者将所有方法编译为一个超大方法并在各处使用GOTO（甚至由于方法大小限制而无法实现），或者将异常用作控制流，那么以下至少有一件事情是真实的：

• 您的调用约定与其他语言期望的JVM堆栈布局不兼容，即您失去了互操作性。
• JIT编译器不知道您的代码在做什么，并呈现字节码模式、执行流模式和使用模式（例如抛出和捕获庞大量的异常）它不希望且不知道如何优化，即您失去了性能。

Rich Hickey（Clojure的设计者）曾在演讲中说过：“尾调用，性能，Interop。选择两个。”我将其概括为我所称的Hickey's Maxim：“高级控制流程，性能，Interop。选择两个。”

实际上，即使实现任何一个互操作性或性能也很困难。

此外，您的编译器将变得更加复杂。

当这个构造在JVM中可以原生使用时，所有这些问题都会消失。例如，想象一下如果JVM没有线程。那么，每种语言实现都会创建自己的线程库，这是困难、复杂、缓慢且与任何其他语言实现的线程库无法互操作。

一个最近的真实例子是lambda：许多JVM上的语言实现都有lambda，如Scala。然后Java也添加了lambda，但是因为JVM不支持lambda，它们必须以某种方式进行编码，而Oracle选择的编码与Scala之前选择的编码不同，这意味着您无法将Java lambda传递给期望Scala Function的Scala方法。在这种情况下的解决方案是，Scala开发人员完全重写了他们的lambda编码以与Oracle选择的编码兼容。这实际上在某些地方破坏了向后兼容性。

- Jörg W Mittag

---

如果他们在Exception之上实现它们，那么没有人会使用它们，在这些控制流程之上实现（至少在Java中 - 即使是空的堆栈跟踪）将是昂贵的。其次，您关于lambdas的说法只有部分正确，它们确实具有字节码指令，让运行时决定这些实现将是什么 - 而不是编译器（invokedynamic）。 - Eugene

invokedynamic和整个LambdametaFactory机制都是实现细节。Java lambdas早于JSR292，最初是在没有它的情况下实现的。JSR292允许更高效、更紧凑的实现，但并非必需。特别是，Retrolambda项目提供了一个符合标准的Java 8 lambdas和方法引用实现，在Java 7、6或5 JVM上运行，后两者都没有invokedynamic。invokedynamic与lambda无关，其目的是加速具有任意语义的虚拟分派，特别是语义... - Jörg W Mittag

这是一种可由用户编程的 invokevirtual 版本，其不匹配 invokevirtual。该版本向程序员公开了 JVM 为 invokevirtual 进行的所有巧妙优化技巧，以便于 每个 虚拟派发都能受益于这些优化，而不仅仅是看起来像 Java 的虚拟派发。例如，鸭子类型或多重继承。 - Jörg W Mittag

Answer 2

根据Kotlin关于协程的文档（我强调）：

协程通过将复杂性放入库中使异步编程更加简单。程序逻辑可以在协程中顺序表达，底层库会为我们处理好异步问题。库可以将用户代码的相关部分包装成回调函数、订阅相关事件、在不同线程（甚至不同机器）上安排执行，而代码看起来就像按顺序执行一样简单。

简而言之，它们被编译为使用回调和状态机处理挂起和恢复的代码。

该项目的负责人Roman Elizarov在KotlinConf 2017上发表了两次关于此主题的精彩演讲。其中一篇是介绍协程，另一篇则是深入了解协程。

- Todd

---

使用回调函数和状态机 - 一个小修正：在编译代码中没有回调函数，因为有限状态机的作用就像它们一样。 - voddan

这个视频是由Android团队的Manuel Vivo主讲的，介绍了使用“传递续体（CPS）”和“状态机”的实现方式来实现suspend函数的优秀概述。 - nilTheDev

Answer 3

协程 不依赖于操作系统或JVM的功能。相反，编译器通过转换协程和suspend函数生成一个状态机，能够处理一般的挂起并传递挂起的协程以保持它们的状态。这是由Continuations实现的，编译器将其作为参数添加到每个挂起函数中；这种技术称为“Continuation-passing style”（CPS）。

一个例子可以看到suspend函数的变换：

suspend fun <T> CompletableFuture<T>.await(): T

下面是 CPS 转换后的签名：

fun <T> CompletableFuture<T>.await(continuation: Continuation<T>): Any?

如果您想了解详细信息，需要阅读解释。

- s1m0nw1

---

从理想的角度来看，CPS可以解决问题，但它往往会产生代码，其中没有任何调用会返回，这会导致快速堆栈溢出，除非JVM进行尾调用优化。优化尾调用是JVM规范允许的，但许多实现不会这样做，或者至少不会默认这样做，而是更喜欢保留足够的信息，以便能够为新的Throwables配备与程序员预期的天真执行模型相匹配的堆栈跟踪。 - hmakholm left over Monica

我认为在广泛使用中，只有J9执行（但不保证）TCO，尽管Avian可能也会执行。 - Jörg W Mittag

Answer 4

“Project Loom”是由同一作者编写的“Quasar”库之前推出的。

以下是它的文档中的一句话引用：

内部来说，一个纤程是一个连续体，然后在调度器中进行调度。一个连续体捕获了计算的瞬时状态，并允许它在稍后的时间从被暂停的点处挂起并恢复。Quasar通过对可暂停方法进行插桩（在字节码级别）创建连续体。对于调度，Quasar使用ForkJoinPool，这是一个非常高效、工作窃取、多线程的调度器。

每当一个类被加载时，Quasar的插桩模块（通常作为Java代理运行）会扫描其中的可暂停方法。然后对每个可暂停方法f进行以下方式的插桩：扫描其中对其他可暂停方法g的调用。对于每个调用g的可暂停方法，会在调用g之前（和之后）插入一些代码，将局部变量的状态保存（和恢复）到纤程的堆栈（一个纤程管理自己的堆栈），并记录这个（即调用g）可能是一个暂停点的事实。在这个“可暂停函数链”的末尾，我们会找到一个对Fiber.park的调用。park通过抛出SuspendExecution异常（即使你的方法包含一个catch(Throwable t)块，插桩也会阻止你捕获它）来挂起纤程。

如果g确实阻塞了，SuspendExecution异常将被Fiber类捕获。当纤程被唤醒（使用unpark）时，方法f将被调用，然后执行记录将显示我们在调用g处被阻塞，因此我们将立即跳转到f中调用g的行，并调用它。最后，我们将达到实际的暂停点（调用park），在那里我们将立即恢复执行，紧接着是调用之后的代码。当g返回时，插入在f中的代码将从纤程堆栈中恢复f的局部变量。

这个过程听起来很复杂，但它只会产生不超过3%-5%的性能开销。

似乎几乎所有纯Java的continuation 库都使用类似的字节码检测方法来捕获和恢复堆栈帧上的本地变量。

只有Kotlin和Scala编译器足够勇敢，实现更加独立和可能更高效的方法，这些方法涉及一些其他答案中提到的CPS转换状态机。

- Vadzim