Erlang JIT之路

自从Erlang 存在，就一直有让它更快的需求和野心。这篇博文是一堂历史课，概述了主要的 Erlang 实现以及如何尝试提高 Erlang 的性能。

Prolog 解释器

Erlang 的第一个版本是在 1986 年在 Prolog 中实现的。那个版本的 Erlang 对于创建真正的应用程序来说太慢了，但它对于找出Erlang语言的哪些功能有用，哪些无用时很有用。在Prolog解释器中，可以在几小时或几天内添加或删除新的语言功能。

很快就清楚的了解，Erlang 需要至少快 40 倍才能在实际项目中应用。

JAM（Joe’s Abstract Machine）

1989 年，JAM（Joe’s Abstract Machine）首次实现。Mike Williams用 C 编写了运行时系统，Joe Armstrong编写了编译器， Robert Virding编写了库。

JAM 比 Prolog 解释器快 70 倍，但事实证明这仍然不够快。

TEAM (Turbo Erlang Abstract Machine)

Bogumil (“Bogdan”) Hausman 创建了 TEAM (Turbo Erlang Abstract Machine)。它将 Erlang 代码编译为 C 代码，然后使用 GCC 将其编译为本机代码。

对于小型项目，它比 JAM 快得多。但不幸的是，编译速度非常慢，而且编译后的代码太大，无法用于大型项目。

BEAM（Bogdan’s Erlang Abstract Machine）

Bogumil Hausman 的下一台机器称为 BEAM（Bogdan’s Erlang Abstract Machine）。它是一种混合机器，可以执行本机代码（通过 C 翻译）和带有解释器的线程化代码。这允许客户将他们对时间要求严格的模块编译为本机代码，并将所有其他模块编译为线程化的 BEAM 代码。线程化的 BEAM 比 JAM 代码快。

BEAM/C 的经验教训

现代的 BEAM 只有解释器，BEAM 生成 C 代码的能力在 OTP R4 中被删除，这是为什么呢？

C 语言不是 Erlang 编译器合适的目标语言，其主要原因是因为 Erlang 的进程模型，这里不能简单地将 Erlang 函数转换为 C 函数。每个 Erlang 进程都必须有自己的堆栈，并且该堆栈不能由 C 编译器自动管理。

BEAM/C 为每个 Erlang 模块生成了一个 C 函数。模块内的本地调用是通过显式将返回地址推送到 Erlang 堆栈，使用随后的goto语句跳转到调用函数来进行的。（严格来说，调用函数将返回地址存储到 BEAM 寄存器，然后被调用函数将该寄存器压入堆栈。）

使用 GCC 扩展，也可以类似地完成其他模块的调用：获取标签的地址，然后跳转到它。外部的调用也可以通过将返回地址压入堆栈，随后使用一个goto语句跳转到别的C 函数中的标签地址，完成外部调用。

这是不是未定义的行为？

是的，即使在 GCC 中也是未定义的行为。它只是碰巧在 Sparc处理器上与 GCC 一起工作，但是不适用于 X86 的 GCC。更复杂的是，嵌入式系统的 ANSI-C 编译器没有任何 GCC 扩展。

因此，我们必须维护三种不同风格的 BEAM/C 来处理不同的 C 编译器和平台。我不记得当时有任何基准测试，但 BEAM/C 在任何其他平台上都不太可能比在 Sparc 上的 Solaris 上解释的 BEAM 更快。

最后，我们移除了 BEAM/C 并对解释后的 BEAM 进行了优化，使其在速度上可以击败 BEAM/C。

HiPE

HiPE（高性能 Erlang 项目）是Uppsal大学的一个研究项目，从 1996 年左右开始运行多年。它“旨在使用一般的消息传递，特别是并发功能语言 Erlang 有效地实现并发编程系统”。

该项目的众多成果之一是用于 Erlang 的 HiPE 本机代码编译器。HiPE 于 2001 年成为 OTP R8 中 OTP 发行版的一部分。HiPE 原生编译器是用 Erlang 编写的，无需 C 编译器的帮助即可将 BEAM 代码转换为原生代码，因此避免了 BEAM/C 遇到的许多问题.

与解释的 BEAM 代码相比，HiPE 本机编译器通常可以将顺序代码加速两倍或三倍。我们希望这将加速现实世界的大型应用系统。不幸的是，爱立信内部尝试 HiPE 的项目发现它并没有提高性能。

这是为什么？

主要原因可能是大多数大型 Erlang 应用程序没有包含足够的 HiPE 可以优化的顺序代码。这些系统的运行时间通常由消息传递、对ETS BIF 的调用和垃圾收集的某种组合控制，这些都没有 HiPE 可以优化。

另一个原因可能是大系统通常有许多小模块。HiPE 原生编译器（与 Erlang 编译器一样）无法跨模块边界优化代码，因此无法进行很多基于类型的优化。

