C++ 调度技术深度解析

标题：A Deep Dive Into Dispatching Techniques in C++

日期：2023/07/23

作者：Jonathan Müller

链接：https://www.youtube.com/watch?v=vUwsfmVkKtY

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

备注一：对我有价值的演讲，虽然这些技巧是很多年前就存在的。做解释器的人应该很熟悉这一套。

备注二：没空搬运幻灯片的代码。

好的，太好了。那么，欢迎来到我的演讲。我希望大家享受这次大会。能再次回到阿斯彭（Aspen）真的非常棒。

这是一场关于性能的演讲。因此，我需要先做一个免责声明。在没有先运行你自己的基准测试之前，永远不要进行任何优化。 特别是，你不应该仅仅因为某人告诉你某个方法很快就去实现它。我所有的基准测试都是在一台 2020 年的 Apple Mac Mini 上运行的，操作系统是 Asahi Linux，编译器是 Clang 14，这很可能不是你所针对的目标平台。所以，不要直接复制我的任何基准测试结果。

在演讲期间，随时可以提问，但如果你有任何评论，请留到最后。我为了营造一些戏剧性效果，会做一些有点奇怪的事情，所以请把评论留到最后，到时候问题可能会自行解决。

所以，我将要优化一个调度循环（dispatch loop），它看起来像这样。我们有一个 while 循环，然后是一个 switch 语句，我们想让它变得更快。

我所不关心的是像 enum_to_string 这样的性能。如果这个函数成了显著的性能问题，那说明有非常严重的问题出错了。另外，这是一个从工作中提取的例子。我们公司是 think-cell。我们做一个 PowerPoint 插件，所以需要处理很多 PowerPoint 的东西。在这种情况下，我们想特别处理幻灯片母版。所以我们用一个 switch 来做这个，然后是一个 default。有人问这是否真的是最好的方法。有人把他们引向了我的演讲。

但这不是这次演讲的内容，对吧？你应该这样写代码。我们有一个 enum_set，然后我们可以请求一个子集，然后像这样做。我只想借此机会提一下，我们正在招聘。所以如果你在找工作，可以考虑申请。

我真正要谈论的是类似这样的东西。比如，我们要解析一个二进制文件。我们有一些头部信息（header），然后我们根据头部类型进行 switch，并根据它解析一些有效负载（payload）。然后我们在一个循环中重复这个过程。这最终可能会成为一个性能问题。所以我们可能需要研究一下如何让它变快。

当然，还有一个经典的例子：我们想写一个字节码解释器。我们有一系列指令，我们想相应地执行它们。这算是我研究这个问题的动机。去年夏天，我写了这个小小的字节码解释器。所以我想优化这类代码。这也是我将在整个演讲中使用的例子。

一个简单的基于栈的字节码

让我们定义一个简单的基于栈的字节码。什么是字节码？字节码是由单个字节组成的指令。所以我们有一个字节码操作码（opcode），它是一个 uint8_t 的 enum。然后我们在里面有各种指令。

一条指令要么直接是操作码，要么带有一个字节的负载。所以我们要么有一个无符号整数值，要么有一个有符号整数偏移量。

然后，字节码本身只是一个 std::vector of instruction。每条指令都以操作码开始，然后可以有多个可选的字节作为负载。

这个字节码是基于栈的。这意味着指令不访问寄存器。它们修改一个值栈（Value Stack），简称 VStack。例如，我们有一个 push 指令，它将一个常量推入 VStack。这个常量作为负载在字节码的下一个字节中指定。例如，我们可以有 ABC，然后我们想 push 42。现在 42 就在栈顶了。

我们也可以对栈进行操作。例如，add 从栈顶弹出两个值，将它们相加，然后将和推回栈中。这个指令不带任何负载。

有了这些，我们就可以写一个非常简单的例子，就是将三个数字相加。所以我们 push 1 和 2。现在 VStack 在右边显示。VStack 上有 1 和 2。然后我们执行 add，它会弹出它们并推入 3。然后我们再 push 一个 3。最后的 add 得到 6。通过这种方式，我们可以进行基本的算术运算。

VStack 的一个问题是，如果我们想两次使用同一个值，会发生什么？比如我们刚得到一个加法的结果，我们想修改它，但又想稍后再次使用它。是的。我们如何多次使用同一个值呢？为此，我们可以复制它。dup 指令简单地复制 VStack 顶部的任何内容，所以现在它在栈上出现了两次。然后我们可以只弹出一个，它仍然在那里。

一个类似的问题可能会在 VStack 中的值顺序错误时发生。例如，由于某些其他计算，我们可能在栈上推入了两个数字。现在，我们想将它们相减，但我们想以相反的顺序相减。为此，我们可以使用 swap。它简单地弹出两个值，并以相反的顺序将它们推回。还有更复杂的栈操作，但我们的例子中不需要它们。

对于控制流，我们的解释器维护一个指令指针（Instruction Pointer），简称 IP。一个正常的指令只是将指令指针增加，越过操作码和任何数据。例如，在一个 push 之后，我们会将它增加 2，因为我们有一个字节的数据。而在一个 add 之后，我们会将它增加 1，因为我们没有任何数据。

jump 指令将指令指针增加由负载指定的偏移量。这样，我们就可以实现一个循环，例如。循环结束后，我们想回到开头。这就是一个 jump 指令。

然后我们还需要条件跳转。否则，我们的循环将是无限的。这会根据一个偏移量增加指令指针，但前提是 VStack 的顶部是非零的。它会从 VStack 弹出一个值。如果它非零，它将跳转指定的偏移量。否则，它将跳过 jump 指令并正常继续。

最后，我们想要函数调用。为了简单起见，我们只允许一个函数。所以我们整个字节码程序本质上就是那个函数。它的参数在调用前被推入 VStack。当函数完成时，它会在 VStack 顶部留下一个单一的返回值，也就是函数的结果。

然后我们没有 call，只有一个 recurs。因为我们只有一个函数，所以我们只能进行递归。recurs 简单地保存指令指针并回到开头。然后我们可以在一个不同的调用帧上再次执行它。

然后是 return。当你完成时，我们想回到调用者。所以我们跳转到最后保存的指令指针。指令指针保存在调用栈（Call Stack）或 CStack 上。这是一个独立的栈，以确保我们不与值混淆。这允许我们连续调用多个函数。

作为一个例子，让我们看一个递归计算斐波那契（Fibonacci）的程序。这并不是你真正想要的实现方式，但它很好，因为它有指数级的时间复杂度，这在我们的情况下很方便，因为只需要很少的代码，我们就可以获得大量的执行次数来进行基准测试。

我们的想法是计算第 n 个斐波那契数。如果 n 小于 2，那么结果就是 n。所以第 0 个斐波那契数是 0，第一个是 1。否则，我们对前两个数求和。

