Aeq*_*tas 22 java performance branch-prediction
与此答案相关:https://stackoverflow.com/a/11227902/4714970
在上面的答案中,提到了如何通过避免分支来避免分支预测失败.
用户通过替换以下内容来演示:
if (data[c] >= 128)
{
sum += data[c];
}
附:
int t = (data[c] - 128) >> 31;
sum += ~t & data[c];
这两个是如何等效的(对于特定的数据集,不是严格等同的)？
在类似的情况下,我可以采取哪些一般方法来做类似的事情？它总是通过使用>>和~？
Lou*_*man 27
int t = (data[c] - 128) >> 31;
这里的诀窍是,如果data[c] >= 128,那么data[c] - 128是非负的,否则它是负的.int当且仅当该数字为负时,符号位中的最高位为1. >>是一个扩展符号位的移位,因此右移31会使整个结果为0(如果它曾经是非负的),并且所有1位(表示-1)(如果它曾经是负数).所以t是0如果data[c] >= 128,和-1其他. ~t切换这些可能性,如果~t是,以及否则.-1data[c] >= 1280
x & (-1)总是等于x,并且x & 0总是等于0.因此,通过if 和其他方式sum += ~t & data[c]增加.sum0data[c] < 128data[c]
其中许多技巧可以应用于其他地方.当然0并且只有当一个值大于或等于另一个值时,这个技巧当然可以应用于一个数字,-1否则,你可以更多地使用它来获取<=,<等等.这样的比特是一种使数学运算无分支的常用方法,尽管它肯定不会总是用相同的操作构建; ^(xor)和|(或)有时也会发挥作用.
apa*_*gin 16
虽然Louis Wasserman的回答是正确的,但我想向您展示一种更通用(更清晰)的方法来编写无分支代码.你可以使用? :运算符:
int t = data[c];
sum += (t >= 128 ? t : 0);
JIT编译器从执行配置文件中看到这里的条件预测不佳.在这种情况下,编译器足够聪明,可以用条件移动指令替换条件分支:
mov 0x10(%r14,%rbp,4),%r9d ; load R9d from array
cmp $0x80,%r9d ; compare with 128
cmovl %r8d,%r9d ; if less, move R8d (which is 0) to R9d
您可以验证此版本对已排序和未排序的数组的运行速度同样快.
无分支代码通常意味着使用集合[0,1]中的权重来评估条件语句的所有可能结果,以便Sum {weight_i} = 1.大多数计算基本上被丢弃.某些优化可能是由于E_i当相应的权重w_i(或掩码m_i)为零时不必正确的事实.
result = (w_0 * E_0) + (w_1 * E_1) + ... + (w_n * E_n) ;; or
result = (m_0 & E_0) | (m_1 & E_1) | ... | (m_n * E_n)
其中m_i代表位掩码.
通过水平折叠并行处理E_i也可以实现速度.
这与语义if (a) b; else c;或它的三元速记相矛盾a ? b : c,其中只评估了[b,c]中的一个表达式.
因此,三元运算对于无分支代码来说不是神奇的子弹.一个体面的编译器同样产生无分支代码
t = data[n];
if (t >= 128) sum+=t;
与
movl -4(%rdi,%rdx), %ecx
leal (%rax,%rcx), %esi
addl $-128, %ecx
cmovge %esi, %eax
无分支代码的变化包括通过其他无分支非线性函数(例如ABS)呈现问题(如果存在于目标机器中).
例如
2 * min(a,b) = a + b - ABS(a - b),
2 * max(a,b) = a + b + ABS(a - b)
甚至:
ABS(x) = sqrt(x*x) ;; caveat -- this is "probably" not efficient
除了<<和之外~,使用bool和!bool代替(可能是未定义的)(int >> 31)也同样有益.同样,如果条件的计算结果为[0,1],则可以生成带有否定的工作掩码:
-[0, 1] = [0, 0xffffffff] in 2's complement representation