高效解释器的结构与性能¶

标题：The Structure and Performance of Efficient Interpreters

日期：2003/11/03

作者：M. Anton Ertl, David Gregg

链接：https://jilp.org/vol5/v5paper12.pdf

注意：此为 AI 翻译生成 的中文转录稿，详细说明请参阅仓库中的 README 文件。

备注一：受此前 2023 年的调度演讲影响，找了篇老论文作为对照。

备注二：2003 年的结论到现在也从未改变，分支是最大的问题。

备注三：还是要学一手线程化代码（threaded code，和线程没关系）。

摘要¶

为高通用性能而设计的解释器通常会执行大量的间接分支（在我们测试的基准程序中占所有已执行指令的 3.2%-13%）。在我们模拟的多种配置中，这些分支消耗了超过一半的运行时间。我们评估了各种现有和提议的分支预测方案在多种解释器上的准确性，预测失误如何影响解释器的性能，以及两种不同的解释器实现技术在各种分支预测器下的表现。我们还提出了一些硬件设计者、C 编译器作者和解释器作者可以用来提高解释器性能的方法。

1. 引言¶

解释器的几个优点使其具有吸引力：

易于实现。
可移植性。
快速的编辑-编译-运行周期。

在许多解释型语言的实现中，运行时效率是一个重要的次要需求。Romer 等人 [1] 研究了几种解释器（MIPSI, Java, Perl, Tcl）的性能。他们没有发现所有解释器共有的性能问题，也没有针对特定解释器得出特别引人注目的结果，并得出结论：解释器的性能应该通过软件手段而不是专门的硬件来提高。

因此，在本文¹中，我们研究了四种为良好通用性能而设计的解释器（在本文的其余部分，我们称之为高效解释器）。我们发现它们执行了异常高数量的间接分支：它们中间接分支的比例都高于间接分支预测研究人员使用的任何基准测试。这一点对许多解释器作者来说可能是显而易见的，但对硬件设计者来说不一定，甚至关于解释器性能特征最著名的论文 [1] 也完全忽略了这一点（详见第 7 节）。

* 部分由 Enterprise Ireland, International Collaboration Scheme 支持

本文的一个更早且更短的版本出现在 Euro-Par ‘01 会议录 [2] 中。

由于间接分支数量众多，高效解释器的性能高度依赖于间接分支预测的准确性和分支预测失误的惩罚；性能影响的量级可能甚至会让解释器作者感到惊讶：我们在没有预测器和有良好预测器之间看到了高达 4.77 倍的加速因子。

本文的主要贡献是量化间接分支在现代硬件上对解释器的影响，这种影响如何作用于不同的实现技术，以及现有和提议的间接分支预测器在解释器上的工作效果。

本文的另一个重要贡献是反驳 [1] 的读者可能产生的印象，即解释器的行为就像 SPECint 基准测试一样。

1.1 为什么需要高效解释器？¶

你可能会想，为什么有人要在加速解释器上花费任何精力；为什么不直接编写一个编译到本地代码的编译器呢？主要原因是，本地代码编译器在开发和维护上需要显著更多的努力，特别是如果它需要支持多个平台（见第 1.2 节）；采用本地代码编译器路线的最终结果通常是一个只在一个平台上运行的语言实现，缺少像样的调试器等可用性功能，编译时间明显，或者在跟踪语言或环境的发展方面速度很慢。

为什么不编写一个编译到 C 的编译器呢？虽然这种方法解决了易于实现和重定目标的问题，但当需要交互性、快速周转或非 C 特性（例如，运行时代码生成或保证的尾调用优化）时，这是不可接受的。

即使你准备好支付本地代码编译的成本，你可能仍然关心解释器的性能，因为像 HotSpot 这样的混合模式 JIT 编译器会对每段代码的首次执行使用解释器；解释器产生性能分析数据，以确定在何处以及如何投入优化工作。解释器越快，你就可以等待更长的时间再进行本地代码编译，从而编译更少的代码（因此编译时间更短或优化更好）并获得更好的性能分析信息（从而优化更好）。HotSpot 系统费了很大力气来使解释器变得快速。

有些人认为效率在解释器中不重要，因为它们反正都很慢。然而，这种态度可能导致解释器在许多程序上比优化编译器产生的本地代码慢 1000 倍以上 [1], 而高效解释器的减速仅为 10 倍 [3]。也就是说，慢速解释器和快速解释器之间的差异，比快速解释器和本地代码之间的差异还要大。

另一个论点是，解释型程序大部分时间花费在本地代码库中，因此加速解释引擎不会为这些程序带来加速。然而，在项目开始时，花费在库中的时间量不一定是已知的，而且如果库没有覆盖所有功能，并且需要使用简单操作执行大量计算，那么减速超过 1000 倍的前景是令人望而生畏的。此外，拥有一个高效的解释器会增加库主导运行时间的应用程序数量。例如，考虑一个应用程序，如果使用优化本地代码编译器编译，它将花费 99% 的时间在库中：使用高效解释器（非库代码减速 10 倍），它将花费 90% 的时间在库中（整体减速为 1.1 倍于优化的本地代码），而使用低效解释器（减速因子 > 1000），它将花费不到 10% 的时间在库中（整体减速 > 10）。

你可能还会问另一个问题：为什么关注高效解释器？为什么不看看最流行的那些，比如 Perl？Perl 已经被 Romer 等人 [1] 研究过，结论是它应该通过软件手段来改进。在本文中，我们关注的是已经应用了这些手段的解释器。如果 Perl 社区某一天决定解释器效率是重要的（而且看起来他们确实为 Perl6 这样做了），重写的 Perl 解释器将具有与我们在本文中研究的高效解释器相似的性能特征，所以本文对于一个具有更高效解释器的 Perl 版本也将是有用的。

1.2 本地代码编译器¶

本节在速度和实现工作量上对解释器与本地代码编译器进行定量比较：

