通往 JIT 之路

2020 年 12 月 01 日 · 作者：Björn Gustavsson

自从 Erlang 诞生以来，一直存在使其速度更快的需要和雄心。这篇博文是一堂历史课，概述了 Erlang 的主要实现以及为提高 Erlang 性能所做的尝试。

Prolog 解释器 #

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

很快就清楚地发现，Erlang 至少需要快 40 倍才能在实际项目中发挥作用。

JAM（Joe 的抽象机）#

1989 年，首次实现了 JAM（Joe 的抽象机）。Mike Williams 用 C 语言编写了运行时系统，Joe Armstrong 编写了编译器，而 Robert Virding 编写了库。

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

TEAM（Turbo Erlang 抽象机）#

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

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

BEAM（Bogdan 的 Erlang 抽象机）#

Bogumil Hausman 的下一台机器称为 BEAM（Bogdan 的 Erlang 抽象机）。它是一个混合机器，可以执行本机代码（通过 C 转换）和具有线程代码以及解释器。这使得客户可以将他们的时间关键模块编译为本机代码，并将所有其他模块编译为线程 BEAM 代码。线程 BEAM 本身比 JAM 代码更快。

从 BEAM/C 中吸取的教训 #

现代 BEAM 只有解释器。BEAM 生成 C 代码的能力在 OTP R4 中被放弃了。为什么？

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

BEAM/C 为每个 Erlang 模块生成一个 C 函数。模块内的本地调用是通过显式将返回地址推送到 Erlang 堆栈，然后`goto`到被调用函数的标签来实现的。（严格来说，调用函数将返回地址存储到 BEAM 寄存器，被调用函数将该寄存器推送到堆栈。）

对其他模块的调用也类似，使用 GCC 扩展，该扩展使获取标签地址并在之后跳转到它。因此，通过将返回地址推送到堆栈，然后 `goto` 到另一个 C 函数中的标签地址来进行外部调用。

那不是未定义的行为吗？

是的，即使在 GCC 中也是未定义的行为。它碰巧在 Sparc 上的 GCC 上有效，但在 X86 的 GCC 上无效。进一步的复杂情况是，嵌入式系统具有没有任何 GCC 扩展的 ANSI-C 编译器。

因此，我们必须维护三种不同的 BEAM/C 版本来处理不同的 C 编译器和平台。我不记得那个时候的任何基准测试，但是 BEAM/C 不太可能在 Solaris on Sparc 以外的任何其他平台上比解释的 BEAM 快。

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

HiPE #

HiPE（高性能 Erlang 项目）是乌普萨拉大学的一个研究项目，从 1996 年左右开始运行多年。它“旨在高效地实现使用消息传递和并发函数式语言 Erlang 的并发编程系统”。

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

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

为什么？

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

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

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

由于没有爱立信 Erlang 项目使用 HiPE 本机编译器，因此 OTP 团队只能投入有限的时间来维护 HiPE。因此，HiPE 的文档中包含以下注释

HiPE 和 HiPE 编译代码的执行仅得到爱立信 OTP 团队的有限支持。OTP 团队仅对 HiPE 进行有限的维护，并且不积极开发 HiPE。HiPE 主要由乌普萨拉大学的 HiPE 团队支持。

HiPE 项目的其他成果 #

我认为，如果没有 HiPE 项目，Erlang/OTP 今天看起来会大不相同，这是公平的说法。以下是 HiPE 项目对 OTP 的主要贡献

  • OTP R7 中新的分阶段标签方案。新的标签方案允许 Erlang 系统寻址完整的 4GB 地址空间（以前的标签方案仅支持寻址较低的 1 GB）。令人惊讶的是，新的标签方案也提高了性能。

  • Core Erlang 中间表示法至今仍在使用 Erlang 编译器中。有关更多信息，请参阅Core Erlang 简介和Core Erlang 示例。

  • Dialyzer（用于 ERlang 程序的差异分析器）最初是 HiPE 本机编译器的类型分析传递，但很快成为 Erlang 程序员的工具，以帮助查找其应用程序中的错误和无法访问的代码。

  • 位串和二进制推导.

  • 在 OTP R10 中引入try...catch。

  • 实现每个函数的计数器和cprof模块。计数器最初用于查找热函数并仅为这些函数生成本机代码。但是解释代码和本机代码之间上下文切换的开销使得这种用法不太有用。

  • 反复建议 Erlang 需要一个文字池用于预制的文字项（而不是每次使用时都构建它们）。在 HiPE 团队和 OTP 团队之间的一次会议上，我记得 Richard Carlsson 向我指出，Wings3D 拥有浮点文字会很好。OTP 团队在 OTP R12 中实现了文字池。

