最近，在闲逛浏览Python的源代码时，我在字节码VM实现（Python / ceval.c）中遇到了有关使用GCC的计算得到的gotos扩展的有趣评论。在好奇心的驱使下，我决定编写一个简单的示例，以评估针对简单VM使用计算的goto和传统的switch语句之间的区别。这篇文章是我的发现的总结。
首先，让我们弄清楚我所说的“ VM”是什么意思。在这种情况下-字节码解释器。简而言之，这是一个循环执行一系列指令的循环，一个接一个地执行它们。
以Python的2000行强（不包括一堆支持宏）PyEval_EvalFrameEx为例，这不是很有教育意义。因此，我将定义一个微型VM，其唯一状态是整数，并包含一些用于操作它的指令。虽然很简单，但是此VM的总体结构与真实世界的VM非常相似。该VM非常基础，以至于解释它的最佳方法就是展示其实现：
＃定义OP_HALT 0x0＃定义OP_INC 0x1＃定义OP_DEC 0x2＃定义OP_MUL2 0x3＃定义OP_DIV2 0x4＃定义OP_ADD7 0x5＃定义OP_NEG 0x6 int interp_switch（unsigned char *代码，int initval）（int pc = 0; int val = initval; while（1）{开关（code [pc ++]）{case OP_HALT：return val;情况OP_INC：val ++;打破;情况OP_DEC：val--;打破;情况OP_MUL2：val * = 2;打破;情况OP_DIV2：val / = 2;打破;情况OP_ADD7：val + = 7;打破;情况OP_NEG：val = -val;打破;默认值：return val; }}}
请注意，这完全是＆＃34; standard＆＃34; C.无限循环遍历指令流，而switch语句根据指令操作码选择要执行的操作。在此示例中，控制始终是线性的（pc在指令之间仅前进1），但是使用流程控制指令以不那么琐碎的方式修改pc来扩展它并不困难。
switch语句应由C编译器非常有效地实现-该条件用作查找表的偏移量，该查找表说明下一步跳转到哪里。但是，事实证明，存在一个流行的GCC扩展，该扩展允许编译器生成更快的代码。
我将非常简要地介绍计算的goto的细节。有关更多信息，请转到GCC文档或Google。
计算的goto基本上是C的两个新功能的组合。第一个功能是将标签的地址放入void *。
第二种是在变量表达式上调用goto而不是在编译时已知的标签上，即：
不久我们将看到，这两个功能结合使用时，可以简化主VM循环的有趣替代实现。
对于任何有汇编语言编程经验的人来说，计算后的goto立即有意义，因为它仅公开了大多数现代CPU体系结构所具有的通用指令-跳转到寄存器（也称为间接跳转）。
int interp_cgoto（unsigned char *代码，int initval）{/ * dispatch_table中标签的索引是相关的操作码* / static void * dispatch_table [] = {＆amp;＆amp; do_halt，＆amp;＆amp; do_inc，＆amp;＆amp; ; do_dec，＆amp;＆do_mul2，＆amp;＆amp; do_div2，＆amp;＆amp; do_add7，＆amp;＆amp; do_neg}; #define DISPATCH（）转到* dispatch_table [code [pc ++]] int pc = 0; int val = initval;调度（）; while（1）{do_halt：return val; do_inc：val ++;调度（）; do_dec：val--;调度（）; do_mul2：val * = 2;调度（）; do_div2：val / = 2;调度（）; do_add7：val + = 7;调度（）; do_neg：val = -val;调度（）; }}
我使用随机操作码做了一些简单的基准测试，goto版本比switch版本快25％。自然，这取决于数据，因此实际程序的结果可能会有所不同。
CPython实现内部的注释指出，使用计算的goto可使Python VM加快15-20％，这也与我在网上看到的其他数字一致。
在帖子的更下方，您会发现两个＆＃34;奖金＆＃34;这些部分包含上述两个函数的带注释的反汇编，这些函数在GCC的-O3优化级别上进行了编译。它是我的读者真正的低水平爱好者的天堂，也是我自己的未来参考。在这里，我打算解释为什么所计算的goto代码在较高的级别上会更快，因此，如果您觉得没有足够的细节，请仔细阅读奖金部分中的反汇编。
如果您检查一下交换机版本的反汇编，您会发现它按照每个操作码执行以下操作：
检查代码[pc]的内容。如果在范围之内（＆lt; = 6），请继续。否则从函数返回。
两者之间的区别显然是“界限检查”。切换步骤。为什么需要它？您可能认为这是由于default子句引起的，但这不是正确的。即使没有default子句，编译器也必须为switch语句生成边界检查以符合C标准。从C99引用：
如果没有转换后的大小写常量表达式匹配并且没有默认标签，则不会执行开关主体的任何部分。
因此，该标准强制编译器生成＆＃34; safe＆＃34;。开关的代码。像往常一样，安全性是有成本的，因此开关版本最终每次循环迭代都要做更多的工作。
现代CPU具有很深的指令流水线，并且要竭尽全力确保流水线保持尽可能完整。分支可能会破坏管道的一天，这就是分支预测变量存在的原因。简而言之（有关更多详细信息，请阅读链接的Wikipedia文章），它是CPU用来尝试预先预测是否将采用分支的算法。由于CPU可以轻松地从分支目标中预取指令，因此成功的预测可以使预取的指令有效，并且无需完全刷新管道。
分支预测变量的作用是它们根据其地址映射分支。由于switch语句具有单个＆＃34;主跳转＆＃34;分派所有操作码，预测其目的地非常困难。另一方面，将计算出的goto语句编译为每个操作码一个单独的跳转，因此，鉴于指令通常成对出现，分支预测程序更容易返回原位。正确地进行各种跳跃
这样考虑：对于每次跳转，分支预测器都会预测下一次跳转的位置。如果每个操作码都有一个跳跃，则等效于预测一个操作码对中的第二个操作码，实际上这有时会获得成功的机会。另一方面，如果只有一次跳转，则预测在所有操作码之间共享，并且每次迭代时它们都会互相踩脚趾。
我不能肯定地说两个因素中的哪个因素在开关和计算的goto之间的速度差中所占的比重更大，但是如果我不得不猜测那是分支预测。
因此，本文首先提到Python实现在其字节码解释器中使用了计算的goto。那其他VM呢？
最后，如果您想看一个简单但现实的VM，我邀请您检查Bobscheme的源代码-我自己的Scheme实现。 ＆＃34; barevm＆＃34;组件（C ++中的字节码解释器）使用开关进行分派。
这是interp_switch函数的带注释的反汇编。该代码是使用gcc编译的，可以进行全面优化（-O3）。
0000000000400650＆lt; interp_switch＆gt;：##每个系统V x64 ABI，＆＃34; code＆＃34;在％rdi中，＆＃34; initval＆＃34; ＃400650：66 0f 1f 44 00 00在％rsi中，返回的值在％eax中。＃400650：89 f0 mov％esi，％eax ##这另一个NOPx指令是用于对齐其他＃指令的填充符。 nopw 0x0（％rax，％rax，1）##这是循环的主要条目。＃如果code [pc]＆lt; = 6，请转到跳转表。否则，继续从该函数返回＃。＃400658：80 3f 06 cmpb $ 0x6，（％rdi）40065b：76 03 jbe 400660＆lt; interp_switch + 0x10＆gt; ##返回。这也可以处理OP_HALT＃40065d：f3 c3 repz retq 40065f：90 nop ##将代码[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加$ 0x7，％eax 400673：0f 1f 44 00 00 nopl 0x0（％rax，％rax，1）## pc ++，然后返回以检查下一个操作码。＃400678：48 83 c7 01添加$ 0x1，％rdi 40067c： eb da jmp 400658＆lt; interp_switch + 0x8＆gt; 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＆lt; interp_switch + 0x28＆gt; 40068c：0f 1f 40 00 nopl 0x0（％rax）##处理OP_MUL2＃400690：01 c0添加％eax，％eax 400692：eb e4 jmp 400678＆lt; interp_switch + 0x28＆gt; ##处理OP_DEC＃400694：0f 1f 40 00 nopl 0x0（％rax）400698：83 e8 01 sub $ 0x1，％eax 40069b：eb db jmp 400678＆lt; interp_switch + 0x28＆gt; 40069d：0f 1f 00 nopl（％rax）##句柄OP_INC＃4006a0：83 c0 01加$ 0x1，％eax 4006a3：eb d3 jmp 400678＆lt; interp_switch + 0x28＆gt; 4006a5：0f 1f 00 nopl（％rax）##处理OP_NEG＃4006a8：f7 d8 neg％eax 4006aa：eb cc jmp 400678＆lt; interp_switch + 0x28＆gt; 4006ac：0f 1f 40 00 nopl 0x0（％rax）
如何确定代码的哪一部分处理哪个操作码？请注意，＆＃34;表跳转＆＃34;通过以下方式完成：
这将以％rdx表示的值乘以8，然后将结果用作从0x400b20开始的偏移量。因此，跳转表本身包含在地址0x400b20中，可以通过检查可执行文件的.rodata部分来看到它：
$ readelf -x .rodata interp_compute_gotos＆＃39; .rodata＆＃39;的十六进制转储：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 .. @ .... p。@ ..... 0x00400b50 a8064000 00000000 01010306 02020405 .. @ .............
0x0（OP_HALT）-> 0x40065d0x1（OP_INC）-> 0x4006a00x2（OP_DEC）-> 0x4006980x3（OP_MUL2）-> 0x4006900x4（OP_DIV2）-> 0x4006800x5（OP_ADD7）-> 0x4006700x6（OP_NEG）-> 0x4006a8
与上述类似，这是interp_cgoto函数的带注释的反汇编。我将省略前面片段中解释的内容，尝试仅关注计算的goto实现所特有的内容。
00000000004006b0＆lt; interp_cgoto＆gt ;: 4006b0：0f b6 07 movzbl（％rdi），％eax ##从跳转表中移动跳转地址indo％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中（请注意，这里的编译器＃选择通过索引代码[1]来访问下一个操作码，仅稍后＃执行代码++。＃然后完成操作（此处为％eax + = 1），最后是一个将指令从表跳转到下一条指令。＃4006c8：0f b6 57 01 movzbl 0x1（％rdi），％edx 4006cc：83 c0 01加$ 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加$ 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加$ 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添加％eax，％eax 40070e：48 8b 14 d5 e0 0b 40 mov 0x400be0（，％rdx，8），％rdx 400715：00 400716：48 83 c7 01加$ 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加$ 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加$ 0x7， ％eax 400747：48 8b 14 d5 e0 0b 40 mov 0x400be0（，％rdx，8），％rdx 40074e：00 40074f：48 83 c7 01加$ 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）-> 0x4006c00x1（OP_INC）-> 0x4006c80x2（OP_DEC）-> 0x4006f00x3（OP_MUL2）-> 0x4007080x4（OP_DIV2）-> 0x4007200x5（OP_ADD7）-> 0x4007400x6（OP_NEG）-> 0x400758 据我所知，它受到其他主要编译器（例如ICC和Clang）的支持，但不受Visual C ++的支持。 请注意，这里的while循环并不是必需的，因为循环是由goto调度隐式处理的。 我只是为了与以前的示例保持视觉一致性而将其保留。