此外，对于大多数大型系统，将所有 Erlang 模块编译为本地代码会导致构建时间过长，并且生成的代码会消耗过多的内存。从本机代码切换到解释 BEAM 会产生少量开销，反之亦然。找出哪些模块可以从编译为本机代码中获益，同时避免在本机代码和解释代码之间进行过多的上下文切换，这是一项不平凡的任务。

由于 Ericsson Erlang 项目中没有一个使用 HiPE 原生编译器，因此 OTP 团队只能花费有限的时间来维护 HiPE。因此，HiPE 的文档包含以下说明：

HiPE 和 HiPE 编译代码的执行仅得到爱立信 OTP 团队的有限支持。OTP 团队只对 HiPE 做有限的维护，并没有积极开发 HiPE。HiPE 主要由Uppsala大学的 HiPE 团队提供支持。

HiPE 项目的其他成果

我认为如果没有 HiPE 项目，Erlang/OTP 在今天看起来会非常不同。以下是 HiPE 项目对 OTP 的主要贡献：

• OTP R7 中的一种新的分段标签方案。新的标记方案允许 Erlang 系统寻址完整的 4GB 地址空间（以前的标记方案仅支持寻址较低的 1GB）。令人惊讶的是，新的标签方案还提高了性能。
• 直到今天，Erlang 编译器仍在使用 Core Erlang 中间表示。有关更多信息，请参阅 Core Erlang 简介和 Core Erlang 示例。
• Dialyzer（DIscrepancy AnaLYZer for ERlang programs）最初是作为 HiPE 原生编译器的类型分析通道，但很快成为 Erlang 程序员帮助在其应用程序中查找错误和无法访问代码的工具。
• Bit string 和 binary comprehensions。
• 在 OTP R10 中引入try…… catch
• 实现每个函数的计数器和cprof 模块。计数器最初旨在用于查找热点函数并为这些函数生成本机代码。但是解释代码和本机代码之间上下文切换的开销使得这种用法没那么有用。
• 曾有多次建议， Erlang 需要一个字面量池（literals pool)来存放预制的字面量项（而不是每次使用它们时都构建它们）。在 HiPE 团队和 OTP 团队的一次会议上，我记得Richard Carlsson向我指出，如果Wings3D拥有浮点字面量会很好。OTP 团队在 OTP R12 中实现了字面量池。

The Tracing JIT projects (BEAMJIT)

已经有三个独立的研究项目试图为 Erlang 开发tracing JIT。他们都由RISE（前身为 SICS）的 Frej Drejhammar 领导。

tracing JIT（Just In Time compiler）是一个分两个阶段运行的 JIT：

• 首先，它跟踪执行以查找热（经常执行）代码。
• 然后它将找到的tracing重写为本机代码。

这三个 JIT 项目的目标是：

• JIT 应该自动工作，用户无需事先确定哪些模块要编译为本机代码。
• 应该与非 JIT BEAM 完全兼容。特别是，跟踪、调度行为、保存调用和热代码重新加载应该能正常工作，并且堆栈跟踪应该与非 JIT BEAM 中的相同。
• 至少平均而言系统应该永远不会比非 JIT BEAM 慢。

如果运行基准测试，则会获得一些承诺的结果，但最终证明不可能实现永远不比非 JIT 系统慢的目标。以下是运行缓慢的主要原因：

• 为了进行跟踪（查找热代码），BEAM 解释器需要调整。而在不降低 BEAM 解释器的基本速度的情况下，很难进行跟踪。
• 在不降低 BEAM 解释器基本速度的情况下，设计解释代码和本机代码之间的上下文切换机制也很困难。
• 当找到热代码序列时，需要将代码编译为本机代码。但使用 LLVM 的编译速度很慢。
• 当一个热代码序列最终被转换为本机代码时，它可能不会再次被执行。对于运行多道pass的 Erlang 编译器来说，这尤其是一个问题。通常，当一次pass的某些代码已转换为本机代码时，编译器已经在运行下一次pass。

后来的项目缓解了以前项目中的一些问题。例如，通过在调用 LLVM 之前进行更多优化来减少编译时间。不过，最终决定在 2019 年底终止第三个也是最后一个tracing JIT 项目。

有关 BEAMJIT 的更多信息，请参阅：

• BEAMJIT: a just-in-time compiling runtime for Erlang
• Just-in-time in No Time? “Use the Source!”
• JIT, a Maze of Twisty Little Traces
• A Status Update of BEAMJIT, the Just-in-Time Compiling Abstract Machine
• Just-in-time compiler for the Erlang VM
• Tracing JIT Compiler

新的 JIT（也称为 BeamAsm）

在第三个tracing JIT 项目结束后，参与了最后两个tracing JIT 项目的Lukas Larsson，想了各种不同的方法来生成一个有用的 JIT 。造成前三个tracing JIT缓慢的原因是跟踪以查找热代码和使用 LLVM 生成优化的本机代码。是否有可能有一个更简单的 JIT，它不进行跟踪并且没有或很少进行优化？