跟踪 JIT 项目 (BEAMJIT) #

有三个独立的研究项目试图为 Erlang 开发跟踪 JIT。所有这些项目都由 RISE（以前称为 SICS）的 Frej Drejhammar 领导。

跟踪 JIT（即时编译器）是一个分两个阶段运行的 JIT

  • 首先，它跟踪执行以查找热（频繁执行）代码的序列。

  • 然后，它将找到的跟踪重写为本机代码。

三个 JIT 项目的目标是

  • JIT 应该自动工作，而无需用户事先确定要将哪些模块编译为本机代码。

  • 应该与非 JIT BEAM 完全兼容。特别是，跟踪、调度行为、保存调用和热代码重新加载应继续工作，并且堆栈跟踪应与非 JIT BEAM 中的堆栈跟踪相同。

  • 该系统至少在平均水平上永远不应比非 JIT BEAM 慢。

运行一些基准测试时有一些有希望的结果，但最终发现不可能实现永不比非 JIT 系统慢的目标。以下是速度减慢的主要原因

  • 为了进行跟踪（查找热代码），需要对 BEAM 解释器进行调整。在不降低 BEAM 解释器的基本速度的情况下进行跟踪很困难。

  • 以不降低 BEAM 解释器的基本速度的方式设计解释代码和本机代码之间上下文切换的机制也很困难。

  • 当找到热代码序列时，需要将代码编译为本机代码。使用 LLVM 的编译速度很慢。

  • 当热序列最终转换为本机代码后，可能会发现它不会再次执行。对于运行多次传递的 Erlang 编译器来说，这是一个特别的问题。通常，当一个传递的一些代码已转换为本机代码时，编译器已经在运行下一个传递。

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

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

新的 JIT（也称为 BeamAsm） #

在第三个跟踪 JIT 项目结束后，Lukas Larsson 参与了最后两个跟踪 JIT 项目，他一直在思考可能产生有用 JIT 的不同方法。先前方法放慢速度的原因是跟踪以查找热代码以及使用 LLVM 生成优化的本机代码。是否有可能拥有一个更简单的 JIT，它不进行跟踪并且不进行或很少进行优化？

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

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

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

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

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

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

2020 年 4 月 7 日，John 达到了“提示啤酒”里程碑。

提示啤酒 #

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

另一方面，当提示符最终出现时，这是一个值得用一些提示啤酒或其他合适的饮料庆祝或休息一晚的主要里程碑。

新 JIT 的成熟 #

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

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

下一个主要里程碑是在 5 月 6 日实现的，当时实现了堆栈跟踪中的行号。这意味着现在有更多的测试用例成功了。

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

  • 对 BEAM 加载程序进行重大重构，以便在 JIT 和 BEAM 解释器之间共享尽可能多的代码。（BEAM 解释器仅在不支持 JIT 的平台上使用。）

  • 实现和改进重要但较少使用的功能，例如跟踪和 perf 支持，以及保存调用（请参阅 process_flag/2 的标志 save_calls）。

  • 缩小生成的本机代码的代码大小。

  • 将 JIT 移植到 Windows，事实证明这相对容易。

  • 使得可以使用本机堆栈指针寄存器和堆栈操作指令。这改进了 perf 支持并略微减小了本机代码的大小。

这项工作最终形成了一个公共的 拉取请求，Lukas 在 9 月 11 日的 新 JIT 演示中创建了这个请求。

拉取请求于 9 月 22 日合并。

未来 #

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

  • 支持 ARM-64（由 Raspberry Pi 和 Apple 的新款搭载 Apple Silicon 的 Mac 使用）。

  • 实现类型引导的本机代码生成。在 OTP 22 中引入的新 基于 SSA 的编译器传递进行了复杂的类型分析。令人沮丧的是，并非所有类型信息都可以用于为解释的 BEAM 生成更好的代码。我们计划修改编译器，以便将一些类型信息包含在 BEAM 文件中，然后由 JIT 在代码生成期间使用。

  • 引入用于二进制匹配和/或构造的新指令，以帮助 JIT 生成更好的代码。