这就是字节码。我们从 VStack 上的 n 开始，我们想把斐波那契数放到 VStack 上。 所以我们首先进行比较。我们不想移除 n，所以我们复制它，推入 2，然后与 2 进行比较。现在，比较的结果在 VStack 的顶部，我们进行一个条件跳转。所以如果你大于等于 2，我们就跳到下面的 duplicate。否则，我们继续执行 return。因为 n 现在在 VStack 的顶部，这就是正确的结果。所以我们直接 return，并将 n 本身返回给调用者。

否则，我们进入了那个 duplicate 指令。在这里，我们想减去 1，但也复制它，这样我们可以保留它。所以我们减去 1 然后 recurs。这将计算 n-1 的斐波那契数并将其放在 VStack 的顶部。然后我们的顺序是错的，所以我们做一个 swap 把 n 放到顶部，从中减去 2，然后再次 recurs。最后，我们在栈上有两个数，所以我们把它们相加然后 return。

你不需要理解所有关于它为什么正确的细节。用基于栈的解释器手动编程有点棘手。你只需要理解基础知识，以及每个指令独立工作的方式。我可以向你保证，这个字节码实际上是正确的。

到此为止有什么问题吗？好的。

编写解释器

那么，让我们为那个字节码编写一个解释器。我们需要维护四种状态：

  1. 指令指针 (IP)：一个指向当前字节码指令的指针。

  2. 值栈指针 (VStack Pointer)：VStack 只是一个 int 数组，VStack 指针指向 VStack 上下一个空闲的栈槽。

  3. 调用栈 (Call Stack)：这只存储指令指针，所以我们有一个这样的数组，并且也记住当前的栈顶。

  4. 字节码本身：这样我们就可以跳回到开头。

然后每个执行指令的实现都非常直接。例如，push 只是获取负载中的东西，也就是在下一个偏移量处的东西，并将其推到 VStack 的顶部。然后我们将指令指针增加 2，以转到下一条指令。

duplicate，VStack 的顶部在偏移量 -1 处，因为 VStack 指针总是在后面一个位置。所以我们取 -1，那是顶部的值，然后我们再次推入它。然后我们增加 1，因为这次字节码中没有负载。

add 或 subtract 或 comparison 等等，它们看起来都一样。我们弹出操作数，计算结果，然后把它推回 VStack，然后增加 1。

一个条件跳转，例如，它只是从 VStack 弹出一个值。如果它非零，那么我们就跳转到那个偏移量。否则，我们跳过操作码和偏移量。

recurse 在调用栈上保存指令指针。唯一需要注意的是，我们保存的是 recurse 之后的地址。否则，return 将直接跳回到 recurse，我们就会有一个无限循环，因为我们一直在递归。然后我们跳到函数的开头，也就是我们整个字节码的开头。

最后，return 简单地跳转到我们刚刚保存的位置。

解释器的入口点接受字节码和我们函数的单个参数。然后它创建一个 VStack 和一个 CStack，它们只是一些固定大小的数组。我们初始化指令指针和 VStack 指针。然后我们想先把参数推到 VStack 的顶部，并且我们还想在调用栈的顶部推入一个特殊的退出指令。这样，第一个函数的 return 就会转到这个退出指令，然后我们就可以检测到并退出解释器。然后我们只需调用 dispatch。

这就是缺失的部分。这是我们将在这次演讲的剩余部分实现的函数。它接受我们的解释器状态作为参数，读取当前的操作码，执行处理该指令所需的适当汇编代码，然后重复这个过程，直到我们到达退出指令并完成执行。

这次会议谈论了很多关于安全性的问题。所以此时我需要做一个免责声明。字节码解释器是远程代码执行漏洞的绝佳目标。 一旦你能够利用它们，你就可以控制它们。所以你永远不应该实际执行不受信任和未经验证的字节码。话虽如此，这是一场关于性能的演讲。所以我们忽略这一点，继续前进。

最基础的调度技术：Switch

我们可以用来实现字节码解释器的最基础的调度技术是 switch。它看起来像这样。我们有一个 while (true) 循环，为了简单起见。然后我们对当前的操作码进行 switch，并执行 push 或 add 或任何需要的东西。当我们到达特殊的退出指令时，我们从循环中返回，并返回 VStack 顶部的最终值。

一个限定条件。虽然我们在 switch 中实际上覆盖了每一个 enum 值，但编译器并不知道。如果我们不告诉它，它会生成一些丑陋的代码。所以我们告诉编译器我们没有 default case。否则，汇编代码会变得有点乱。所以我们忽略这一点。

至此，我基本上已经向你们展示了字节码解释器的完整实现。关于这个有什么问题吗？好的。如果你在 YouTube 上观看这个视频，你也可以在 GitHub 上找到源代码。

要理解编译器对 switch 做了什么，我们必须看看生成的汇编代码。这里有多少人能大致读懂汇编代码？好的。差不多是所有人。当你们回答那个问题时，有谁想到的是 ARM64 汇编代码？好的。没有人。太好了。

那么让我们非常快速地看一下 ARM64 汇编代码，因为这是我运行这个程序的机器。别担心，它比 x86 简单得多。我们有一些寄存器，x0 到 x30，它们是 64 位的。我们也可以通过使用 w 而不是 x 来访问它们的 32 位低半部分。

需要提到的重要事情是我们可以进行的内存访问。也就是寻址模式。例如，当我们有一个寄存器存着一个地址，并且我们想读取那个地址的值时，我们把它放在方括号里。这本质上是一个指针解引用。

我们也可以用一个偏移量来解引用指针。例如，我们可以读取 x0 + 42，然后读取那个地址。这是一个以字节为单位的偏移量。

我们可能还想永久地加上 42。所以我们有预增量和后增量。这只是加上偏移量并读取它。它可以在读取之前或之后进行增量，这在你想要读取某些东西并同时增加指针时非常方便。

最后，当你想读取，例如，索引到一个由 8 字节对象组成的数组时，你想将偏移量乘以 8。为此，你可以使用最后的索引操作，你指定一个左移 3 位的操作。这基本上是对一个 64 位整数数组进行数组访问。

有了这些，我们就可以看看我们 switch 语句的汇编代码了。循环从那个标签开始，然后我们读取当前的操作码。我们首先将它与 0 比较。如果是 0，那么我们想去 push。然后我们将它与 1 比较。如果是 1，我们想去 add，以此类推。如果其他都不匹配，我们去 exit。

然后每个 push 指令或其他指令只有几条汇编指令。例如，push，我们读取字节码中的下一个字节，把它存到一个寄存器里，然后把它存回 VStack。之后，我们直接用后增量来增加 VStack 指针。然后我们把指令指针增加 2，然后回到循环的开头。当我们到达 exit 时，我们只需加载最终值并从函数返回。

非常直接的代码。事实上，这太直接了，以至于它并不是编译器实际生成的代码。因为它做的是将操作码与 0 比较，然后与 1 比较，然后与 2 比较，然后与 3 比较，这是一个与操作码数量成线性关系的比较次数。所以编译器可以更聪明一点。它可以进行一种二分搜索。这在汇编代码中会变得有点乱。所以这里是 C 语言的版本。

