计算goto实现高效调度表 (2012)

# 使用计算 goto 实现高效调度表 来源：https://eli.thegreenplace.net/2012/07/12/computed-goto-for-efficient-dispatch-tables 最近，我在闲逛 Python 源码时，偶然在字节码虚拟机实现（`Python/ceval.c`）中看到了一个有趣的评论，提到使用了 GCC 的[计算 goto](http://gcc.gnu.org/onlinedocs/gcc/Labels-as-Values.html) 扩展[[1]](https://eli.thegreenplace.net/2012/07/12/computed-goto-for-efficient-dispatch-tables#id4)。出于好奇，我决定编写一个简单示例，评估在一个简单的 VM 中使用计算 goto 和传统 `switch` 语句之间的性能差异。本文就是我的发现总结。 ### 定义一个简单的字节码 VM 首先明确一下，我所说的“VM”指的就是[字节码解释器](http://en.wikipedia.org/wiki/Interpreter_(computing))。简单来说，它是一个循环，依次执行指令序列。用 Python 长达两千多行（还不包括众多辅助宏）的 `PyEval_EvalFrameEx` 作为例子并不太有教学意义。因此，我定义了一个极小的 VM，其唯一状态是一个整数，并有几个操作该整数的指令。虽然简单，但这个 VM 的整体结构与真实世界的 VM 非常相似。 这个 VM 实在是太基础了，最好的解释方式就是直接给出实现代码： ```c #define OP_HALT 0x0 #define OP_INC 0x1 #define OP_DEC 0x2 #define OP_MUL2 0x3 #define OP_DIV2 0x4 #define OP_ADD7 0x5 #define OP_NEG 0x6 int interp_switch(unsigned char* code, int initval) { int pc = 0; int val = initval; while (1) { switch (code[pc++]) { case OP_HALT: return val; case OP_INC: val++; break; case OP_DEC: val--; break; case OP_MUL2: val *= 2; break; case OP_DIV2: val /= 2; break; case OP_ADD7: val += 7; break; case OP_NEG: val = -val; break; default: return val; } } } ``` 注意，这是完全“标准”的 C 代码。一个无限循环遍历指令流，`switch` 语句根据指令操作码选择执行的操作。在这个例子中，控制流始终是线性的（`pc` 每次只递增 1），但可以轻松扩展为包含更复杂的流控制指令，以非平凡的方式修改 `pc`。 C 编译器应该能非常高效地实现 `switch` 语句——条件值用作查找表的索引，从而确定跳转到哪里。不过，事实证明，有一个流行的 GCC 扩展可以让编译器生成更快的代码。 ### 计算 goto 我会非常简要地介绍计算 goto 的细节。更多信息请参考 [GCC 文档](http://gcc.gnu.org/onlinedocs/gcc/Labels-as-Values.html)或 Google。计算 goto 基本上是两个 C 新特性的组合。第一个是将标签的地址保存为 `void*`： ```c void* labeladdr = &&somelabel; somelabel: // code ``` 第二个是在 `goto` 中使用变量表达式而不是编译时已知的标签，即： ```c void* table[]; // 地址数组 goto *table[pc]; ``` 正如我们马上就会看到的，这两个特性结合起来，可以为主 VM 循环提供一种有趣的替代实现方式。对于有一点汇编语言编程经验的人来说，计算 goto 立刻就有意义，因为它只是暴露了大多数现代 CPU 架构都有的常见指令——通过寄存器跳转（也称为间接跳转）。 ### 使用计算 goto 实现的简单 VM 下面是同一个 VM，这次使用计算 goto 实现[[2]](https://eli.thegreenplace.net/2012/07/12/computed-goto-for-efficient-dispatch-tables#id5)： ```c int interp_cgoto(unsigned char* code, int initval) { /* dispatch_table 中的标签索引即为对应的操作码 */ static void* dispatch_table[] = { &&do_halt, &&do_inc, &&do_dec, &&do_mul2, &&do_div2, &&do_add7, &&do_neg}; #define DISPATCH() goto *dispatch_table[code[pc++]] int pc = 0; int val = initval; DISPATCH(); while (1) { do_halt: return val; do_inc: val++; DISPATCH(); do_dec: val--; DISPATCH(); do_mul2: val *= 2; DISPATCH(); do_div2: val /= 2; DISPATCH(); do_add7: val += 7; DISPATCH(); do_neg: val = -val; DISPATCH(); } } ``` ### 基准测试 我用随机操作码进行了一些简单的[基准测试](https://github.com/eliben/code-for-blog/tree/main/2012/computed-goto-dispatch-tables)，结果 `goto` 版本比 `switch` 版本快 25%。这当然依赖于数据，因此实际程序的结果可能有所不同。CPython 实现内部的注释提到，使用计算 goto 使 Python VM 快了 15-20%，这也与我在网上看到的其他数据一致。 ### 为什么更快？ 在本文后面，你将看到两个“附加”章节，其中包含了上述两个函数在 GCC 的 `-O3` 优化级别下编译的注释版反汇编。这是为读者中的底层爱好者准备的，也作为我自己未来的参考。这里我打算在更高层次上解释为什么计算 goto 代码更快，如果你觉得细节不够，可以去看看附加章节的反汇编。 计算 goto 版本更快的原因有两个： 1. `switch` 每次迭代因为边界检查而做了更多工作。 2. 硬件分支预测的影响。 #### 每次迭代做更少的工作 如果你分析 `switch` 版本的反汇编，会发现每个操作码执行以下步骤： - 执行操作本身（例如 `OP_MUL2` 的 `val *= 2`） - `pc++` - 检查 `code[pc]` 的内容。如果在范围内（<= 6），则继续；否则从函数返回。 - 根据从 `code[pc]` 计算出的偏移量，通过跳转表跳转。 另一方面，计算 goto 版本执行以下步骤： - 执行操作本身 - `pc++` - 根据从 `code[pc]` 计算出的偏移量，通过跳转表跳转。 两者的区别显然在于 `switch` 的“边界检查”步骤。为什么需要它？你可能认为是因为 `default` 子句，但事实并非如此。即使没有 `default` 子句，编译器也必须为 `switch` 语句生成边界检查，以符合 C 标准。引用 C99 的话： > 如果没有转换后的 case 常量表达式匹配，并且没有 default 标签，则 switch 体的任何部分都不会被执行。 因此，标准强制编译器为 `switch` 生成“安全”的代码。安全性，一如既往，是有代价的，所以 `switch` 版本每次循环迭代做了更多工作。 #### 分支预测 现代 CPU 具有深度的指令流水线，并尽力确保流水线尽可能满载。分支是可能破坏流水线的一件事，这就是[分支预测器](http://en.wikipedia.org/wiki/Branch_predictor)存在的原因。简单来说（更多细节请阅读链接的维基百科文章），分支预测器是一种算法，CPU 用它来预先预测分支是否会被执行。由于 CPU 可以轻松地从分支目标预取指令，成功的预测可以使预取的指令有效，无需完全清空流水线。 分支预测器的一个特点是它们根据分支的地址来映射分支。由于 `switch` 语句有一个“主跳转”来分派所有操作码，预测它的目标相当困难。另一方面，计算 goto 语句被编译成每个操作码一个独立的跳转，因此鉴于指令经常成对出现，分支预测器更容易“锁定”各个跳转。这样想：对于每个跳转，分支预测器会保留下一个跳转位置的预测。如果每个操作码有一个跳转，这相当于预测操作码对中的第二个操作码，这实际上有时有一定成功机会。而如果只有一个跳转，预测在所有操作码之间共享，它们每次迭代都会互相干扰。 我不能确定这两个因素在 `switch` 和计算 goto 的速度差异中各自占多大比重，但如果要我猜，我会说是分支预测。 ### 其他 VM 中是如何做的？ 本文开头提到 Python 实现在其字节码解释器中使用了计算 goto。其他 VM 呢？ - Ruby 1.9 (YARV)：也使用计算 goto。 - Dalvik (Android Java VM)：使用计算 goto。 - Lua 5.2：使用 `switch`。 - 最后，如果你想看一个简单但真实的 VM，我邀请你查看 [Bobscheme](https://github.com/eliben/bobscheme) 的源代码——这是我自己的 Scheme 实现。其中的 `barevm` 组件（一个用 C++ 编写的字节码解释器）使用 `switch` 进行分派。 ### 附加：interp_switch 的详细反汇编 以下是 `interp_switch` 函数的注释版反汇编。代码使用 `gcc` 编译，启用了完全优化（`-O3`）。 ```asm 0000000000400650 <interp_switch>: # # 根据 System V x64 ABI，"code" 在 %rdi，"initval" 在 %rsi， # # 返回值在 %eax 中。 # 400650: 89 f0 mov %esi,%eax # # # 这些 NOPx 指令是填充，用于对齐其他指令。 # 400652: 66 0f 1f 44 00 00 nopw 0x0(%rax,%rax,1) # # # 循环主入口。 # # 如果 code[pc] <= 6，跳转到跳转表；否则继续到函数返回。 # 400658: 80 3f 06 cmpb $0x6,(%rdi) # 40065b: 76 03 jbe 400660 # # # 返回。同时也处理 OP_HALT # 40065d: f3 c3 repz retq # 40065f: 90 nop # # # 将 code[pc] 放入 %edx，并根据其值通过跳转表跳转。 # 400660: 0f b6 17 movzbl (%rdi),%edx # 400663: ff 24 d5 20 0b 40 00 jmpq *0x400b20(,%rdx,8) # 40066a: 66 0f 1f 44 00 00 nopw 0x0(%rax,%rax,1) # # # 处理 OP_ADD7 # 400670: 83 c0 07 add $0x7,%eax # 400673: 0f 1f 44 00 00 nopl 0x0(%rax,%rax,1) # # # pc++，然后回去检查下一个操作码。 # 400678: 48 83 c7 01 add $0x1,%rdi # 40067c: eb da jmp 400658 # 40067e: 66 90 xchg %ax,%ax # # # 处理 OP_DIV2 # 400680: 89 c2 mov %eax,%edx # 400682: c1 ea 1f shr $0x1f,%edx # 400685: 8d 04 02 lea (%rdx,%rax,1),%eax # 400688: d1 f8 sar %eax # 40068a: eb ec jmp 400678 # 40068c: 0f 1f 40 00 nopl 0x0(%rax) # # # 处理 OP_MUL2 # 400690: 01 c0 add %eax,%eax # 400692: eb e4 jmp 400678 # # # 处理 OP_DEC # 400694: 0f 1f 40 00 nopl 0x0(%rax) # 400698: 83 e8 01 sub $0x1,%eax # 40069b: eb db jmp 400678 # 40069d: 0f 1f 00 nopl (%rax) # # # 处理 OP_INC # 4006a0: 83 c0 01 add $0x1,%eax # 4006a3: eb d3 jmp 400678 # 4006a5: 0f 1f 00 nopl (%rax) # # # 处理 OP_NEG # 4006a8: f7 d8 neg %eax # 4006aa: eb cc jmp 400678 # 4006ac: 0f 1f 40 00 nopl 0x0(%rax) ``` 我是如何确定哪段代码处理哪个操作码的？注意，“表跳转”是通过以下指令完成的： ```asm jmpq *0x400b20(,%rdx,8) ``` 这条指令将 `%rdx` 中的值乘以 8，并作为从 `0x400b20` 开始的偏移量。因此跳转表本身位于地址 `0x400b20`，可以通过查看可执行文件的 `.rodata` 节看到： ```bash $ readelf -x .rodata interp_compute_gotos Hex dump of section '.rodata': 0x00400b00 01000200 00000000 00000000 00000000 ................ 0x00400b10 00000000 00000000 00000000 00000000 ................ 0x00400b20 5d064000 00000000 a0064000 00000000 ].@.......@..... 0x00400b30 98064000 00000000 90064000 00000000 ..@.......@..... 0x00400b40 80064000 00000000 70064000 00000000 [email protected].@..... 0x00400b50 a8064000 00000000 01010306 02020405 ..@............. ``` 读取从 `0x400b20` 开始的 8 字节值，得到映射关系： ``` 0x0 (OP_HALT) -> 0x40065d 0x1 (OP_INC) -> 0x4006a0 0x2 (OP_DEC) -> 0x400698 0x3 (OP_MUL2) -> 0x400690 0x4 (OP_DIV2) -> 0x400680 0x5 (OP_ADD7) -> 0x400670 0x6 (OP_NEG) -> 0x4006a8 ``` ### 附加：interp_cgoto 的详细反汇编 与上面类似，这是 `interp_cgoto` 函数的注释版反汇编。我会省略之前片段中解释过的部分，只关注计算 goto 实现特有的内容。 ```asm 00000000004006b0 <interp_cgoto>: # 4006b0: 0f b6 07 movzbl (%rdi),%eax # # # 从跳转表中获取跳转地址放入 %rdx # 4006b3: 48 8b 14 c5 e0 0b 40 mov 0x400be0(,%rax,8),%rdx # 4006ba: 00 # 4006bb: 89 f0 mov %esi,%eax # # # 通过调度表跳转。 # 4006bd: ff e2 jmpq *%rdx # 4006bf: 90 nop # # # 返回。同时也处理 OP_HALT # 4006c0: f3 c3 repz retq # 4006c2: 66 0f 1f 44 00 00 nopw 0x0(%rax,%rax,1) # # # 处理 OP_INC。 # # 这里的模式在其他指令处理中也重复出现。 # # 下一个操作码被放入 %edx（注意，编译器选择通过索引 code[1] 访问下一个操作码， # # 然后才执行 code++）。 # # 然后执行操作（这里 %eax += 1），最后通过表跳转到下一条指令。 # 4006c8: 0f b6 57 01 movzbl 0x1(%rdi),%edx # 4006cc: 83 c0 01 add $0x1,%eax # 4006cf: 48 8b 14 d5 e0 0b 40 mov 0x400be0(,%rdx,8),%rdx # 4006d6: 00 # 4006d7: 66 0f 1f 84 00 00 00 nopw 0x0(%rax,%rax,1) # 4006de: 00 00 # 4006e0: 48 83 c7 01 add $0x1,%rdi # 4006e4: ff e2 jmpq *%rdx # 4006e6: 66 2e 0f 1f 84 00 00 nopw %cs:0x0(%rax,%rax,1) # 4006ed: 00 00 00 # # # 处理 OP_DEC # 4006f0: 0f b6 57 01 movzbl 0x1(%rdi),%edx # 4006f4: 83 e8 01 sub $0x1,%eax # 4006f7: 48 8b 14 d5 e0 0b 40 mov 0x400be0(,%rdx,8),%rdx # 4006fe: 00 # 4006ff: 48 83 c7 01 add $0x1,%rdi # 400703: ff e2 jmpq *%rdx # 400705: 0f 1f 00 nopl (%rax) # # # 处理 OP_MUL2 # 400708: 0f b6 57 01 movzbl 0x1(%rdi),%edx # 40070c: 01 c0 add %eax,%eax # 40070e: 48 8b 14 d5 e0 0b 40 mov 0x400be0(,%rdx,8),%rdx # 400715: 00 # 400716: 48 83 c7 01 add $0x1,%rdi # 40071a: ff e2 jmpq *%rdx # 40071c: 0f 1f 40 00 nopl 0x0(%rax) # # # 处理 OP_DIV2 # 400720: 89 c2 mov %eax,%edx # 400722: c1 ea 1f shr $0x1f,%edx # 400725: 8d 04 02 lea (%rdx,%rax,1),%eax # 400728: 0f b6 57 01 movzbl 0x1(%rdi),%edx # 40072c: d1 f8 sar %eax # 40072e: 48 8b 14 d5 e0 0b 40 mov 0x400be0(,%rdx,8),%rdx # 400735: 00 # 400736: 48 83 c7 01 add $0x1,%rdi # 40073a: ff e2 jmpq *%rdx # 40073c: 0f 1f 40 00 nopl 0x0(%rax) # # # 处理 OP_ADD7 # 400740: 0f b6 57 01 movzbl 0x1(%rdi),%edx # 400744: 83 c0 07 add $0x7,%eax # 400747: 48 8b 14 d5 e0 0b 40 mov 0x400be0(,%rdx,8),%rdx # 40074e: 00 # 40074f: 48 83 c7 01 add $0x1,%rdi # 400753: ff e2 jmpq *%rdx # 400755: 0f 1f 00 nopl (%rax) # # # 处理 OP_NEG # 400758: 0f b6 57 01 movzbl 0x1(%rdi),%edx # 40075c: f7 d8 neg %eax # 40075e: 48 8b 14 d5 e0 0b 40 mov 0x400be0(,%rdx,8),%rdx # 400765: 00 # 400766: 48 83 c7 01 add $0x1,%rdi # 40076a: ff e2 jmpq *%rdx # 40076c: 0f 1f 40 00 nopl 0x0(%rax) ``` 同样，如果我们使用 `readelf` 查看地址 `0x400be0`，可以看到跳转表的内容，并推断出处理各个操作码的地： ``` 0x0 (OP_HALT) -> 0x4006c0 0x1 (OP_INC) -> 0x4006c8 0x2 (OP_DEC) -> 0x4006f0 0x3 (OP_MUL2) -> 0x400708 0x4 (OP_DIV2) -> 0x400720 0x5 (OP_ADD7) -> 0x400740 0x6 (OP_NEG) -> 0x400758 ``` [[1]](#id1) 据我所知，其他主流编译器如 ICC 和 Clang 也支持它，但 Visual C++ 不支持。 [[2]](#id3) 注意，此处的 `while` 循环并非必需，因为循环由 `goto` 分派隐式处理。我保留它只是为了与前面的示例在视觉上保持一致。 --- 如有评论，请发送[电子邮件](mailto:[email protected])给我。