2020 年 1 月，从第三个tracing JIT 项目中挽救了一些代码，Lukas 迅速构建了一个原型 BEAM 系统，该系统在加载时将每个 BEAM 指令翻译成本机代码。生成的代码不如 LLVM 生成的代码优化，主要是因为它仍然使用 BEAM 的堆栈和 X 寄存器（存储在内存中），但消除了指令解包和指令分派的开销。

最初的基准测试结果很有希望：与解释的 BEAM 代码相比，速度大约是两倍，因此 Lukas 扩展了原型，以便它可以处理更多种类的 BEAM 指令。

John Högberg很快对这个项目产生了兴趣，并开始充当传声筒。一段时间后，可能是在 3 月，John 建议新的 JIT 应该将所有加载的代码转换为本地代码。这样，就不需要支持 BEAM 解释器和本机代码之间的上下文切换，这将使设计更简单并消除上下文切换的成本。

那当然是一场赌博。毕竟，本机代码可能太大而无法实际使用或降低性能，因为它不适合代码缓存。他们认为冒险是值得的，以后可能会优化代码的大小。（剧透：在撰写本文时，JIT 生成的本机代码比解释的 BEAM 代码大 10%。）

设计的另一个变化是生成本机代码的工具。在 Lukas 的原型中，每条指令的本地代码模板都包含在与加载程序使用的其他文件类似的文本文件中。那是不灵活的，所以决定使用一些可以生成本机代码的库。虽然可以使用一些纯 C 库，但 C++ 库AsmJIT在实际使用中比任何 C 库都更方便。此外，一些 C 库被排除在外，因为它们使用了 GNU 许可证，而我们不能在 OTP 中使用。因此，将 BEAM 指令转换为本机代码的加载程序部分需要用 C++ 编写，但运行时系统的其余部分仍然是纯 C 代码，并且将保持不变。

John 于 3 月底加入了重新调整的 JIT 项目的实际工作。

2020 年 4 月 7 日，约翰达到了“prompt beer”的里程碑。

Prompt Beer

当 Erlang 系统启动时，在提示符出现之前执行了大量的代码。一方面，这意味着在启动 Erlang 系统之前需要实现许多指令的翻译，更不用说运行任何测试套件或基准测试了。

另一方面，当提示符最终出现时，是一个重要的里程碑，值得用一些prompt beer或其他适当的饮料来庆祝，或者在晚上剩下的时间里休息一下。

新的 JIT成熟

4 月 14 日，John 让 Dialyzer 使用 JIT 运行，而在 4 月 17 日，在对代码生成进行了一些改进之后，使用 JIT 的 Dialyzer 仅比使用 HiPE的 慢 10%。没有一个tracing JIT 在加速 Dialyzer 方面取得任何成功。（在撰写本文时，Dialyzer 在 JIT 下的运行速度与在 HiPE 上的运行速度大致相同，尽管由于 HiPE 不能在 OTP 23 之后的版本上运行，因此进行公平比较变得越来越困难。）

可能是在那个时候，我们意识到我们有一个可以最终包含在 OTP 版本中的 JIT。

5 月 6 日实现了堆栈跟踪中的行号，实现了下一个重要里程碑。这意味着更多的测试用例现在可以运行并取得成功了。

此后不久，所有测试套件都可以成功运行。在夏季和初秋期间， 我和Dan兼职加入了该项目，并完成了以下工作：

对 BEAM 加载程序进行了重大重构，以便在 JIT 和 BEAM 解释器之间共享尽可能多的代码。（BEAM 解释器仅用于不支持 JIT 的平台。） 实现和完善重要但较少使用的功能，例如跟踪、性能支持和保存调用（参见process_flag/2的save_calls标志）。 缩小生成的本机代码的代码大小。 将 JIT 移植到 Windows，结果相对容易。 使使用本机堆栈指针寄存器和堆栈操作指令成为可能。这改进了性能支持并略微减小了本机代码的大小。

在 Lukas 于 9 月 11 日介绍新JIT期间，其创建的pull request时，这项工作达到了高潮。

pull request于 9 月 22 日合并。

未来

以下是我们一直在为未来版本考虑的一些改进

• 支持 ARM-64（在 Raspberry Pi 和 Apple 新的带有 Apple Silicon 的 Mac 中使用）。
• 实现本机代码的类型引导生成。OTP 22 中引入的新的基于 SSA 的编译器通道进行了复杂的类型分析。令人沮丧的是，并非所有类型信息都可以用来为解释的 BEAM 生成更好的代码。我们计划修改编译器，以便将一些类型信息包含在 BEAM 文件中，然后由 JIT 在代码生成期间使用。
• 引入二进制匹配和/或构造的新指令，以帮助 JIT 生成更好的代码