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

有时CPU占用大部分时间的循环经常会有一些分支预测错误(错误预测)(接近.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 } 

此外,我已经看到了野外技术在某些环境中改变了&&&条件,现在正在逃避我的思绪。 我是这个优化级别的新手,但确实感觉还有更多。

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

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

以下是以下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代码映射到相应的条件移动指令中,您只需执行编译器的工作。

使用Matt Joiner的例子:

 if (b > a) b = a; 

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

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

您给出的示例的概括是“用数学替换条件评估”; 条件分支避免很大程度上归结为那个。

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

GCC已经足够聪明,可以用更简单的指令替换条件。 例如,较新的Intel处理器提供cmov (条件移动)。 如果你可以使用它,SSE2提供一些指令来一次比较4个整数 (或8个短路,或16个字符)。

另外计算最小值你可以使用(参见这些魔术技巧 ):

 min(x, y) = x+(((yx)>>(WORDBITS-1))&(yx)) 

但是,要注意以下事项:

 c[i][j] = min(c[i][j], c[i][k] + c[j][k]); // from Floyd-Warshal algorithm 

即使没有隐含的跳跃也比慢得多

 int tmp = c[i][k] + c[j][k]; if (tmp < c[i][j]) c[i][j] = tmp; 

我最好的猜测是,在第一个片段中,您会更频繁地污染缓存,而在第二个片段中则不会。

在这个级别,事物非常依赖于硬件和编译器。 您使用的编译器是否足够智能以编译<无控制流? x86上的gcc足够聪明; lcc不是。 在旧的或嵌入式指令集上,可能无法计算<没有控制流。

除了类似卡桑德拉的警告之外,很难做出任何有用的一般性陈述。 所以这里有一些可能无益的一般性陈述:

  • 现代分支预测硬件非常好。 如果你能找到一个真正的程序,其中坏分支预测的成本降低超过1%-2%,我会非常惊讶。

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

  • 如果你真的需要改进这样的代码,我会研究跟踪调度和循环展开:

    • 循环展开复制循环体并为优化器提供更多控制流以便使用。

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

  • 我对在集会中自己编写代码感到谨慎。 当下一个芯片推出新的分支预测硬件时,很有可能你所有的努力都耗尽了。 相反,我会寻找一个反馈导向的优化编译器

在我看来,如果你达到这种优化水平,可能是时候直接进入汇编语言了。

基本上,你依靠编译器生成一个特定的程序集模式,无论如何都要利用C中的这种优化。 很难准确猜出编译器将生成什么代码,所以你必须在任何时候进行一些小改动时再看它 – 为什么不在assembly中做它并用它来完成呢?

大多数处理器提供的分支预测优于50%。 事实上,如果你的分支预测得到1%的提高,那么你可以发表一篇论文。 如果您有兴趣,有很多关于这个主题的论文。

你最好担心缓存命中和未命中。

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

 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完成了。但是,如果嵌套深入,你想确保测试所有这些都比仅仅通过短路评估建议的最小测试更快。

除了最热门的热点之外,这种优化水平不太可能产生有价值的差异。 假设它(在特定情况下没有certificate)是一种猜测forms,并且优化的第一条规则是不作出猜测