4

这个问题主要是在阅读了 Aater Suleman 的这篇关于从软件方面改进分支预测的文章之后的后续问题。作者提供了一种“展开”条件语句的方法，以增加在 2 位饱和计数器方案的情况下预测分支的概率。这是一段摘录：

让我用一个例子来解释。让我们假设 X 是 0 到 99 之间的随机变量。我想运行以下代码：

if (X > 5 && X < 95) //90% 的时间使用分支
do_something();

但是，如果我将代码编写为：

if(X > 5) //95% 的时间
使用分支 if(X < 95) //95% 的时间使用分支
do_something();

分支预测器可以更准确地预测这两个分支，这可能会带来更好的性能，因为分配给这两个分支的计数器更有可能在采取时保持饱和（因为两个未采取的可能性较小）。

一般来说，每当您在 if 语句中对条件进行 ANDing/ORing 时，您都应该考虑该组合是否会更偏向或更少偏向，并选择更偏向的版本。

我的问题是：编译器是否一直遵循这种启发式方法？由于编译器存在于 ISA 的范围内，而架构和分支预测方案存在于处理器和更具体的硬件实现的范围内，编译器是否甚至有权做这样的事情？

我的直觉是，以这种方式扩展控制语句不会损害性能，但同时我还没有找到任何证据表明编译器进行了这种优化。如果是这样，他们为什么不呢？我在推理中遗漏了什么，有人可以提供一个例子，说明这种优化对某个架构或预测方案是有害的吗？

谢谢。

4

2 回答 2

4

苏尔曼似乎没有意识到

if (X > 5 && X < 95)
  do_something();

和

if(X > 5)
  if(X < 95)
    do_something();

在 C 和 C++ 中是语义等价的。最新的 C 标准状态 (6.5.13/4)：

与按位二进制 & 运算符不同，&& 运算符保证从左到右的求值；如果计算第二个操作数，则在第一个和第二个操作数的计算之间存在一个序列点。如果第一个操作数比较等于 0，则不计算第二个操作数。

编译器可能会或可能不会为两个代码示例生成相同的代码。重写程序以使用一种或另一种形式来提高性能并不是一个好主意。结果将在很大程度上取决于编译器版本、ISA 以及可能更多的变量。将这种优化留给编译器，但给编译器它需要的信息。

像 GCC 和 LLVM 这样的一些编译器允许你给出这样的明确提示：

if (__builtin_expect(X > 5, 1)) {
  // This block is likely to be taken.
}
if (__builtin_expect(X <= 5, 0)) {
  // This block is unlikely to be taken.
}

另一种方法是使用配置文件引导优化。第一步需要对程序进行一次或多次测试，以生成包含有关分支指令的统计信息的数据库。在第二步中，编译器可以使用这个数据库来优化你的程序。有关详细信息，请参阅您的编译器手册。

于 2013-01-08T18:52:44.473 回答
1

您可以通过将此代码替换为

if (((unsigned int) X) - 6 < 88)
    do_something ();

__builtin_expect 显然不能改变条件是真还是假。它主要用于已采用的分支比未采用的分支慢的处理器。所以编译器会编译

if (__builtin_expect (condition, 0))
    statement;

morestuff ();

对此：

if (condition) goto elsewhere;
backhere: morestuff ();

....

elsewhere: statement; goto backhere;

这样通常不会采用任何分支，而不是通常的

if (! condition) goto nextstatement;
statement;
nextstatement: morestuff ();

但在问题中，事情并非如此。if (cond1 && cond2) 不会生成单个分支（仅在具有非常聪明的编译器的特殊情况下），因此比较无效。如果是这样，两个预测正确率为 95% 的分支并不比一个预测为 90% 的分支好，因为错误预测的数量是相同的。

于 2014-06-10T22:14:56.020 回答