通过按位选择删除分支

Question

我被告知代码中的分支

int value = //some number;
if(value > some_other_value)
   value *= 23;
else
   value -= 5; 

可以通过按位掩码消除(以便对代码启用SIMD优化)：

const int Mask = (some_other_value-value)>>31;
value =      ((value * 23)&Mask)|((value-5)&~Mask);

然而，我不明白这是如何工作的(即使我知道这里使用的是什么操作，以及结果在二进制中看起来是什么样子)。此外，这有多普遍适用？如果原来的代码是这样的呢？

if(value & 1 == 1)
   value *= 23;
else
   value -= 5;

删除分支的代码还会是一样的吗？否则，遮罩的用途是什么，我应该如何开始创建它？这是怎么回事？

Answer 1

这是可行的：

const int Mask = (some_other_value-value)>>31;
value =      ((value * 23)&Mask)|((value-5)&~Mask);

Mask成为some_other_value - value的符号位-类似于：

if (value > some_other_value) mask = -1; else mask = 0; 

你可以用你的第二个例子来实现同样的事情，使用：

mask = -(value & 1);

所以，-0 = 0，-1 =全1。

编辑:我也会记住，如果计算变得太复杂，你不会从分支版本中获得任何东西，特别是如果分支是合理可预测的。

Answer 2

在最好的情况下，这是过早的优化，在最坏的情况下，这是反优化。

如果代码可以矢量化，它无论如何都会使用条件移动，因为SIMD不知道其他任何事情。

但是，即使对于标量代码，现代编译器通常也会生成条件移动，所以没有分支(除非编译器认为计算这两个等式的代价足够高，所以分支更有效)。

条件移动一直是RISC处理器(例如ARM)上的标准功能，甚至在x86上也支持了17年。在现代处理器上，条件移动将占用与正常移动完全相同的周期，或者最多额外占用2-3个周期。

这显然假设条件已经足够早地进行了评估(尽管如果不存在对值的依赖关系并不重要，因为无序执行会隐藏它)，但这也适用于您所应用的任何一种隐蔽的优化技巧。你只是不能使用一个还不存在的结果。

如果可以的话，在第一眼看到时，总是写一些容易理解的代码，而不是一些模糊的代码

value = (((foo<<31)&bar, ++baz) -= (foo & 7121)) + PHASE_OF_MOON;

这种东西不仅不会更快，也可能更慢，而且会让审查你的代码的人感到困惑(包括你自己，从现在开始的6-10个月！)，它是高度不可移植的，而且很可能在你意想不到的情况下产生不正确的结果。