它首先检查，操作码是否小于 4？如果是，好的，我们处理这种情况。现在它在 0 和 3 之间。然后我们与 1 进行比较。然后我们只剩下两种情况了。所以我们要么去 push 要么去 add。这本质上是对我们想要跳转的标签进行二分搜索，并且有 log(n) 次比较，这更好一些。所以，谢谢编译器。

让我们看看计算到底有多快。我们来测量执行 Fib(35) 所需的时间。结果是 460 毫秒。这快吗？谁认为 460 毫秒对于 Fib(35) 来说是快的？谁认为他们完全没概念，因为我完全没有提供任何上下文？

那么我们到底该如何进行基准测试呢？我们需要进行多次运行，因为存在随机噪声。然后我们可以报告平均值和标准差，以准确量化噪声的水平。然后我们可以将它与别的东西进行比较。孤立的性能数字是毫无意义的。我们需要一个不同的实现。

我发现一个非常方便的基准测试工具是 Hyperfine。这是一个命令行基准测试工具。你给它多个，本质上是 shell 命令。它会多次执行每个 shell 命令，报告范围、平均值，然后告诉你哪个更好。这是一个非常方便的工具，我用它来做所有的基准测试。然而，我实际上不会给你们标准差之类的东西。我只会给你们平均值，因为我希望你们做自己的基准测试，进行自己的定性性能分析。

我们只有一个基准测试。但为了这次演讲，我们就说这太慢了。我们想让它更快。那么我们如何让它更快呢？

如何优化？

第一步是我们需要猜测一个问题，比如到底是什么慢。这可以是一个有根据的猜测，也可以是一个凭空的猜测。让我们做一个猜测，说这里的问题是分支预测。

我这是什么意思呢？CPU 分阶段执行汇编指令。它首先需要获取将要执行的下一条汇编指令的内存。然后它需要弄清楚那到底是什么。然后它可以执行它。然后它可以将结果写回内存。关键是，这是并行完成的。所以在它获取内存的时候，在它执行一条指令的时候，它可以开始获取下一条指令，等等，因为这是由 CPU 的不同部分完成的。所以它可以并行完成。所以我们得到了很好的加速。

然而，只有当 CPU 知道下一条指令是什么时，这才能并行完成。关键是，如果有一个分支指令，它完全不知道下一条是什么。那么 CPU 会做什么呢？它只是猜测。它预测分支是否会被采用，以预测下一条指令是什么。如果它做出了正确的预测，它就有效地利用了流水线。所以我们碰巧预测了实际上将要被执行的指令，通过部分地执行它。所以这是好的。如果它做出了不正确的预测，那就不好了。因为那时它已经部分地执行了它。所以我们需要停止一切，回滚流水线，并开始执行真正的那个。所以我们希望总是猜对。

这是通过基本上记住历史来完成的。对于每个汇编分支，它会记住，比如，好的，大多数时候我们采用了它。所以我们预测说我们再次采用它，并开始推测性地执行它。

然而，我们在循环中做的是，每个循环迭代都执行一个不同的字节码指令。所以它怎么能预测任何东西呢？因为每次你都在做完全不同的事情。分支预测器在这里帮不上我们什么忙。所以，我们假设这就是我们的猜测。分支预测是个问题。

下一步是测量以验证它确实是问题的根本原因。一个测量特别是分支预测失败（branch misses）的方法是使用 Linux 的 Perf Stat。这是一个允许你查询硬件性能计数器的工具。特别是，我们可以查询在执行我们的字节码解释器时，有多少分支被采用，有多少分支被错误预测。

然后我们得到这个结果。总长度是分支的数量，然后黄色的部分是错误预测的分支。我们有这么多的分支预测失败。这算多吗？同样，孤立地看是毫无意义的。我们需要有东西来比较。但为了这次演讲，我们就说这很多。我们想把黄色的部分减少。

最后一步，我们如何实际解决这个问题？一个方法是切换到不同的调度技术。我们将要看的第一个叫做调用线程化分派 (Call Threading)。它叫 threading，但它和线程（threads）没有任何关系。这只是它的叫法。是的，不，就是这样，但它使用了相同的比喻，threads，所以它被称为 threading，但它与多线程无关。

优化技巧一：Call Threading

这个想法是使用一个函数指针数组。我们为每个可能的操作码都写一个单独的函数来执行每个指令。所以我们有一个执行 push 的函数，一个执行 add 的函数，然后我们有一个包含这些函数的大数组。然后在我们的循环中，我们直接跳转到那个函数指针并调用它。

/* 生成代码，仔细甄别 */

// 为每个操作码定义一个函数
void execute_push(uint8_t*& ip, int*& vstack_ptr, ...);
void execute_add(uint8_t*& ip, int*& vstack_ptr, ...);

// 函数指针数组
using handler_t = void(*)(uint8_t*&, int*&, ...);
handler_t execute_table[] = {
    &execute_push,
    &execute_add,
    // ...
};

// 调度循环
while (true) {
    auto opcode = *ip;
    if (opcode == OP_EXIT) break;
    execute_table[opcode](ip, vstack_ptr, ...);
}

有两点要指出。首先，我们在执行查找表时没有做范围检查，如果我们不控制传递给我们的字节码，这是非常糟糕的。所以你不应该这样做。但我们再次忽略这一点。

第二点是，例如，push 会修改 vstack_ptr。所以我们需要通过引用传递 vstack_ptr。同样，我们需要通过引用传递 ip。所以我们只需要确保修改能够生效。

这是循环生成的汇编代码。首先，我们需要为所有这些东西创建引用。所以我们把它们的地址加载到栈上。例如，指令指针存储在栈指针偏移 24 的位置。所以我们把它加载到寄存器 x0。现在我们有了一个指向指令指针的引用。同样，我们为其他参数做设置。

然后是这个 LDR 指令，它获取指令指针，当前的操作码，并用它来索引 execute_table，这个表的基地址在循环前已经被加载到寄存器 x20 了。所以现在 x8 存储了函数的地址。然后下一条指令用我们之前设置的参数调用那个函数。当函数返回时，我们把下一个操作码加载到寄存器，检查我们是否完成。如果没有，我们回去重复这个过程。

关于使用函数指针进行分派的技术有什么问题吗？好的。

让我们来测试一下它。

switch 是黄色的。这个是绿色的。这明显慢了很多。

等等，它并没有明显慢很多，因为对于基准测试，我只是随便找了一个网站来生成条形图。而那个条形图实际上不是从 0 开始的。它从 450 开始。所以那个大尖峰实际上是 75% 的差异。就像很多出版物使用条形图一样，你总是应该注意这一点。

这是实际的图，如果你从 0 开始，你慢了这么多。那么这里出了什么问题？我们实现了不同的分派技术。我们没有所有那些分支了。为什么我们更慢了？

嗯，主要原因在这里的内存访问。让我们比较一下实际的 execute_push 指令的汇编指令。如果 execute_push 是按值传递所有东西，它知道，例如，x0 存储着指令指针。我们可以直接加载它，从中获取负载，并把它加载到一个寄存器里。然后我们可以把它存到 x1 指向的 VStack 指针。我们可以直接操作它。最后增加 x0。

