在CPU仿真中使用switch case时如何处理分支预测

Question

在CPU仿真中使用switch case时如何处理分支预测

cperformancecompiler-optimizationemulationbranch-prediction

23

我最近阅读了这里的问题为什么处理有序数组比无序数组快？，发现答案非常有趣，并且完全改变了我在处理基于数据的分支时编程的观点。

我目前有一个相当基本但完全可用的解释器，使用C语言编写，模拟Intel 8080处理器。其核心是一个256行的switch-case表，用于处理每个操作码。我的最初想法是这显然是最快的工作方法，因为8080指令集中的操作码编码不一致，解码会增加很多复杂性、不一致性和一次性情况。而一个充满预处理器宏的switch-case表是很整洁且易于维护的。

不幸的是，在阅读了之前提到的文章后，我意识到我的计算机中的分支预测器绝对无法预测switch case的跳转。因此，每次导航switch-case时，流水线都必须完全清除，导致在原本应该是极快的程序中出现几个周期的延迟（我的代码中甚至没有乘法运算）。

我相信你们大多数人都会想，“哦，这里的解决方案很简单，转向动态重新编译。” 是的，这似乎可以削减大部分switch-case，并显著提高速度。不幸的是，我的主要兴趣是模拟旧的8位和16位时代的游戏机（这里的Intel 8080只是一个示例，因为它是我模拟代码中最简单的一部分），在这些游戏机中，根据这些确切定时处理视频和音频非常重要。

当处理这个级别的精度时，性能成为一个问题，即使对于旧的游戏机来说也是如此（例如看看bSnes）。是否有任何救济措施，或者这只是处理具有长流水线的处理器时的事实？

- Fascia

FYI：我发现在gcc中使用计算goto比使用大型switch要快得多。 - Vaughn Cato

2

你的问题并没有完全让我明白你是否真的进行了测试来衡量性能。你所提到的帖子确实很好，但这样的信息会让人们“过度反应”，解决只导致1%性能损失（或使情况变得更糟）的性能问题。过早优化是万恶之源。 - Bart

请参阅分支预测和解释器性能-不要相信民间传说，现代IT-TAGE预测器能够很好地处理单个“grand central dispatch” switch语句。同时，还可以参考X86预取优化：“computed goto”线程代码以及有关解释器的此问答，这些内容对于解释CPU仿真器与R或Python同样适用，而不是JIT仿真器。 - Peter Cordes

1

此外：“管道必须完全清除” - 不完全是这样，具有“快速恢复”（https://dev59.com/FVUL5IYBdhLWcg3wB0FJ）的现代OoO执行CPU只需要刷新在错误预测分支之后的指令。它们可以检测到错误预测并开始恢复，而一些来自分支之前的指令尚未完成，因此如果你很幸运（并且分支不依赖于该缓存未命中加载的数据！），则错误预测惩罚可以与缓存未命中重叠。但是，如果在紧密循环中出现分支未命中，则仍然会很糟糕。 - Peter Cordes

4个回答

11

由于您的256路开关语句中的分支密集，编译器会将其实现为跳转表，因此每次通过此代码时都会触发单个分支错误预测（因为间接跳转不会显示任何可预测的行为），这一惩罚在现代CPU（Sandy Bridge）上大约为15个时钟周期，或者在缺乏微操作缓存的旧微架构上可能高达25个周期。关于这种事情的一个很好的参考是agner.org上的“软件优化资源”，“C ++中的软件优化”第43页是一个很好的开始。

http://www.agner.org/optimize/?e=0,34

唯一可以避免此惩罚的方法是确保无论操作码的值如何，都执行相同的指令。这通常可以通过使用条件移动（添加数据依赖项，因此比可预测的分支慢）或以其他方式查找代码路径中的对称性来完成。考虑到您试图做的事情，这可能不太可能，并且如果确实这样做，那么它几乎肯定会增加超过误判的15-25个时钟周期的开销。

总之，在现代架构上，您不太可能做任何比switch / case更有效的事情，而错误预测分支的成本并不像您期望的那样高。

- jleahy

1

不幸的是，在处理仿真时，您可能会尝试每秒执行数千万甚至数亿条指令。如果对于每个指令都有15个周期的停机时间，那么这将导致相当大的性能影响。 - Fascia

4

这里没有免费的午餐。如果您想要做几件事情，而且这是完全不可预测的，您必须执行每个（可能的）可能性的代码或者进行管道清除。唯一的替代方案是将您尝试模拟的内容JIT编译成本地代码（这就是VMWare和其他x86仿真器在虚拟化之前的工作方式）。您不能指望处理器在读取操作码之前推测执行您的操作码。 - jleahy

8

间接跳转可能是指令解码的最佳选择。

在旧机器上，比如1997年的英特尔P6，间接跳转可能会出现分支预测错误。

在现代机器上，比如英特尔Core i7，有一个间接跳转预测器，可以相当好地避免分支预测错误。

但即使在没有间接跳转预测器的旧机器上，你也可以使用一个技巧。这个技巧（曾经）在很久以前的英特尔P6日子里，在《英特尔代码优化指南》中有记录：

不要生成像下面这样的东西

    loop:
       load reg := next_instruction_bits // or byte or word
       load reg2 := instruction_table[reg]
       jmp [reg]
    label_instruction_00h_ADD: ...
       jmp loop
    label_instruction_01h_SUB: ...
       jmp loop
    ...

