您知道哪些技术可以避免条件分支？

Question

有时CPU占用大部分时间的循环经常会有一些分支预测错误(错误预测)(接近0.5概率).我在非常孤立的线程上看到了一些技术但从未列出过.我所知道的那些已经解决了条件可以变为bool并且以某种方式使用0/1来改变的情况.是否有其他可以避免的条件分支？

例如(伪代码)

loop () {
  if (in[i] < C )
    out[o++] = in[i++]
  ...
}

可以用这样的东西重写,可能会失去一些可读性:

loop() {
  out[o] = in[i]  // copy anyway, just don't increment
  inc = in[i] < C  // increment counters? (0 or 1)
  o += inc
  i += inc
}

此外,我已经看到在野外的技术在某些情况下在有条件的情况下改变&&,&现在正在逃避我的思想.我是这个优化级别的新手,但确实感觉还有更多.

Answer 1

使用Matt Joiner的例子:

if (b > a) b = a;

您也可以执行以下操作,而无需深入了解汇编代码:

bool if_else = b > a;
b = a * if_else + b * !if_else;

Answer 2

我认为避免分支的最常用方法是利用位并行来减少代码中的总跳转.基本块越长,管道冲洗的频率越低.

正如其他人提到的那样,如果你想做的不仅仅是展开循环,并提供分支提示,那么你将需要进入汇编.当然,这应该非常谨慎地进行:在大多数情况下,典型的编译器可以编写比人类更好的汇编.你最大的希望是削减粗糙的边缘,并做出编译器无法推断的假设.

以下是以下C代码的示例:

if (b > a) b = a;

在没有任何跳转的程序集中,通过使用位操作(和极端注释):

sub eax, ebx ; = a - b
sbb edx, edx ; = (b > a) ? 0xFFFFFFFF : 0
and edx, eax ; = (b > a) ? a - b : 0
add ebx, edx ; b = (b > a) ? b + (a - b) : b + 0

请注意,虽然组件爱好者会立即跳过条件移动,但这只是因为它们易于理解并在方便的单个指令中提供更高级别的语言概念.它们不一定更快,在较旧的处理器上不可用,并且通过将C代码映射到相应的条件移动指令,您只需执行编译器的工作.

Answer 3

当您必须执行多个嵌套测试才能获得答案时，可以应用原始问题中演示的技术的扩展。您可以根据所有测试的结果构建一个小的位掩码，并在表中“查找”答案。

if (a) {
  if (b) {
    result = q;
  } else {
    result = r;
  }
} else {
  if (b) {
    result = s;
  } else {
    result = t;
  }
}

如果 a 和 b 几乎是随机的（例如，来自任意数据），并且这是在一个紧密的循环中，那么分支预测失败确实会减慢速度。可以写成：

// assuming a and b are bools and thus exactly 0 or 1 ...
static const table[] = { t, s, r, q };
unsigned index = (a << 1) | b;
result = table[index];

您可以将其概括为几个条件。我已经看到它完成了 4 个。不过，如果嵌套变得那么深，您需要确保测试所有这些测试确实比仅进行短路评估建议的最少测试要快。

Answer 4

您给出的示例的概括是"用数学替换条件评估"; 条件分支避免很大程度上归结为这一点.

替换&&的&原因在于,由于&&是短路,因此它本身构成了条件评估. &如果双方都是0或1,并且不是短路,则会获得相同的逻辑结果.同样适用于||和|除了您不需要确保边被约束为0或1(再次,仅用于逻辑目的,即您仅使用布尔的结果).

Answer 5

在这个级别上，事情非常依赖于硬件和依赖于编译器。您使用的编译器是否足够聪明来编译<而没有控制流？x86上的gcc足够聪明；lcc不是。在较旧的或嵌入式指令集上，可能没有控制流就无法计算<。

除了类似Cassandra的警告之外，很难做出任何有用的一般性说明。因此，以下一些一般性声明可能无济于事：

• 现代的分支预测硬件非常好。如果您能找到一个真实的程序，其中不良分支预测的耗费速度超过1％-2％，我会感到非常惊讶。

• 告诉您在哪里可以找到分支错误预测的性能计数器或其他工具是必不可少的。

• 如果您确实需要改进此类代码，我将研究跟踪调度和循环展开：

  • 循环展开将复制循环主体，并为您的优化器提供更多可使用的控制流。

  • 跟踪调度可以识别最可能采用的路径，以及其他技巧，它可以调整分支方向，以便分支预测硬件在最常见的路径上可以更好地工作。对于展开的循环，路径越来越多，因此跟踪调度程序需要处理更多的工作。

• 我很乐意尝试自己编写汇编代码。当下一个芯片带有新的分支预测硬件时，极有可能使您的所有辛苦工作付诸东流。相反，我会寻找一个反馈导向的优化编译器。