但我们不是按值传递。我们是按引用传递。所以 x0 不包含指令指针。它包含一个对指令指针的引用，换句话说，一个指向指令指针的指针。所以汇编代码首先必须把实际的指令指针加载到寄存器里。然后我们才能进行操作。然后对于 VStack，它同样需要加载 VStack 指针，进行实际的操作，然后再把它存回内存。最后当我们增加它时也类似。所有这些内存访问和开销，它们加起来了。

这些的原因是 CPU 只有当东西在寄存器里时才能工作。当我们有一个引用时，它们不直接在寄存器里，它们在内存里。所以我们首先需要把它们加载到寄存器，修改它们，然后再把它们放回去。这增加了开销。

所以那个方法没用。让我们试试另一个方法。这就是你做优化的方式。你猜测一个问题，你尝试修复它，然后你重复这个过程直到你修复它。

优化技巧二：Token Threading

我们可以做的另一个分派技术是 Token Threading，或者有时叫做 Indirect Threading。这里的想法是利用一个 GNU 扩展：计算型 goto (computed goto)。

你们都熟悉常规的 goto。你有一个语句的标签，然后你可以 goto 那个标签。如果你想写出可读性高的代码，它真的很好用。（笑）

通过计算型 goto，我们有两个扩展。首先，我们可以使用这个奇怪的双 & 操作符来获取一个标签的地址。这给了我们一个标签的地址。然后我们可以 goto 那个存储的地址。是的，我们在 goto 前面解引用了一个 void 指针，但这没问题。

void* push_label = &&push_handler;
// ...
goto *push_label;
// ...
push_handler:
  // ...

现在的想法是，我们不再有一个函数指针数组，而是有一个标签地址的数组。我们为每个我们想做的指令处理器都有一个标签，它包含代码。然后我们为此创建一个表。我们不调用函数，而是直接 goto 那个标签。在我们执行了一个特定的字节码处理器之后，我们继续，回到循环，然后开始执行下一个。

如果我们看生成的汇编代码，它看起来非常相似。在循环的开始，我们加载当前的操作码。然后我们索引到一个表。然后我们跳转到那里。然后在每个指令的末尾，我们将指令指针增加适当的数量，然后回到循环的开头。

这实际上，又一次，不是编译器生成的汇编代码，因为它看到那个然后想，好的，在 push 之后，我们做了一个 add。然后我们跳回循环。然后我们做一些事情，然后我们立刻跳到别的地方。这有点傻。让我为你修复一下，直接从一开始就跳到正确的地方。所以它在每个指令之后都复制了开头的分派代码。所以在 push 之后，它会直接跳到下一个指令，而不是回到循环。

编译器能做的另一个优势是，之前，我们有 add，然后我们有一个分支，然后我们加载 x0。通过这种方式，编译器能够将这两个操作合并成一个。这个加载操作已经用增量操作为我们做好了 add。所以我们同时做了 add 和加载，然后直接跳到下一个位置。

因为编译器总是会生成那样的代码，无论我做什么，我都无法阻止它生成这种代码。这也是在 C 代码中编写 token-threaded 分派的标准方式。所以你为每个指令都有标签，然后在每个指令之后都有 goto *execute_table[...]，并且只需要一个来启动整个过程。

/* 生成代码，仔细甄别 */

// ... C/C++ with GNU extension
dispatch:
    goto *execute_table[*ip];

push_handler:
    // push logic
    ip += 2;
    goto dispatch;

add_handler:
    // add logic
    ip += 1;
    goto dispatch;

现在你看不到循环了。取而代之的是，每个指令跳到下一个，跳到下一个，跳到下一个，直到我们到达 exit，那时我们返回。这就是为什么 goto 会导致一些复杂的控制流，因为这是一个循环，但你永远看不到循环。你只是在整个函数中到处直接跳转，这使得弄清楚指令在这里实际执行的顺序非常棘手。

有问题吗？是的？

观众：这能在标准 C++ 中实现吗，不用扩展？
讲者：不完全可以。好的。

好的。让我们来测试一下那个技术。看看这个。我们实际上让我们的目标更快了。我们现在几乎比 switch 快两倍，并且明显比函数指针快。这是因为我们现在有了使用表的高效分派，但我们没有任何与按引用调用相关的开销。所以这很好。

然而，我们开始时说，好的，让我们假设问题是分支预测。而所有这些跳转，它们仍然是分支。它们字面上就是我们到处在做的分支指令。所以让我们看看分支。

上面是 switch，下面是我们刚做的。我们的分支明显少了很多，这很合理，因为我们每个指令只有一个分支，而不是二分搜索。但我们绝对的分支预测失败也更少了，所以 CPU 能够更好地预测它们。

为什么会这样？嗯，在 switch 之后，我们有一个单一的分派代码。我们有一个分派代码来选择下一个字节码指令，这意味着只有一个分支指令，CPU 可以在那里进行分支预测。但它学不到很多东西。所以它唯一能学到的是哪个指令最有可能被执行。而每个指令被执行的概率大致相等，所以那对我们没有帮助。

然而，我们现在在每个字节码指令之后都有独立的分派。CPU 可以分别学习所有这些。这非常好，因为它本质上学到的是，好的，在 push 之后，我们很可能有一个 sub 指令。所以它可以预测在 push 之后，我们将要去 sub。然后在 sub 之后，它知道，好的，我们要调用 fib，所以我们有 recurse 指令。所以它可以分别预测接下来最可能发生的事情，并因此获得更好的分支预测。

优化技巧三：Tail Calls

我们已经让它快了两倍，但我们假设这仍然太慢了。我们如何让它更快？为此，我们需要更多的信息。一种方法是使用 Perf Record。它会执行程序并频繁地停止 CPU，看看当前的函数是什么。所以当我们… 它基本上记录了最常见的函数。

如果你看结果，我们花了 99.85% 的运行时间在 dispatch 函数里，这是对的。但这也没用。就像，我们当然在做这个。我们正在做分派。我们没有别的函数了。所以理想情况下，我们希望有独立的函数。如果我们使用函数指针，我们就会有独立的函数，并得到更详细的分解。但我们不想要带独立函数的内存开销。

所以我们能把这两种技术结合起来，取其精华吗？这是可能的，通过尾调用 (tail calls)。

这里的想法是什么？让我们回到写函数的方式。我们有独立的函数。但我们不按引用调用，为了性能，我们按值调用。现在，当然，当我们修改指令指针时，这对我们的调用者没有影响，因为我们有一个独立的副本。所以我们不回到调用者。取而代之的是，我们直接进入下一个指令，类似于计算型 goto 发生的情况。所以现在我们可以修改指令指针，然后用新值调用另一个函数。同样，我们仍然有一个函数指针表，所以有点像是两种技术的混合。

/* 生成代码，仔细甄别 */

// 仍然是独立的函数，但按值传递
return_type execute_push(uint8_t* ip, int* vstack_ptr, ...) {
    // push logic
    ip += 2;
    // ...
    // 用尾调用跳转到下一个指令
    return execute_table[*ip](ip, vstack_ptr, ...);
}