生成代码如下

    loop:
       load reg := next_instruction_bits // or byte or word
       load reg2 := instruction_table[reg]
       jmp [reg]
    label_instruction_00h_ADD: ...
       load reg := next_instruction_bits // or byte or word
       load reg2 := instruction_table[reg]
       jmp [reg]
    label_instruction_01h_SUB: ...
       load reg := next_instruction_bits // or byte or word
       load reg2 := instruction_table[reg]
       jmp [reg]
    ...

即在每个位置用循环顶部的代码替换跳转到指令获取/解码/执行循环的跳转。事实证明，即使没有间接预测器，在这种后续的线程代码中，这样做的分支预测要好得多。更准确地说，在只有单个间接跳转副本的原始代码上，条件、单目标、PC索引BTB将比较适用于此后续线程代码。

大多数指令集都有特殊的模式——例如，在Intel x86上，比较指令几乎总是跟随着一个分支。

祝你好运并玩得开心！

（如果你在意的话，工业中指令集模拟器使用的指令解码器几乎总是执行N路跳转树，或者数据驱动的双重导航N路表树，每个树节点中的条目指向其他节点或函数进行评估。）

哦，也许我应该提一下：这些表格、开关语句或数据结构是由专用工具生成的。

一种N路跳转的树，因为当跳转表中的案例数量变得非常大时会出现问题 - 在我在20世纪80年代编写的工具mkIrecog（制作指令识别器）中，我通常会制作大小为64K条目的跳转表，即使用16位进行跳转。当跳转表的大小超过16M（24位）时，当时的编译器会崩溃。

数据驱动，即指向其他节点的节点树，因为（a）在旧机器上无法很好地预测间接跳转，（b）事实证明，许多时候指令之间存在共同代码 - 而不是在跳转到每个指令的情况下出现分支误判，然后执行公共代码，再次切换，并获得第二个错误预测，您可以执行公共代码，稍微调整参数（例如，您消耗指令流的位数以及下一组要跳转的位在哪里）。

在mkIrecog中，我非常激进，允许使用32位开关，尽管实际限制几乎总是将我限制在16-24位。我记得我经常将第一个解码视为16或18位开关（64K-256K条目），而所有其他解码都要小得多，不超过10位。

嗯：我大约在1990年发布了mkIrecog到Usenet。 ftp://ftp.lf.net/pub/unix/programming/misc/mkIrecog.tar.gz 如果您感兴趣，可以看到使用的表格。（请友善一点：当时我还很年轻。我不记得这是Pascal还是C语言。我已经多次重写它 - 尽管我尚未重写为使用C++位向量。）

我认识的大多数做这种事情的人都是以字节为单位进行操作 - 即采用8位、256路分支或表查找。

- Krazy Glew

1

对于任何感兴趣的人，这种技术通常被称为“标签作为值”，并且在gcc和clang中得到支持。 - Chuu

1

FYI，对于现代IT-TAGE预测器（Intel自Haswell（2013年），AMD自Zen2）来说，跳跃线程并不是必需的，因为它们可以将单个分支的历史记录分布在整个预测器中。请参见Branch Prediction and the Performance of Interpreters - Don't Trust Folklore。虽然这种方式不会像grand-central-dispatch分支那样损害性能，但我不知道所有相关的现代CPU（如ARM服务器核心）是否具有IT-TAGE或类似的预测器。另请参见关于解释器的此问答。 - Peter Cordes

1

此外，Darek Mihocka在2008年的一篇文章中讨论了这种模式，讨论了解释CPU模拟器（例如他工作的Bochs）的情境以及它在当时相关的各种CPU上的表现。"computed goto"线程化代码的X86预取优化总结如下。 - Peter Cordes

2

我想补充一些内容，因为没有人提到它。

当然，间接跳转可能是最好的选择。

然而，如果你采用N比较方法，有两件事情让我想起：

首先，你可以通过二分法（或者逐位测试数字）基于数值操作码来测试指令，而不是进行N个等式比较。这有点像哈希表，你可以实现一个静态树来找到最终元素。

其次，你可以对要执行的二进制代码进行分析。你甚至可以在每个二进制文件中执行此操作，并在运行时修补模拟器。这个分析将构建代表指令频率的直方图，然后你将组织你的测试，以便最常见的指令被正确预测。

但是，除非你有99%的MOV并在其他测试之前放置一个MOV操作码的等式，否则我看不出这比中等15个周期的惩罚更快。

- user2011773

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Shahbaz · Accepted Answer

相反地，switch语句很可能会转换为跳转表，这意味着它们执行可能只有几个if（用于范围检查）和单个跳转。这些if不应该对分支预测造成问题，因为不太可能会出现错误的操作码。跳转与流水线不太友好，但最终在整个switch语句中只有一个。

我不认为您可以将一长串操作码的switch语句转换为任何其他形式，从而获得更好的性能。当然，前提是您的编译器足够聪明，可以将其转换为跳转表。如果不能，请手动转换。

如有疑问，请实施其他方法并衡量性能。

编辑

首先，请确保不要混淆分支预测和分支目标预测。

分支预测仅适用于分支语句。它决定分支条件是否会失败或成功。它们与跳转语句无关。

另一方面，分支目标预测试图猜测跳转的结束位置。

因此，您的说法“分支预测无法预测跳转”应该是“分支目标预测无法预测跳转”。

在您的特定情况下，我认为您实际上无法避免这种情况。如果您有一个非常小的操作集，也许可以想出涵盖所有操作的公式，就像逻辑电路中的那些操作一样。但是，对于像CPU这样大的指令集，即使它是RISC，那个计算的成本也比单个跳转的惩罚要高得多。