你知道什么技术来避免条件分支？ [英] What techniques to avoid conditional branching do you know?

问题描述

有时一个循环，在CPU花费的大部分时间有一些分支prediction小姐（MIS prediction）经常（接近0.5的概率）。我已经看到了非常孤立的线程，但一些技巧从来没有一个列表。我所知道的那些已经固定在那里的条件下可以变成一个布尔情况和0/1以某种方式改变使用。是否有可避免其他条件分支？

Sometimes a loop where the CPU spends most of the time has some branch prediction miss (misprediction) very often (near .5 probability.) I've seen a few techniques on very isolated threads but never a list. The ones I know already fix situations where the condition can be turned to a bool and that 0/1 is used in some way to change. Are there other conditional branches that can be avoided?

例如。 （伪code）

e.g. (pseudocode)

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

可以重写，可以说失去一些可读性，像这样的东西：

Can be rewritten, arguably losing some readability, with something like this:

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

＆安培;

此外，我已经看到了在野外技术改变＆放到＆安培; 在有条件的某些情况下，现在逃避我的脑海里。我在这个级别的优化的新秀，但它肯定感觉就像我们有了更多。

Also I've seen techniques in the wild changing && to & in the conditional in certain contexts escaping my mind right now. I'm a rookie at this level of optimization but it sure feels like there's got to be more.

推荐答案

我相信，以避免分支最常见的方式是利用位并行在降低总跳跃present在code。该基本块的时间越长，常少流水线刷新

I believe the most common way to avoid branching is to leverage bit parallelism in reducing the total jumps present in your code. The longer the basic blocks, the less often the pipeline is flushed.

由于别人已经提到的，如果你想要做的比展开循环，并提供分支提示多了，你会想拖放到装配。当然，这应该以最大的谨慎进行：典型的编译器可以在大多数情况下比人类写更好的装配。你最希望的是剃掉粗糙的边缘，并假设编译器无法推断。

As someone else has mentioned, if you want to do more than unrolling loops, and providing branch hints, you're going to want to drop into assembly. Of course this should be done with utmost caution: your typical compiler can write better assembly in most cases than a human. Your best hope is to shave off rough edges, and make assumptions that the compiler cannot deduce.

下面的下面的C code的例子：

Here's an example of the following C code:

if (b > a) b = a;

在组装没有任何跳跃，用位操作（和极端评论）

In assembly without any jumps, by using bit-manipulation (and extreme commenting):

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 code到相应的条件移动指令，你只是在做编译器的工作。

Note that while conditional moves are immediately jumped on by assembly enthusiasts, that's only because they're easily understood and provide a higher level language concept in a convenient single instruction. They are not necessarily faster, not available on older processors, and by mapping your C code into corresponding conditional move instructions you're just doing the work of the compiler.

这篇关于你知道什么技术来避免条件分支？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！