有一点需要指出的是，让我们看看调用栈。每次我们进行调用时，我们基本上需要把程序计数器推入调用栈，类似于我们的 recurs 指令，这样我们才知道返回到哪里。然后 return 只是弹出那个程序计数器并跳回到那个位置。

所以我们从 dispatch 开始，它把程序计数器推入 CPU 栈。然后我们跳到第一个 execute，推入程序计数器，跳到下一个，推入程序计数器，等等，直到我们最终到达 exit 指令，那时我们弹出程序计数器并回到我们的调用者，弹出程序计数器，回到调用者，等等，直到我们最终回到 dispatch。

当然，这并不是实际会发生的事情。实际会发生的是我们开始 dispatch，调用那个，调用那个，调用下一个，直到我们发生栈溢出。因为我们每次执行一条指令就一直调用新函数，而我们将要执行数百万条指令。

然而，幸运的是，我们不需要那样。我们需要保存程序计数器以便能够返回到我们的调用者。但然后我们的调用者只是回到它的调用者，因为我们有 return，就像我们用函数调用返回一样。所以当我们返回时，下一步是回到我们的调用者。所以为什么不直接回到“祖父”调用者，而不是经过中间环节呢？

这就是尾调用的想法。我们从 dispatch 开始。这是一个真正的调用，它会推入一个程序计数器。然后我们只是跳转到第一个 duplicate。然后我们跳转到下一个。所以我们不继续往调用栈上加东西。最后，当我们使用 exit 指令时，我们只有一个 return。那个单一的 return 只是回到调用栈顶部的程序计数器，也就是来自 dispatch 的那个。所以我们不需要在返回路上的所有中间步骤，那些是多余的，我们可以直接跳回 dispatch 代码，这更方便，也避免了栈溢出。

这也是编译器可以做的一个常见优化，如果你有那种形式的 return 语句。然而，我们实际上要求这个优化。没有它，我们就会有栈溢出。所以我们需要一种方法来友好地请求编译器，请总是生成一个尾调用，即使在调试代码中也是如此。

Clang 有一种方法可以做到这一点。Clang 提供了一个属性，[[clang::musttail]]。你可以用它来注解一个 return 语句，以强制编译器生成一个尾调用。这甚至在没有优化的调试模式下也会发生。编译器将总是生成一个尾调用。我真的很喜欢这个属性。不幸的是，它只在 Clang 中可用。它在 GCC 中不可用。它在 MSVC 中也不可用。它只在 Clang 中可用。

所以我们不在每个指令的末尾进行普通调用，而是进行尾调用。这将确保我们只是跳到下一个指令，就像计算型 goto 一样，但没有任何调用栈的开销。事实上，如果你看汇编代码，我们有 dispatch 代码，它加载查找表，然后跳到第一个条目。然后在 push 的末尾，我们再次加载表。然后我们跳到下一个。这和我们用计算型 goto 得到的汇编代码完全一样。唯一的区别是现在表是全局的，所以它首先需要从全局内存加载它们。但除此之外，它是完全相同的分派和代码。

观众：对不起。澄清一下上一张幻灯片，为什么你不能要求 GCC 开启尾调用优化？
讲者：你不能要求 GCC 开启尾调用优化，首先，因为 GCC 不提供一个属性。那只是一个 Clang 属性。而 GCC 不提供这个属性是因为 GCC 支持一些不能做尾调用的晦涩硬件。
观众：这是 LLVM 的东西吗？
讲者：是的，这是 LLVM 的东西。你请求编译器生成一个尾调用，如果它做不到，你的代码就不会编译。所以这是一个保证。如果它编译了，它就是一个尾调用。我猜 GCC，他们不能支持那个。有一些限制，比如你尾调用的函数必须有完全相同的签名。函数中不能有析构函数等等。但如果不满足条件，它就不会编译。

还有其他问题吗？是的？

观众：你试过在 GCC 中用 longjmp 之类的东西来模拟这个行为吗？
讲者：我没有试过在 GCC 上用 longjmp 模拟这个行为。我主要是为一个业余项目实现了这个，我只用 Clang 就行了。所以我没有尝试去解决其他编译器缺少功能的问题。

让我们看看当我们测试那个技术时会发生什么。我们在底部有一条橙色的线，我们大致相似，性能和计算型 goto 一样。我们甚至因为某些原因更快了，但我不知道。比如，我们为什么会更快？我们基本上在做同样的事情。出乎意料，又不意外的是，分支预测失败和分支预测错误预测的数量也类似。所以我们基本上只是用尾调用实现了计算型 goto，这让我回到那个问题。是的，你可以在没有计算型 goto 的情况下做到，但你需要另一个编译器扩展。所以我不知道那是否真的实用。

然而，一个很大的好处是，因为我们现在实际上有一个单独的函数，如果我们让 Perf 做分析，我们实际上得到了不同指令处理器的分解。所以我们可以看到 16% 的时间，我们实际上花在了 push 上。所以现在我们知道了，好的，我们可能想优化 push。例如，我们经常 push 1。所以让我们加一个单独的指令只用来 push 1，这可以优化那个并可能让程序更快，这非常有用。

深入探讨：寄存器分配

让我们谈谈 register 关键字。register 关键字在 C 语言中可用。你可以请求 C 编译器请把这个变量放在一个寄存器里。正如我们所见，CPU 只能在值在寄存器里时处理变量。所以我们可以请求 C 编译器为我们做这个。然而，现代编译器会为你做这个。所以我们实际上不需要告诉编译器请把指令指针放在一个寄存器里。用 register 关键字，现代编译器会为你做这个，这就是为什么 register 在 C++ 中没有任何意义。

然而，现代编译器并不总是为你这样做。这是 Mike Pall 的一句话。Mike Pall 是 LuaJIT 的作者。除了是一个 Lua 的即时编译器，LuaJIT 也有一个字节码解释器。这个字节码解释器是用汇编写的。在这封邮件中，他解释了为什么他用汇编写它。

… 寄存器分配器只能分别处理这些代码段，并且会做得非常糟糕。根本没有办法给它一个目标函数，比如“我希望在每个 goto 之前保持相同的寄存器分配”。

所以我们不希望在执行时，一直把东西在寄存器之间 shuffling。我们希望为常用变量保持相同的寄存器分配。例如，我们想确保指令指针总是在 x0 中，而不是有时在 x1 中，然后传来传去。用计算型 goto，没有办法强制做到这一点。

然而，我们没有用计算型 goto。我们用的是函数调用。而对于函数调用，有调用约定 (calling convention)。在汇编层面，一个函数调用只是一个到地址的跳转。那么参数在哪里传递？它们在寄存器里传递。在 ARM64 上，我们有 8 个参数可以在前 8 个寄存器里传递。所以当我们调用一个函数时，我们把第一个参数放在 x0，下一个放在 x1，等等，然后我们跳到那个地址。

