22

我最近在这里阅读了这个问题为什么处理排序数组比处理未排序数组更快？并发现答案绝对令人着迷，并且在处理基于数据的分支时完全改变了我对编程的看法。

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

不幸的是，在阅读了上述帖子后，我突然想到，我计算机中的分支预测器绝对无法预测开关盒的跳跃。因此，每次切换开关盒被导航时，管道都必须被完全擦除，从而导致原本应该是一个非常快速的程序的几个周期延迟（我的代码中甚至没有乘法）。

我相信你们中的大多数人都在想“哦，这里的解决方案很简单，转向动态重新编译”。是的，这似乎确实会削减大部分开关盒并大大提高速度。不幸的是，我的主要兴趣是模拟较旧的 8 位和 16 位时代的控制台（这里的英特尔 8080 只是一个示例，因为它是我最简单的一段模拟代码），其中与视频和声音一样，保持精确指令的周期和时间很重要必须根据这些确切的时间进行处理。

当处理这种级别的准确性时，性能成为一个问题，即使对于较旧的控制台也是如此（例如，查看 bSnes）。在处理具有长管道的处理器时，是否有任何追索权，或者这只是一个事实？

4

4 回答 4

12

相反，switch语句很可能会转换为跳转表，这意味着它们可能执行几个ifs（用于范围检查）和一次跳转。s 不应导致分支预测出现问题，if因为您不太可能有错误的操作码。跳转对管道不是那么友好，但最后，它只是整个switch语句的一个..

我不相信您可以将switch操作码的长语句转换为任何其他可以带来更好性能的形式。当然，前提是您的编译器足够聪明，可以将其转换为跳转表。如果没有，您可以手动执行此操作。

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

编辑

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

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

另一方面，分支目标预测试图猜测跳跃将在哪里结束。

因此，您的陈述“分支预测器无法预测跳跃”应该是“分支目标预测器无法预测跳跃”。

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

于 2012-07-26T11:31:52.053 回答
10

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

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

避免这种惩罚的唯一方法是确保执行相同的指令，而不管操作码的值如何。这通常可以通过使用条件移动（添加数据依赖关系因此比可预测的分支慢）或以其他方式在代码路径中寻找对称性来完成。考虑到您要尝试执行的操作，这可能是不可能的，如果是这样，那么几乎肯定会增加比错误预测的 15-25 个时钟周期更大的开销。

总而言之，在现代架构上，没有什么比 switch/case 更有效的了，而且错误预测分支的成本也没有你想象的那么高。

于 2012-07-26T11:42:20.507 回答
7

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

在较旧的机器上，比如 1997 年的 Intel P6，间接跳转可能会导致分支预测错误。

在现代机器上，比如 Intel 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 向表树，树中的每个条目都指向到其他节点，或到要评估的函数。

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

一棵N路跳转树，因为当跳转表中的case数量变得非常大时会出现问题-在我在1980年代编写的工具mkIrecog（make指令识别器）中，我通常会跳转表达到64K条目的大小，即在 16 位上跳跃。当跳转表的大小超过 16M（24 位）时，当时的编译器就崩溃了。

数据驱动，即指向其他节点的节点树，因为 (a) 在较旧的机器上可能无法很好地预测间接跳转，并且 (b) 事实证明，指令之间的大部分时间都有公共代码 - 而不是具有跳转到每条指令的案例时的分支预测错误，然后执行公共代码，然后再次切换，并获得第二个错误预测，您执行公共代码，参数略有不同（例如，您消耗了多少指令流的位，以及下一组要分支的位是 (are)。

我在 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 路、分支或表查找。）

于 2013-04-03T22:28:40.453 回答
2

我想我会添加一些东西，因为没有人提到它。

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

但是，如果您采用 N 比较方式，我会想到两件事：

首先，您可以进行 log(N) 不等式比较，而不是进行 N 相等比较，通过二分法根据它们的数字操作码测试您的指令（或者如果值空间接近满，则逐位测试数字）。这是一个有点像哈希表，你实现一个静态树来查找最终元素。

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

但我看不出这比中等 15 个周期的惩罚更快，除非你有 99% 的 MOV 并且你在其他测试之前为 MOV 操作码设置了相等性。

于 2013-01-25T17:02:32.947 回答