使用按位运算符消除分支 [英] Branching elimination using bitwise operators

问题描述

我有一个运行的大约2 ^ 26次循环中一些关键的分支code。科prediction不是最优的，因为 M 是随机的。我如何将消除分歧，可能使用位运算符？

I have some critical branching code inside a loop that's run about 2^26 times. Branch prediction is not optimal because m is random. How would I remove the branching, possibly using bitwise operators?

bool m;
unsigned int a;
const unsigned int k = ...; // k >= 7
if(a == 0)
    a = (m ? (a+1) : (k));
else if(a == k)
    a = (m ?     0 : (a-1));
else
    a = (m ? (a+1) : (a-1));

这里是所产生的相关组件的gcc -O3 ：

.cfi_startproc
movl    4(%esp), %edx
movb    8(%esp), %cl
movl    (%edx), %eax
testl   %eax, %eax
jne L15
cmpb    $1, %cl
sbbl    %eax, %eax
andl    $638, %eax
incl    %eax
movl    %eax, (%edx)
ret
L15:
cmpl    $639, %eax
je  L23
testb   %cl, %cl
jne L24
decl    %eax
movl    %eax, (%edx)
ret
L23:
cmpb    $1, %cl
sbbl    %eax, %eax
andl    $638, %eax
movl    %eax, (%edx)
ret
L24:
incl    %eax
movl    %eax, (%edx)
ret
.cfi_endproc

推荐答案

的无分支无划分模的可能的是有益的，但​​试验表明，在实践中，它是不

The branch-free division-free modulo could have been useful, but testing shows that in practice, it isn't.

const unsigned int k = 639;
void f(bool m, unsigned int &a)
{
    a += m * 2 - 1;
    if (a == -1u)
        a = k;
    else if (a == k + 1)
        a = 0;
}

测试用例：

unsigned a = 0;
f(false, a);
assert(a == 639);
f(false, a);
assert(a == 638);
f(true, a);
assert(a == 639);
f(true, a);
assert(a == 0);
f(true, a);
assert(a == 1);
f(false, a);
assert(a == 0);

其实这个时机，用一个测试程序：

Actually timing this, using a test program:

int main()
{
    for (int i = 0; i != 10000; i++)
    {
        unsigned int a = k / 2;
        while (a != 0) f(rand() & 1, a);
    }
}

（注：没有函数srand ，所以结果是确定的。）

(Note: there's no srand, so results are deterministic.)

我原来的答复：5.3s

My original answer: 5.3s

在code的问题：4.8s

The code in the question: 4.8s

查找表：4.5S（静态无符号查找[2] [K + 1]; ）

查找表：4.3s（静态无符号查找[K + 1] [2]; ）

Eric的回答是：4.2s

Eric's answer: 4.2s

该版本：4.0s

这篇关于使用按位运算符消除分支的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！