所以当我们想要某个东西在一个寄存器里时，我们把它作为一个参数传递。指令指针是第一个参数，所以它在调用函数时会在 x0 中。当然，然后编译器可以做任何它想做的事，把它移来移去，存到内存里，做任何事。但在最后，它调用下一个函数，那个函数期望指令指针作为第一个参数，所以它必须把它放回 x0。这意味着在实践中，指令指针将总是被保留在 x0 中，因为为什么要把它移来移去呢？

正如我们所见，在代码中，x0 总是指令指针，x1 是 VStack 指针，x2 是 CStack 指针，x3 是字节码。通过这种方式，我们可以利用调用约定强制编译器得到一个特定的寄存器分配。

标准的 ARM64 调用约定给了我们 8 个寄存器。所以我们可以用 8 个参数把 8 个东西保留在寄存器里。在 x64 Linux 上，我们只有 6 个寄存器，这比较少。在 Windows 上，只有一半，4 个，这有点不幸。所以在 Windows 上，我们只能把 4 个东西保留在寄存器里。

然而，我们不需要用标准的调用约定。我们是唯一调用那个函数的人。没有别人。所以你可以请求编译器生成一个不同的调用约定，一个给我们更多寄存器的。其中一个是 __attribute__((regcall)) (GNU)。通过 regcall，有一个调用约定会尽可能多地在寄存器里传递。这样，在 Linux 上，我们得到 12 个寄存器。在 Windows 上，我们得到 11 个。在 ARM 上，它什么也不做，因为我们已经有 8 个了。所以我们现在可以注解，如果你需要超过 4 个参数，给超过 4 个东西在寄存器里。我们可以用 regcall 来注解它。

观众：Clang 也支持吗？
讲者：是的，Clang 支持。
观众：MSVC?
讲者：可能用不同的… 我不知道。我不常用它。MSVC 不支持尾调用。所以……
观众：这有红线吗？比如，有性能影响吗？
讲者：是的，性能影响是在一个函数内部，你的临时寄存器变少了。所以如果你需要临时寄存器，你会有更好的选择。但如果你的工作对象只是那些参数值，那就没问题。
观众：这就是为什么它不是默认开启的。
讲者：是的，它不是默认开启的，因为通常，一个函数会用临时值做实际的事情。但在这里，所有的函数都只有三条指令。

观众：register 关键字被弃用的一个原因是，如果你试图锁定你所有的寄存器，优化器就没有任何办法了。
讲者：是的。
观众：所以它真的，真的会扼杀性能。
讲者：它真的会扼杀性能。
观众：除了你的例子，最好甚至不要尝试这样做。
讲者：是的。
观众：因为即使你必须从内存重新加载它，也比没有可用寄存器要快。
讲者：是的。所以总的来说，通常编译器比你更知道该把什么保留在寄存器里。但这是一个非常特殊的情况，我们想知道得更清楚，并且精确地生成我们想要做的汇编。所以我们可以用这种技巧来可靠地强制编译器不做蠢事。

深入探讨：iCache 和慢路径

Mike Pall 的邮件继续列出了用汇编写解释器循环的优点。

你可以为所有字节码指令保持固定的寄存器分配。 嘿，我们也可以做到。用参数，我们可以保持固定的寄存器分配。 你可以在快速路径上把所有东西都保留在寄存器里，只在慢速路径上溢出和重载。 你可以把慢速路径移到别处，以帮助提高 iCache 密度。

这是什么意思？什么是 iCache？CPU 执行的汇编指令存储在内存的某个地方。而内存访问是慢的。所以 CPU 有缓存。它有一个专门为当前指令准备的缓存，即 iCache (指令缓存)。然后这个缓存会被预先填充指令。但这意味着你不想用你不会执行的指令来污染它。所以如果你有很少执行的东西，你不想把它放在 iCache 里。你想把实际执行的东西保留在 iCache 里，因为它只有一个固定的大小。

让我们看一个例子。让我们加一个愚蠢的指令，print_42。如果顶部的值是 42，它就打印 42。否则，它什么也不做。而里面的那个 print 语句，这是一个慢路径。它会执行额外的工作，做一个系统调用。这是慢的。

让我们改变一下基准测试。同样是 Fib(35) 的实现。但在每个字节码的开头都做一个 print_42。这不会做任何事，因为 n 总是小于 42。所以这不会改变行为。我们只是在开头加了额外的指令。当我们这样做时，我们明显变慢了。我说的明显，是指 4 毫秒，因为那个条形图不是从 0 开始的。抱歉，要注意这个。

这里的一个因素可能是 iCache。我们可能有 puts 的代码被加载进去了。但因为它只是一个函数调用，这可能不是真正的问题。更重要的问题，当你看到汇编时就非常明显了。

这是 print_42 的全部汇编。这些都在做什么？在中间和左下角，我们有与 42 的比较。然后我们有分支。如果分支不被采用，我们调用 puts。好的，这正是我们想做的。然后在最末尾，我们加载我们的调用表，并在增加 IP 后转到下一个指令。

那么所有其他的围绕它的东西是什么？那个 puts 调用是一个函数调用。所以它调用另一个函数。为此，它需要把参数设置在适当的寄存器里。所以 x0 需要是字符串 “42”。所以它在之前这样做。但这意味着我们当前的指令指针需要被保存在别处。所以我们把 x0 存到别处，比如 move x22, x0。这会把 x0 存到 x22。然而，x22 是一个 puts 本身可能使用的寄存器。所以它首先需要把 x22 的现有值存到调用栈上。

所以编译器做的是，它必须做一大堆寄存器 shuffling，只是为了确保对 puts 的调用不会污染我们的寄存器。所以它必须做内存访问，移动寄存器，然后才能调用 puts。然后在最后，它必须撤销所有这些。这有点傻，因为我们不是总调用 puts。我们只在有 42 的时候才调用 puts。所以如果编译器只在我们调用 puts 之前做所有这些 shuffle，而不是每次调用这个函数时都做，那就好多了。

同样，有一种方法可以调整编译器来做到这一点。我们不直接调用 puts，而是用一个函数来做。如果子值是 42，我们就调用另一个函数。另一个函数打印 42 然后继续执行。所以我们有点复制了这里的代码。现在 execute_print_42 没有任何函数调用。它只有一个到另一个函数的尾调用。所以 print_42 的汇编，它看起来就像我们期望的那样。我们与 42 比较。如果是，我们只是跳转到一个到 print_input 的尾调用。否则，我们继续。

然后 print_input 的汇编调用，这个有所有的寄存器 shuffling。这个做所有的设置。这个做所有的内存访问。这个做所有慢的事情。通过这种方式，我们完全消除了实际 print_42 函数中的开销，并且我们又得到了相同的性能。

是的，原则上，没有什么能阻止编译器在分支内部做这个。但我猜只是编译器知道，好的，当我们调用一个函数时，我们需要保存寄存器。而它不看那个函数调用会发生得多频繁。所以它总是在开头做这个，在末尾恢复它。通过使用尾调用，我们没有任何函数调用。我们把它们移到别处，我们就得到了快速的代码。