Ocaml 系统是进行这种比较的一个很好的候选者，因为它包含一个具有许多目标（目前有 8 个架构）的优秀本地代码编译器，以及一个快速的解释器。我们在本节中考察 Ocaml-3.06。

所有编译器都有 5995 行的通用代码；字节码编译器有额外的 3012 行代码；本地代码编译器有额外的 7429 行目标无关代码和每个目标额外的 952-2526 行代码。此外，本地代码需要 1282 行目标无关的运行时系统代码和每个目标 326-550 行的目标特定运行时系统代码（有时是目标/操作系统组合）。确定解释器特定的运行时系统的大小并不容易（因为它没有与通用的（对所有）运行时系统分开组织，例如，垃圾回收器），但字节码解释器本身有 1036 行。解释器适用于本地代码编译器支持的所有目标以及一些额外的目标，没有目标特定的代码。总的来说，即使只有一个目标，基于解释器的实现也比本地代码实现小得多，并且随着每个额外目标架构的增加，差异会越来越大。

关于执行速度，Ocaml FAQ (http://caml.inria.fr/ocaml/speed.html) 报告说，Ocaml 本地代码编译器比 Ocaml 解释器快 2-15 倍（平均：6 倍）。

关于编译速度，在一台 800MHz 21264 机器上编译一个 4296 行的文件（tk.ml），使用字节码编译器需要 5.5 秒的 CPU 时间，而使用本地代码编译器需要 40.2 秒的 CPU 时间，所以字节码编译器快了大约 7 倍。

1.3 概述¶

我们首先介绍解释器实现技术（第 2 节），然后介绍我们的基准测试及其基本性能特征，特别是间接分支的高频率（第 3 节），接着介绍使间接分支变快的方法（第 4 节），并使用周期精确的模拟器在我们的基准测试上对它们进行评估（第 5 节）。最后，我们提出一些加速解释器的方法（第 6 节）。我们在第 7 节讨论相关工作。

2. 实现高效解释器¶

本节讨论如何实现高效解释器。我们对高效解释器没有精确的定义，但“为良好通用性能而设计”这个模糊的概念已经直接指向了具体的实现技术。

如果我们想要良好的通用性能，我们不能假设解释的程序会花费大量时间在本地代码库中。相反，我们必须为最坏的情况做准备：解释一个执行大量简单操作的程序；在这样的程序上，解释器相对于本地代码是最慢的，因为这些程序每单位有用工作需要最多的解释器开销。

为了避免重复解析源程序的开销，高效的解释系统将程序编译成一种中间表示，然后解释这种表示（这种设计也有助于模块化）。

为了最小化解释中间表示的开销，高效的解释系统使用一种扁平、顺序的操作布局（与例如基于树的中间表示相反），类似于机器码；因此，这种中间表示被称为虚拟机 (VM) 代码²。高效解释器通常使用 VM 解释器，但并非所有 VM 解释器都是高效的。

精心设计的 VM 既为从源语言轻松编译而量身定做，也为在真实机器上快速解释而设计。这使得编写一个从源语言到 VM 的快速编译器变得容易，而不会因为解释开销而损失太多性能。

VM 指令的解释包括访问指令的参数，执行指令的功能，以及分派（获取、解码和启动）下一条指令。分派是所有 VM 解释器共有的，并且（正如我们将在第 5 节中看到的）可以构成解释器运行时间的大部分，所以本文专注于分派。

直接线程化代码 (Direct threaded code) [4] 是分派下一条 VM 指令的最有效方法。直接线程化代码通过实现该指令的例程地址来表示 VM 指令（见图 3）。VM 指令分派包括获取 VM 指令、跳转到获取的地址，并递增指令指针³。

不幸的是，直接线程化不能在 ANSI C 和其他没有一级标签（first-class labels）且不保证尾调用优化的语言中实现。

幸运的是，有一种广泛可用的语言拥有一级标签：GNU C (版本 2.x)；因此，直接线程化可以被可移植地实现（见图 1）。如果需要考虑在没有 gcc 的机器上的可移植性，通过使用宏和条件编译，可以很容易地在直接线程化和符合 ANSI C 的方法之间切换。

Romer 等人 [1] 在更广泛的意义上使用虚拟机，基本上涵盖了所有解释器，包括字符串解释器。
直接线程化代码是实际使用中最有效的方法，因为所有 VM 指令分派方法都使用间接分支或调用（分支地址为分支预测提供相同或更少的上下文），而直接线程化代码使用最少的额外开销。一个有趣的问题是，使用条件分支树进行分派是否会比使用间接分支更快；我们对此表示怀疑，因为 VM 指令分派有许多可能的目标，没有强烈的偏向性，所以这样的分派总是会经过几个条件分支，即使它们都被正确预测，也会耗费时间；并且不能保证预测失误会比间接分支少。

typedef void *Inst;

void engine()
{
    static Inst program[] = { &&add /* ... */ };
    Inst *ip = program;
    int *sp;

    goto *ip++; /* 分派第一条 VM 指令 */

add:
    sp[1]=sp[0]+sp[1];
    sp++;
    goto *ip++; /* 分派下一条 VM 指令 */
}

图 1：使用 GNU C 的“标签即值”实现的直接线程化代码

typedef enum {
    add /* ... */
} Inst;

void engine()
{
    static Inst program[] = { add /* ... */ };
    Inst *ip = program;
    int *sp;

    for (;;)
        switch (*ip++) {
        case add:
            sp[1]=sp[0]+sp[1];
            sp++;
            break;
        /* ... */
        }
}

图 2：使用 switch 的指令分派

[此处忽略了图 3：MIPS 汇编中的直接线程化代码及其分派序列示意图]

[此处忽略了图 4：汇编中的 Switch 分派示意图]

那些将自己限制在 ANSI C 的实现者通常使用巨大的 switch 方法（图 2）：VM 指令由任意整数标记表示，switch 使用该标记来选择正确的例程。

图 3 和图 4 展示了这两种技术的 MIPS 汇编代码。两种方法每执行一条 VM 指令都会执行一次间接分支，因此在解释主要由简单 VM 指令组成的程序时，已执行间接分支的比例相对较高（见第 3 节），它们对运行时间的影响甚至更高（见第 5.2.2 节）。

switch 方法相对于直接线程化的执行时间惩罚是由范围检查、表查找、大多数编译器生成的分派例程跳转，以及（我们将在第 5.2.4 节看到）在某些处理器上更高的间接分支预测失误率造成的。

3. 基准测试¶

本节描述我们基准测试的解释器，并给出一些关于它们行为（特别是间接分支的频率）的数据。它还讨论了为什么 Perl 和 Xlisp 不能代表高效解释器。

我们基准测试的解释器是⁴：

Gforth 0.4.9-19990617，一个 Forth 系统 [5]；它使用一个虚拟堆栈机。我们为间接线程化代码⁵ [6] 编译了它（即，在指令加载和间接分支之间有一个额外的加载指令）。我们使用的负载是 prims2x，一个小语言的编译器，和 bench-gc，一个保守的垃圾回收器。
Ocaml 2.04，Objective CAML 的“字节码”⁶ 解释器，它也实现了一个虚拟堆栈机 [7]；VM 对带标签的数据进行操作（有一些相关的开销），但不进行运行时类型检查；Ocaml 使用带标签的数据来支持多态和垃圾回收。我们运行了使用直接线程化代码的版本和基于 switch 的版本（Ocaml 为此做好了准备，我们只需更改一个配置选项）。我们使用的负载是 ocamllex，一个扫描器生成器，和 ocamlc，Ocaml 编译器。
Scheme48 0.53；这个解释器是基于 switch 的，使用一个虚拟堆栈机，使用带标签的数据并执行运行时类型检查 [8]。我们使用 Scheme48 编译器作为负载（构建 scheme48.image 的前 10⁸ 条指令）。
Yap 4.3.2，一个 Prolog 系统，使用基于 WAM（一种虚拟寄存器机）的解释器；它使用带标签的数据并执行运行时类型检查 [9]。与 ocaml 一样，我们运行了使用直接线程化代码的版本和使用 switch 分派的版本。我们使用的负载是 boyer，一个定理证明器的一部分，和 chat_parser，一个英语解析器。
Perl SPEC95 基准测试。这个解释器使用一个链表中间表示并对其进行解释。我们使用 SPEC95 train/jumble 基准测试作为负载。
Xlisp SPEC95 基准测试 li。Xlisp 解释 S-表达式（Lisp 数据的列表/树状中间表示）。我们使用 SPEC95 ref/boyer⁷ 程序作为负载。

你可以通过 http://www.complang.tuwien.ac.at/anton/interpreter-arch 找到这些基准测试。
我们无法在 SimpleScalar 上为直接线程化代码编译 Gforth。
实际上指令占用 32 位。
Lisp Boyer 与我们用于 Yap 的 Prolog Boyer 有关，但结果可能不具可比性。

[此处忽略了图 5：我们基准测试的指令类别分布表]

我们使用 Gforth、Ocaml、Scheme48 和 Yap 作为高效解释器⁸ 的例子。我们相信这些解释器是高效的，因为关于它们的论文 [5, 7, 8, 9] 表明它们的作者关心性能；对于 Scheme48，性能似乎不如其他高效解释器重要，但它仍然是一个快速的系统，并与本文讨论的其他高效解释器共享性能特征。Gforth 和 Ocaml 字节码解释器效率的另一个标志是，它们在“计算机语言大比拼”（http://www.bagley.org/~doug/shootout/）的许多基准测试中都是最快的解释器。

我们加入 Perl 和 Xlisp 是为了与相关工作 [10] 进行比较，并且因为它们在 Spec95 基准测试套件中（它们也是 Spec95 套件中间接分支最密集的基准测试）。我们选择了具有非平凡大小的负载，并为大多数解释器使用了两个负载，以避免过分强调某些非代表性的性能方面。

我们为 SimpleScalar 2.0 微处理器模拟器 [11] 编译了解释器，该模拟器模拟一个类似 MIPS 的架构。这些基准测试行为的一些基本数据列在图 5 中。

inst. exec. 列包含了模拟中执行（并提交）的指令数量。接下来的列指定了加载、存储、分支（所有控制转移）和间接分支（不包括返回）的比例；然后你看到间接分支的绝对数量，最后是每条间接分支执行的指令数（即，间接分支比例列的倒数）。我们从间接分支数量中排除了返回指令，因为它们不用于解释器分派，并且可以用返回地址栈轻松准确地预测。

你可能会想知道为什么没有 JavaVM 解释器。原因是，我们不知道有任何能在 SimpleScalar-2.0 上运行的高效 JavaVM 解释器。

这些数据中对本文重要的方面是高效解释器中间接分支的比例极高：3.2%-13%⁹；相比之下，间接分支预测研究 [10] 中使用的基准测试最多执行 2.1% 的间接分支。

所有这些间接分支的原因是，每条 VM 指令都至少执行一次间接分支，无论是使用线程化代码还是 switch 分派。大多数 VM 指令非常简单（例如，将栈顶的两个数相加），并且可以在几个本地指令加上分派代码中实现。复杂的 VM 指令相对较少出现，并且它们的设置通常需要许多简单的 VM 指令；此外，复杂操作有时被拆分成几个 VM 指令，因为这允许在编译器中优化特殊情况和/或简化解释器（类似于 CISC/RISC 的转变）。

Yap 和 Scheme48 每条 VM 指令有更多的本地指令，这可以由 Scheme 和 Prolog 所需的动态类型检查来解释；此外，Scheme48 使用 switch 分派，而 Yap 的 VM 是一个寄存器机，这在指令解码和操作数访问上通常需要比堆栈机更多的开销（然而，一个复杂的编译器可能会生成更少的这些指令）。另外，Scheme48 为了其他目标牺牲了一些效率。

另一个可以很好看到的问题是线程化代码与 switch 分派对指令计数的影响；两种情况下间接分支的数量完全相同，但使用 switch 分派的解释器的总指令数更高（对于 ocamllex，高出 1.76 倍）。对于 Ocaml，switch 分派比线程化代码多花费 5.9–6.6 条指令，对于 Yap，差异是 7.9 条指令。第 5.2.4 节展示了这些差异如何影响执行时间。

同样可以清楚地看到，Perl 和 Xlisp 不共享高效解释器的间接分支特性。

注意，如果 Gforth 使用直接线程化代码而不是间接线程化代码，它每条间接分支会少一个加载，从而导致更高比例的间接分支。

4. 快速的间接分支¶

像所有分支指令一样，间接分支在当前 CPU 中可能很慢，因为如果预测失误，它们需要冲刷流水线。不幸的是，许多 CPU 要么根本不预测间接分支，要么预测得很差。在本文中，我们考察几种预测间接分支的架构和微架构方法，以及它们在各种 VM 解释器上的工作效果。

除非采取特殊措施，否则条件分支和间接分支在现代流水线处理器中是相对昂贵的操作。原因是它们通常只有在到达执行阶段（在 Pentium III 中是第 10 阶段，在 Pentium 4 中是第 17 阶段）后才生效，但它们的结果会影响指令获取阶段（第 1 阶段）；也就是说，在这样的分支之后，新获取的指令必须经过许多流水线阶段才能到达执行阶段。由此产生的延迟现在被称为预测失误惩罚。相比之下，普通 ALU 操作的结果在执行阶段结束时可用，并且通常被后续指令在执行阶段开始时需要，导致 ALU 指令和后续指令之间有一个周期的延迟。

当然，这个问题已经通过各种架构和微架构方法得到了解决。然而，大多数努力都集中在条件分支和过程返回上，而间接分支被忽略了；即使在今天，一些 CPU 在销售时也没有任何减少间接分支成本的方法（例如，AMD K6-2, MIPS R10000, UltraSPARC II）。

4.1 间接分支预测¶

避免预测失误惩罚的一种方法是正确预测分支的目标，并推测性地执行那里的指令。当然，如果预测不正确，推测性执行的指令必须被取消，CPU 会招致预测失误惩罚。

4.1.1 基于性能分析的预测 (PROFILE-GUIDED PREDICTION)¶

Alpha 架构具有间接分支目标提示：JMP 指令中的一个字段指定了预测分支目标的 16 位（这应该足以预测 I-cache 中的一条指令）。这可以被带有性能分析反馈的编译器用来预测间接分支。不幸的是，我们知道的编译器不支持这种方式来帮助解释器：gcc-2.95.2 的 -fprofile-arcs 不支持计算型 goto；Compaq C 编译器只支持 switch 分派并只产生一个间接分支，这将预测准确率限制在约 10%（见第 5 节）。这种预测方法的另一个缺点是，必须先解码分支，这意味着即使预测正确，也存在分支执行惩罚（解码阶段之前的周期）。

4.1.2 动态预测 (DYNAMIC PREDICTION)¶

动态分支预测是一种微架构机制，无需架构、编译器或软件支持即可工作（但软件支持可以提供帮助，见第 6.3 节）。最简单的动态间接分支预测机制是分支目标缓冲器 (Branch Target Buffer, BTB)，它缓存分支最近的目标地址；它使用分支指令的地址作为查找的键。

对普通 BTB 的一个改进是带 2 位计数器的 BTB，它仅在预测失误两次后才替换 BTB 条目¹⁰；如果一个分支通常跳转到一个目标，但有一些例外，这会将预测失误减半。这种 BTB 于 1993 年随 Pentium 引入，并且仍然是商用 CPU 中可用的最复杂的间接分支预测方法。

目前已知的最佳间接分支预测机制是两级预测器，它将 n 个间接分支目标的全局历史模式与分支地址相结合，并使用它在表中查找目标地址；这些预测器由 Driesen 和 Hölzle [10] 提出，他们研究了这些预测器的许多变体；他们没有研究的一个问题是（可能是因为他们使用了基于踪迹而不是执行驱动的模拟器），分支的真实目标只有在预测很久之后才可用，并且不能立即用于更新历史模式和表（见第 5 节）。

我们将在第 5 节中讨论各种预测机制对解释器的影响。

实际上，如果 BTB 仅用于间接分支预测，一位就足够了。使用这个名字是因为条件分支预测器中的相应结构使用两位饱和计数器。而且，例如，Pentium 每个条目有两位，因为这些条目也用于条件分支预测。

4.2 预测失误惩罚¶

减少分支成本的另一种方法是减少预测失误的惩罚，而不是或除了减少预测失误的数量。

一种方法是使用延迟分支。延迟分支在桌面和服务器机器的架构中失宠，因为为了获得最大效益，它们需要有实现相关的延迟槽数量，这会破坏二进制兼容性。然而，在各种用于嵌入式系统的 CPU 中，延迟分支被积极使用，并且在实现解释器时可以很好地使用它们 [3]。

一种比延迟分支更灵活（更少依赖于实现）的方法是分离式分支 (split branches)，其中一个准备分支指令指定分支目标，而分支实际生效的点被明确指定。在 Power/PPC, HP PlayDoh, 和 IA64 架构中，准备分支指令指定一个分支寄存器来包含目标地址，但其他方法也是可能的 [12]。

举个例子，让我们看看 Power/PPC 架构：准备分支指令被称为 mtctr，而实际的控制转移指令是 bctr¹¹。在最初的 Power 实现（以及许多后续版本）中，这些指令之间的延迟是五个周期（用于将地址送入分支单元，并开始获取和解码目标），但实际的控制转移随后立即发生。

然而，对于延迟分支和分离式分支，处理器必须在跳转到该地址生效之前，获取、解码和执行加载下一条 VM 指令地址的加载指令。这意味着执行一条 VM 指令至少需要一个加载从指令获取阶段到结果阶段的时间。

这个问题可以通过将加载移动到前一条 VM 指令中来减少，实质上是对解释器进行软件流水线 [3]。然而，当我们将加载跨越前一个跳转移动时，我们必须重命名结果寄存器。做到这一点的简单方法是使用一条移动指令¹²（PowerPC, PlayDoh, 和 IA-64 的准备跳转指令是一种移动指令，所以不需要额外的指令）；然而，这条移动指令也必须在跳转生效前被获取、解码和执行，从而决定了最小的 VM 指令执行时间：获取、解码和执行移动，然后执行间接跳转。

这些方法的另一个问题是次优的编译器支持：例如，gcc-2.95 没有像人们希望的那样尽早地调度准备分支指令。

还有一对 mtlr/blr，使用另一个分支寄存器，但它仅用于返回地址，并且 PPC 7450 使用返回栈来预测 blr 的目标。
另一种方法是复制整个解释器来执行模变量重命名，但这相当复杂，特别是对于线程化代码。

5. 评估¶

本节展示了间接分支的预测失误惩罚如何影响解释器，以及各种分支预测方案如何提供帮助。

5.1 模拟设置¶

我们向 SimpleScalar-2.0 模拟器添加了几种分支预测方法，并使用以下预测方法运行了解释器：

无预测 (No prediction) 处理器只能等到分支解析。
基于性能分析 (Profile-Guided) 预测一个间接分支总是跳转到训练运行中最频繁的地址。我们通常为训练运行使用一个不同的解释程序（除了 Scheme48，但它仍然得到非常低的预测准确率）。
BTB 预测一个分支总是跳转到它上次跳转的目标（无限表大小）。
BTB2 一种仅在第二次失误时才替换预测的 BTB（无限表大小）。
2-Level 使用分支地址和包含最后 1-8 个目标地址的历史寄存器作为查找表键的两级预测器，查找表中包含预测目标和两位计数器 [10]。我们使用地址的所有位和无限大小的表。你可以将 BTB2 视为历史寄存器中包含 0 个目标地址的 2-Level 预测器。我们无法在周期精确的模拟器中使用这个预测器，因为处理器直到指令提交后才知道真实的目标地址。因此我们使用这个预测器的两个变体：
2-Level-speculative 类似于 2-level，但历史寄存器包含最后 n 个预测的目标。当从预测目标获取指令时，历史寄存器被推测性地更新。如果在任何时候检测到预测失误，历史寄存器保持不变（不执行回滚）。
2-Level-committed 类似于 2-level，但历史寄存器包含最后 n 个已提交的地址（注意提交可能在另一个间接分支已经被预测之后发生）。

SimpleScalar 可以改变预测失误惩罚。这使我们能够了解各种硬件技术在减少预测失误惩罚方面的效果。SimpleScalar 模拟一个带有短流水线的乱序处理器：指令获取、解码/分派、执行、写回、提交。一个间接分支必须在分派阶段等待，直到目标地址可用；然后它通过执行和写回阶段；如果分支被预测失误，它在加载地址的指令执行写回后的下一个周期从正确的地址获取指令，如果我们设置最小的预测失误惩罚；这通常被称为 4 个周期的预测失误惩罚（SimpleScalar 称之为 1 个周期，但我们通篇遵循更传统的用法）；注意，乱序执行甚至可以提高实际的预测失误惩罚。

如果我们设置更高的预测失误惩罚，从分支在执行阶段到获取正确指令之间将经过相应数量的周期；你可以将这看作是模拟一个具有更多指令获取和解码阶段的处理器。

无限表大小对于硬件实现来说是不现实的，但我们认为结果比看一个特定的现实配置更有趣，因为那个配置可能会产生令人困惑的假象（例如，来自冲突失误），而这些假象在另一个配置或小的代码更改后不会出现。此外，至少对于两级预测器，无限模型与具有大表尺寸的精心调整的现实模型非常接近 [10]。

除了间接分支预测器和预测失误惩罚，我们主要使用了 SimpleScalar-2.0 的默认处理器配置：一个能够每个周期发射四条指令的超标量处理器，具有通常的额外限制（例如，只有两个 L1 缓存端口）；从 L1 缓存的加载延迟是两个周期。我们配置的条件分支预测器比默认的稍好：一个由双峰预测器和两级自适应预测器组成的组合预测器，每个表有 4096 个条目，两级预测器的历史长度为 12。我们还将返回地址栈的大小增加到 64。

5.2 结果¶

5.2.1 预测准确率¶

[此处忽略了图 6：各种预测器在解释器上的预测失误率图表]

图 6 显示了解释器的预测失误率。我们在间接分支预测准确率上看到了四种不同的模式：

线程化代码 (Threaded code) 基于性能分析的预测产生 71%-88% 的预测失误，BTB 为 57%-63%，BTB2 为 50%-61%。
基于 Switch 的代码 (Switch-based code) 基于性能分析的预测产生 84%-100% 的预测失误。BTB 和 BTB2 对 ocaml 和 scheme48 产生 98% 的预测失误，对 Yap 产生 81%-86% 的预测失误。
li 基于性能分析的预测、BTB 和 BTB2 表现相当好（14%-21% 的预测失误）。这个结果的原因是，在 li 中大多数动态间接跳转执行动态类型解析，而不是解释器分派，而且 boyer 程序显然主要处理一种特定的数据类型。
perl 基于性能分析的预测、BTB 和 BTB2 产生约 75% 的预测失误。

两级预测器的预测准确率相对较好（通常低于 10% 的预测失误），适用于所有解释器。

线程化代码和基于 switch 的代码之间准确率差异的原因是，线程化代码为每个 VM 指令使用一个单独的分派例程，这允许基于性能分析的预测和 BTB 为每个 VM 指令预测一个不同的目标。也就是说，通过单独的分派例程，预测器有更多的上下文可用于预测（一种单深度历史）。

相比之下，对于一个公共的分派跳转，这些预测器无论从哪里来，都必须预测同样的事情，导致性能更差。基于性能分析的预测器只预测最常用的 VM 指令。BTB 预测最后执行的指令；显然，这个预测对于基于寄存器的 Yap 比对于基于堆栈的 Ocaml 和 Scheme48 解释器更准确。

5.2.2 对执行时间的影响¶

[此处忽略了图 7：各种解释器在各种分支预测方案下，预测失误惩罚为 4 个周期时的执行时间图表]

图 7 显示了不同预测准确率对执行时间的影响，假设预测失误惩罚较短。为了更清楚地看到细节，图 8 以不同的尺度显示了相同的数据（不包括 li 和 perl）。

[此处忽略了图 8：高效解释器在各种分支预测方案下，预测失误惩罚为 4 个周期时的执行时间图表（放大版）]

在高效解释器中，几乎所有的间接分支都执行 VM 指令分派，所以你可以假设每个间接分支的周期数也代表每个 VM 指令的周期数。

在大多数情况下，无预测和 “2-level spec. 8” 之间的预测准确率差异导致执行时间差异主要在 4 个周期（ocamlc）和 6.6 个周期（scheme48build）之间，有一个 10.4 个周期（li-boyer）的异常值。注意，这些差异可能大于纯粹的分支预测惩罚，因为间接跳转可能依赖于其他必须先解析的指令。

[此处忽略了图 9：高效解释器在各种分支预测方案下，预测失误惩罚为 13 个周期时的执行时间图表]

高效解释器与其他解释器之间的区别在于，对于高效解释器，这个差异构成了执行时间的一个更大部分。例如，gforth-benchgc 使用 “2-level spec. 8” 每个间接分支需要 3.5 个周期，而没有分支预测则需要 9 个周期，即，从分支预测中可以获得 2.55 倍的执行时间增益，或者换个角度看，没有间接分支预测，这个基准测试将其 61% 的时间花在间接分支上。相比之下，无预测和 “2-level spec. 8” 之间的因子对于 li-boyer (1.20) 和 perl-jumble (1.06) 来说要小得多。

随着更长、更现实的预测失误惩罚（图 9），预测失误对运行时间的影响甚至更具戏剧性。例如，在 13 个周期的预测失误惩罚下，无预测和 “2-level spec. 8” 之间的因子对于 gforth-benchgc 是 4.77（或者说 79% 的时间花在间接分支上）。

5.2.3 改变预测失误惩罚¶

[此处忽略了图 10：gforth-benchgc 在不同惩罚和间接分支预测器下的执行时间变化图]

图 10 显示了其中一个基准测试的运行时间如何随预测失误惩罚而变化：它几乎线性地上升。其他基准测试也表现出线性行为。

这让我们感到惊讶：我们最初期望，在一系列正确的预测和足够的获取/解码带宽下，解释器分派会领先于 VM 指令执行的其余部分，因为分派的依赖性较少（每条 VM 指令只有一个指令指针更新）；然后，执行旧 VM 指令和预测失误之间的重叠应该会使图 10 中低预测失误惩罚的曲线变平。

然而，这种重叠并没有大量发生（我们看了一些踪迹，并用更多资源的配置进行了实验来证实这一点）。原因是，分派中的加载依赖于 VM 指令执行其余部分的存储（特别是在堆栈 VM 中的堆栈溢出和在寄存器 VM 中的结果寄存器写入）。我们可能会在一个能够推测性地执行加载，甚至在地址未知的存储之前的处理器上看到稍有不同的结果。

这种线性行为的一个好处是，它使得分析和预测行为变得容易：将预测失误的数量（所有类型的分支）减半与将预测失误惩罚（包括间接分支依赖的未完成指令的延迟）减半具有相同的效果。从当前的硬件（即 BTB 风格的间接分支预测器）开始，通过增加一个 2-level 间接分支预测器来加速高效解释器，可能比通过等效量缩短预测失误惩罚要容易得多。

5.2.4 线程化代码 vs. Switch 分派¶

线程化代码和 switch 分派之间的运行时间差异来自于不同的预测失误率，以及由于额外执行的指令而产生的差异。

[此处忽略了图 11：在各种分支预测器下，线程化代码和 switch 分派之间的速度差异表]

图 11 显示了在 SimpleScalar 上，4 个周期预测失误惩罚（SimpleScalar 术语中的 1 个周期）下线程化代码和 switch 分派之间的整体差异。

对于基于性能分析、BTB 和 BTB2，差异比没有预测器时更大，因为 switch 分派在这些预测器上有显著更多的预测失误。对于两级预测器，差异比没有预测器时更小，因为 switch 分派和线程化代码在这种预测器上有相似的预测失误率，并且正确的预测允许通过与后续代码重叠来隐藏 switch 代码的延迟。

考虑到线程化代码 VM 指令的执行时间很短，使用 switch 分派会慢多达 2.02 倍（ocamllex 使用 BTB2 和 4 个周期预测失误惩罚）。

5.2.5 低效解释器¶

Xlisp 和 Perl 的行为与其他解释器非常不同。Xlisp 对所有预测器都有很低的预测失误率。我们检查了代码，发现大多数动态执行的间接分支不是选择下一个要执行的操作，而是对对象上的类型标签进行 switch。大多数对象是相同类型的，所以这些 switch 是非常可预测的。Perl 的预测失误率与其他解释器更一致，但图 7 显示，提高预测准确率对 Perl 的影响很小。非返回的间接分支实在太少了（只有 0.7%），无法产生太大影响。

5.2.6 两级预测器¶

[此处忽略了图 12：Scheme48 build 的两级间接分支预测器准确率图] [此处忽略了图 13：Yap chat 的两级间接分支预测器准确率图]

在本节中，我们岔开话题，更仔细地看看我们的两级间接分支预测器的变体。请注意，本节不像某些人可能希望的那样深入，因为间接分支预测器不是本文的主要主题。

我们测量了历史长度最多为八的 2-level-speculative 和 2-level-committed 预测器。基准测试之间存在显著差异；我们认为这是由于被解释程序中的差异，而不是解释器中的差异。图 12 和 13 显示了两个例子。无论如何，只要有足够的历史长度，两种预测器通常都工作得很好。

更长的历史通常更好，但并非总是如此；我们的解释是，预测器会根据被解释程序的内部循环或频繁执行的过程进行训练；如果循环的行程计数很小，更长的历史会有太多的开销。对于某些基准测试，推测性预测器更好，对于其他基准测试，基于提交的预测器更好。这表明 2-level-speculative 和 2-level-committed 可能作为混合预测器 [13, 10] 的组件而有用。

5.2.7 真实世界结果¶

本节通过呈现来自真实机器的数据来支持模拟结果的有效性。我们使用 Athlon 的性能监控计数器生成了数据。数据不直接可比，但结果支持我们从模拟中得出的一些结论。差异在于：Athlon 的架构与 SimpleScalar 不同，并且计数的事件也不同（特别是，我们必须将采用的分支作为间接分支的最接近的可用近似）；我们使用了一个新版本的 Gforth，因为它支持一个允许改变某些参数的优化。我们使用 gforth-benchgc 基准测试，因为该基准测试执行的直接分支相对较少，所以将采用的分支计数作为间接分支数量的近似应该在这个基准测试中效果最好。

我们测量到 gforth-benchgc（无优化）中 55% 的采用分支被预测失误，这与我们在 SimpleScalar 上看到的 BTB 的 60% 的间接分支预测失误率相差不远（Athlon 使用 BTB）。

当激活超指令优化（见第 6.3 节）时，已执行的真实机器指令数量减少了 1.22 倍，采用的分支数量减少了 1.49 倍，采用分支的预测失误数量减少了 2.28 倍，我们看到执行时间减少（因子 1.74）高于已执行指令和采用分支的减少。这表明预测失误的数量对该基准测试的执行时间比已执行指令的数量更重要。

Gforth-benchgc（无超指令）每 20 个周期执行一次预测失误。Athlon 的分支预测失误惩罚为 10 个周期，所以很容易看出这个基准测试将其一半的时间花在预测失误上（可能还有更多时间等待目标地址）。

6. 建议¶

6.1 硬件设计者¶

对于高效解释器来说，最有用的硬件支持特性是良好的间接分支预测。两级预测器对于解释器以及涉及间接分支或间接调用的其他应用程序（例如，面向对象的程序）都工作得很好。对于我们测量的解释器，在 4 个周期的预测失误惩罚下，两级预测器相比 BTB2 实现了高达 1.97 倍的加速，在 13 个周期的预测失误惩罚下，实现了高达 3.08 倍的加速。

即使只是拥有一个 BTB 也能对线程化代码有很大帮助，并且通过对解释器的适当更改 [14]，它们的预测准确率可以非常好。

6.2 C 编译器作者¶

C 编译器作者可以通过用每个 VM 指令的分派片段的副本来替换单一、共享的 switch 分派代码片段，来提高基于 switch 的解释器（以及可能的其他软件）的性能。这可以通过消除返回到 switch 代码的无条件分支（尾部复制）来实现。这种优化会将预测准确率提高到我们用线程化代码看到的相同水平。我们估计这种优化可以在带有 BTB2 预测器的处理器上提供高达 1.5 倍的加速因子。

C 编译器帮助解释器性能的另一种方式是支持 GNU C 的标签即值扩展，这允许实现线程化代码。线程化代码可以比带有共享分派片段的 switch 分派提供高达 2.02 倍的加速因子（见第 5.2.4 节）。

另外，保证尾调用优化将是支持线程化代码的另一种方式 [15]。

在支持它们的架构上支持间接分支目标提示，最好是通过性能分析反馈，也会有所帮助（高达 1.17 倍的因子）。

6.3 解释器作者¶

文献中已经描述了许多编写高效解释器的技术（见第 7 节）。本节重点介绍减少间接分支所花费时间的技术及其效果。

鉴于过去 BTB 的采用速度缓慢，我们可以预期至少需要十年时间，更复杂的间接分支预测硬件才能在大多数 CPU 上可用，因此解释器作者在不久的将来将不得不迎合带有 BTB 的 CPU，并可能没有间接分支预测。

解释器作者应该支持线程化代码（见第 2 节），以获得相对于基于 switch 的解释器高达 2.02 倍的加速；为了保持最大的可移植性，应该通过条件编译提供一个基于 switch 的 ANSI C 版本。

在目前的工作之后，我们研究了如何为提高 BTB 预测准确率而改进解释器 [14]。我们发现，复制 VM 指令的代码（从而复制间接分支）并在不同地方使用不同的副本可以显著减少预测失误，类似于我们在这里看到的每个 VM 指令使用一个单独的分派分支的效果。特别是，如果我们为程序中 VM 指令的每个实例都有一个单独的副本，我们唯一的预测失误是 VM 级别的间接分支和来自 BTB 冲突的预测失误，从而在 Celeron-800 上实现了超过 90% 的预测准确率和高达 2.39 倍的加速（在 Athlon-1200 上为 2.41 倍）[14]。

将常见的 VM 指令序列组合成 VM 超指令 [16, 17] 也有助于引入更多静态间接分支，并通过减少动态执行的间接分支数量来提供帮助（后一种效果也帮助了没有 BTB 的处理器）。复制和超指令的组合在 Celeron-800 上产生了高达 3.17 倍的加速 [14]。

实现这些技术有两种方式：将一组给定的副本和/或超指令静态编译到解释器中；或者从解释器的静态副本中动态复制代码。由于动态方法可以适应手头的程序，它们产生更好的 BTB 预测准确率和（在像 Celeron 或 Athlon 这样的处理器上）更好的加速。它们也更容易实现一些，但需要一些目标特定的代码（主要是为了刷新 I-cache）和更多的内存。如果这些问题对于你的应用是可接受的，我们推荐使用带有动态复制的动态超指令 [14]。

7. 相关工作¶

我们已经在第 1 节中讨论了 Romer 等人 [1] 的研究。与我们工作最重要的区别是，他们研究的解释器不能代表高效解释器；只有 Java 使用了 VM¹³，但不是一个非常高效的 VM：它平均需要 16 个本地指令用于获取/解码（相比之下，线程化代码分派需要 3 个本地指令），以及每个 JavaVM 指令其余部分需要 18-27 个（在 Hanoi 上为 170 个）本地指令，尽管该 VM 与 Gforth 和 Ocaml 的 VM 相似（它们需要 7.6–15.8 条指令/VM 指令总数）；在 DES 基准测试上，Java 比 C 慢 119 倍。在他们测量的所有解释器的所有基准测试中，分支预测失误在 21064 上占用的周期不到 10%。相比之下，本文研究的是为高性能而编写的解释器，其中进一步的性能改进将需要复杂性的显著增加。分支预测失误是我们研究的解释器运行时间的一个主要组成部分。

我们两级间接分支预测器的基础是 Driesen 和 Hölzle 的工作 [10]。他们从 2-level 预测器开始，然后探索当他们增加越来越多的限制以使预测器在硬件中可实现时会发生什么。我们工作与他们工作的一个主要区别是，我们使用高效解释器作为基准测试，这些解释器具有比他们任何基准测试都高得多的间接分支频率（高达 13% vs. 高达 2.1%）（主要是面向对象的程序，特别是那些具有更高间接分支频率的程序），并且通常每个间接分支有更多的潜在目标。我们限制自己只使用他们的一个预测器（探索预测器不是我们的主要目标），但我们探索了他们没有研究的一个问题：正确结果只有在预测很久之后才可用，以及如何处理它。

他们还提出了一种改进，即多级级联预测，它减小了所需表的大小 [18, 19]。另一种有前途的方法利用数据压缩技术中的预测器来预测间接分支的目标 [20, 21]。同一作者还展示了如何通过将间接分支分类成组来更准确地预测它们 [22]。一种更早的两级间接分支预测方法是使用条件分支结果的最近历史来预测间接分支 [23]。虽然结果比 BTB 好，但更新的方案更准确。

基于性能分析的条件分支预测的准确性可以通过代码复制来提高 [24, 25]。类似地，复制分派代码通过提供更多上下文来提高基于性能分析的间接分支预测（以及 BTB 性能）的性能。

关于条件分支预测存在大量的工作。最重要的是两级自适应预测器，由 Yeh 和 Patt [26] 与 Pan 等人 [27] 大约在同一时间独立发明。另一个重要的发现是分支预测和用于数据压缩的预测器之间的联系 [28]，它为分支预测建立了一个理论基础。Uht 等人 [29] 对许多现有的直接分支预测方案做了很好的介绍。

关于解释器的许多知识都是民间传说。Usenet 新闻组 comp.compilers 中的讨论包含了许多民间智慧和个人经验报告。

可能目前对解释器最完整的处理是 [30]。它还包含一个广泛的参考书目。另一本包含几篇关于解释器效率文章的书是 [31]。大多数关于解释器的已发表文献集中在解码速度 [4, 32]、语义内容、VM 设计和时间/空间权衡 [32, 33]。还有一些关于解释器的更新论文，讨论诸如组合 VM 指令 [34, 16, 3]、软件流水线解释器 [3]、堆栈缓存 [15]、提高 BTB 预测准确率 [14] 和各种优化 [9, 17] 等问题。

MIPSI 直接模拟一个真实机器 (MIPS)。性能可以通过翻译成一个 VM 来提高，但在这种应用中，复杂性和性能之间的权衡对于 VM 方法不如在编程语言解释器中那么有利。

8. 结论¶

高效解释器执行大量的间接分支（在我们的基准测试中高达 13%）；没有间接分支预测，由此产生的预测失误即使在具有短流水线的处理器上也可以占用大部分时间（高达 61%，对于更长的流水线则更多）。

如果解释器对所有 VM 指令使用单一、共享的分派例程（例如，在许多编译器上的 switch 分派），商用分支预测机制表现不佳（0%-19% 的准确率）。如果每个 VM 指令有一个分派例程的副本（例如，使用线程化代码），这些分支预测器表现稍好一些（BTB 的准确率为 37%-50%，基于性能分析的预测为 12%-29%）。两级间接分支预测器表现相当好（通常 > 90% 的准确率），但尚未在广泛可用的 CPU 中实现。

使用线程化代码的解释器比使用 switch 分派的解释器快多达两倍，因为 switch 分派执行更多的本地指令，并且其在 BTB 上的预测准确率更差。提高解释器性能的进一步方法是：复制 VM 指令可以产生更好的 BTB 预测准确率；将 VM 指令序列组合成超指令可以减少 BTB 预测失误的数量和间接分支的数量。这些技术可以组合使用，在像 Pentium-III、Athlon 和 Pentium 4 及其亲属这样的处理器上提供良好的加速。

像基于性能分析的分支预测和准备分支指令这样的架构机制在理论上可以提供帮助，但在实践中往往因缺乏编译器支持（特别是 GCC）而受苦。GCC 是编写高效解释器时的首选编译器，因为它的标签即值扩展使得使用线程化代码成为可能。

致谢¶

Vitor Santos Costa 在让 Yap 在 SimpleScalar 上运行方面提供了很大帮助。Asplos ‘00、CC ‘01、Euro-Par ‘01 和 JILP 的审稿人对本文的早期版本提供了许多有益的评论。