现在，重要的是，因为我们是尾调用，我们实际上不能 return。在我们打印了 42 之后，我们尾调用到了别处。考虑这个例子。比如说我们想防止栈溢出。所以当我们到达调用栈的末尾时，我们想分配更多的内存。这是慢的，所以我们把它移到一个单独的函数里。在我们分配了内存之后，我们想返回到调用者。但我们没有那个信息，就像我们在尾调用中一样。我们已经失去了所有我们从哪里来的信息。这就是尾调用的全部意义。

所以取而代之的是，我们必须做一个尾调用回到我们来自的最后一个指令的开头，再做一次 if，这次条件不再为真，然后继续。你不能只写一个 return，因为 return 会一直回到 dispatch 循环，因为那才是真正的父函数。否则，我们只是在到处跳转。所以你必须记住这一点。

关于这个有什么问题吗？

结论……等等，还有反转！

好的。[[clang::musttail]]，我真的很喜欢它。它通过函数调用实现了线程化分派。这算是我这次演讲想要的结论。所以你可以用 [[clang::musttail]]。你可以用 perf record 得到详细的性能记录。你可以强制编译器使用一个特定的寄存器分配，这真的很酷。但你必须记住，在尾调用函数内部不能有任何函数调用。否则，性能就会一落千丈。所以把它们移到别处。并且记住你实际上不能 return。用 [[clang::musttail]]，你可以调整编译器来生成你想要的确切汇编。

这是一个不错的演讲。我想我可以展示它。我可以演示它。这有点像我用那种方式实现了我的解释器。我想分享那个技术，所以我提交了这次演讲。所以我写了我所有的幻灯片。然后我对自己说，为了保险起见，让我们也在我的旧笔记本上测试一下，而不只是在 Apple M1 上。

新的基准测试。 我的旧笔记本，一台 2016 年的 ThinkPad 13，运行 Arch Linux 和 Clang 14。这些是我们的四种技术的结果。正如预期的那样，switch 是目前最快的。

什么？

观众：它在做二分搜索吗？它在做……
讲者：是的。我告诉过你们。

让我们看看分支预测失败。我们突然有了大量的分支预测失败，在使用线程化分派和尾调用时。这几乎是所有分支的四分之一都被错误预测了。好的，但为什么？

嗯，答案是分支目标预测 (branch target prediction)。对于 switch，我们有一个条件分支，但目标是固定的。所以我们想做一个比较。如果它相等，我们想去某个地方。我们总是知道固定的目标。比如我们总是想去 push 标签。但我们不知道我们是否会跳到那里。

而对于尾调用等等，我们有一个查找表。所以我们加载我们想去的地方的地址，那是一个变量。然后我们总是跳转。我们有一个无条件分支，但我们不知道我们要去哪里。另一方面，我们有一个条件。我们知道我们要去哪里，但我们不知道我们是否会实际采用那个分支。

分支目标预测的工作是确定一个分支要去哪里。之前，我讨论了分支预测器，它决定一个分支是否被采用。但一个无条件分支总是被采用。然后我们只需要弄清楚我们要去哪里。显然，我的旧笔记本只有一个非常糟糕的分支预测器，分支目标预测器。

观众：只是一个小问题。但旧笔记本是 x64 的，对吧？不是 ARM 这种。
讲者：是的，是的。是的，旧笔记本是 x64 的，但我仍然只展示 ARM，因为它更…

那么我们该怎么办？我们 irgendwie 需要绕过我的旧笔记本必须做的分支目标预测，以获得任何性能。我们仍然可以用尾调用，因为我喜欢尾调用。它们给你函数调用。你得到分派来得到寄存器分配。我们只是不能用查找表。

所以我们不在每个指令的末尾进行尾调用，而是可以写一个 switch。所以现在我们在每个指令之后写一个 switch，然后我们尾调用到一个固定的地址。这样，我们仍然有固定的地址。比如在这种情况下，我们总是要去 push。但我们不知道我们是否会实际去那里。通过这种方式，我仍然得到了好的分支预测，并且不需要做任何分支目标预测。我仍然得到一个复制的 switch，因为我们在每个操作码之后都做它。所以我得到了所有的优势。

正如预期的那样，我又得到了好的，更少的分支。所以使用 switch 和尾调用，我们得到了与 switch 类似的性能，同时拥有使用尾调用的所有优势，寄存器分配，等等，以及 perf 记录。

观众：为什么 Clang 不做尾调用优化？
讲者：Clang 在你开启优化时默认做尾调用优化。
观众：啊，好的。所以你没有优化……
讲者：是的。是的，但如果你不做尾调用，我们会有栈溢出。所以如果你不能调试，那么现在在这里写代码，所以你想要那个属性在里面。

所以也许这次演讲的真正结论是，就让编译器去做分派，它最清楚。 简单的 switch 是最快的选项。

除了那并不是编译器为 switch 生成的代码。它只为 switch 生成那种代码，因为我友好地请求编译器请为 switch 生成这种代码，因为我想演示不同的分派技术。

如果我不给编译器传递任何特殊的编译器标志，实际生成的汇编看起来是这样的。你们已经看了足够多的汇编，知道这是什么了。这是一个跳转表 (jump table)。所以默认情况下，编译器为 switch 生成一个跳转表，这给了我与其他跳转表实现完全相同的性能，这在我的旧笔记本上就是非常糟糕。

所以现在，我们不能只相信编译器会做最好的事，因为编译器实际上也不知道什么是最好的。我们有 switch。我们必须传递那个标志才能在我的旧笔记本上得到好的性能。

又一个反转：新笔记本和编译器的智慧

自从我第一次做这个演讲以来，我有了一台新笔记本。我的新笔记本是一台 ThinkPad X1 Carbon，用的是 Intel Core i5。这是它上面的基准测试结果。我只是为了完整性而运行了它们。这次，如预期的那样，计算型 goto 或尾调用是使用查找表的最快实现。两个 switch 版本，它们仍然使用二分搜索。所以它们实际上没有为那个生成查找表。

所以几周前我想，为了完整起见，让我们禁用那个编译器标志，并实际测试一下编译器如果我只说“请优化这段代码并做任何你想做的事”时会生成的原生汇编代码。结果是比计算型 goto 更快。

那么这里发生了什么？嗯，现在我真的必须展示 x86 汇编了，因为这是一台 x86 机器。这是我们在 x86 中实现的跳转表。它基本上是同样的事情。我们首先加载操作码。然后我们去查找表中的那个位置。只是寄存器名字有点奇怪。并且我们把跳转和地址操作结合起来了。这就是我们手动得到的。

这是编译器生成的跳转表。好的，我们加载操作码。然后我们从表中得到地址。然后我们有一个 add 在里面。然后我们跳转。好的，所以我们在跳转前给寄存器加了点东西，恰好是表本身的地址。这有点奇怪。所以这一定意味着跳转表里的地址，它们实际上是相对于跳转表的基地址存储的。所以它们不是绝对偏移量，而是相对的。

但这为什么更好？我们多了一个 add 在里面。为什么那更快？嗯，它更快是因为如果你看做内存访问的指令，execute_table，如果是手动的，它是 8 字节。但如果是 switch，它只有 4 字节。编译器生成的跳转表，用的是 4 字节的相对偏移量，而不是 8 字节的绝对偏移量。因为它们更小或者别的什么原因，这在我的笔记本上恰好更快。

所以我真的不知道这次演讲的结论会是什么。

我们在我的旧笔记本上不能相信编译器，但在我的新笔记本上可以。而尾调用技术仍然非常好。所以也许就是在做任何优化之前，先在目标硬件上进行基准测试，因为你永远不知道你会得到什么。

我想指出，即使我们有尾调用，就像 switch 不用尾调用一样，我们仍然可以用尾调用来使用那个技术。我们可以手动实现一个相对偏移量表，只需要在函数指针之间做一些 reinterpret_cast，存储相对地址，让它们更小，等等。所以我们可以手动实现编译器做的那种技术，并且仍然得到好的性能。所以尾调用本身作为一种分派技术，它们与编译器做的任何其他事情都是兼容的，正如我所演示的。

更多高级分派技术

因为我们还剩下很多时间，我想讲一些更高级的分派技术。我们已经看了计算型 goto 和尾调用。它们基本上做同样的事情。我们只是在一个中有尾调用，一个中有 goto。所以查找表首先包含标签，而这里它包含地址。然后我们用操作码来索引一个数组。

如果我们不做那个间接寻址，而是说操作码本身就是处理器的地址呢？这就是直接线程化分派 (Direct Threading)。它可以用两种方式实现。在第一种中，我们有字节码操作码。就像，我们有一堆地址，然后我们直接 goto 那个地址。它们不能是 const，因为你不能用一个函数内部的标签地址来初始化一个全局变量。所以 dispatch 做的第一件事是初始化所有这些常量。然后它们就不再被修改了，这有点烦人。

用尾调用就好多了。它们是 push。我们不用 enum，而是用一个函数。然后指令指针直接存储函数指针，所以我们可以直接跳转它们。这相当不错。如果你看生成的汇编，我们 execute_push，做所有的逻辑，然后我们增加 x4，这次是 16，因为我们有两个 8 字节。然后我们直接跳到那里，这非常好。这是目前为止最好的分派代码，因为我们只有一个跳转。

缺点是现在操作码不再是一个 8 位的 enum，而是一个 64 位的地址。这意味着在这台笔记本上可能会更慢，因为我们之前在有 32 位相对地址时有性能提升。它仍然需要分支目标预测，所以它在我的旧笔记本上会非常慢。而且它让远程代码执行变得完全微不足道，因为你可以在字节码里写任意地址，人们就开心地跳到那里，然后从那里继续。所以从安全角度来看，这也非常好。

所以这是直接线程化。但比如说我们有这样的代码。我们 push 1，然后 push 2，然后我们想 add。我们何不直接生成那样的汇编代码呢？所以我们得到 push 1 的汇编代码，我们得到 push 2 的汇编代码，然后我们得到 add 的汇编代码。我们只有所有这些汇编代码块，然后我们复制粘贴它们，然后我们想怎么样就怎么样。这非常好，因为最快的分派是没有分派。所以我们只有汇编代码，直接把它们加起来。但这需要 JIT 编译。你必须做一种 JIT-lite。我们不是真的生成高效的汇编代码。我们仍然只是生成我们为常规字节码解释器生成的同样的汇编代码。我们只是把它们连接起来，没有任何分派代码。

至此，我到达了这次演讲的真正结论，再次是，在进行任何优化之前，先在目标硬件上进行基准测试。现在我很高兴听取任何更多的问题或评论，我们可以讨论高级技术。谢谢。

问答环节

观众：在你把所有东西都作为参数传递的例子中，你是否也把分派表作为参数传递了？
讲者：是的，我也可以考虑把分派表作为参数传递。所以我们看到它首先必须从全局内存加载它，我们可以消除那个并因此获得性能提升。但是那么多的参数可能放不下。

观众：你会如何在泛型编程、模板包等情况下使用这些技术来做跳转目标？比如，如果你想为 variant 实现 visitor 操作，你会有一些东西根据整数的操作码告诉你 variant 中是哪个替代选项，等等。
讲者：是的。首先，我不确定这个技术是否真的最适合那个场景，因为它适用于你有循环之类的东西，而不是一个单一的 switch。然后当你在传递 lambda 并想分派到 lambda 时，这不太可能。那些高级的，它们需要修改你要去的函数，这在 C++ 泛型代码中不太可能。所以在那里我会直接写 switch，也许请求编译器生成一个跳转表，或者不生成跳转表，取决于你实际运行的电脑，然后希望它做最好的事，它在我测试的三台电脑中的一台上做到了。

观众：我看到编译器总是会生成一个跳转表，如果你做一些事情，比如，保留函数调用参数的顺序。你甚至可以有不同数量的函数调用参数。但在完全相同的顺序下，所需的子集…… 在 GCC 和 Clang 之间，关于它们何时会生成跳转表曾经有很大的差异。我想你只用 Clang 做了你的实验。
讲者：是的。
观众：是这样吗？
讲者：是的，我只做了我的实验……
观众：因为 GCC 的行为有很大的不同。我认为 Jody Hagins 去年在 CppCon 上对如何在泛型编程的背景下做分派做了广泛的评论。
讲者：是的。是的，我不熟悉那个演讲。但是的，在做任何优化之前先做基准测试，因为也许编译器已经做了正确的事情。

观众：只是一个说明，switch 表的阈值在 GCC 中是完全可配置的，用 -f-param=switch-table-threshold=<size>，你设置你想要从二分搜索转到表的大小。你可以玩那个。
讲者：是的。就像我用了一个类似的标志只是请求不生成跳转表，因为我想要一个不同于跳转表的分派技术。

观众：我认为在 Clang 中，对于数字常量的 if-then-else 会被翻译成 switch 语句或跳转表。
讲者：是的，是的，完全正确。
观众：但 GCC，据我所知，我从来没学会如何控制 GCC 把一个 if-then-else，if-then-else，像一个级联的 if-then-else 转换成一个跳转表。但谢谢你，Joe。我下次会试试你说的那个参数。

讲者：是的，在 LLVM 中也有，几年前有一个演讲，讨论了 LLVM 在 switch 上做的优化。比如 if-then-else、二分搜索、跳转表，还有一些可以用位掩码做的调整。它相当聪明。当你给它一个 switch 时，它通常会找出最快的方式。所以我可能会把那个加到另一个…… 所以所有的幻灯片都在那里。还有，这个很好。如果我记得的话，我可能会在那里加上那个演讲的链接。好的。还有别的事吗？

观众：你当时想实现的 VM 是什么？
讲者：我实现的 VM，我写了一个字节码解释器，它被设计成有很慢的启动时间，所以它可以用来在编译器中做常量表达式求值。所以那是我实现的目标项目，这也是我为什么没有实现一个 JIT 编译器的原因。就是这样。

好的。非常感谢大家来听我的演讲。

谢谢。