使用按位运算符进行分支消除

Question

我在循环中有一些关键的分支代码,运行大约2 ^ 26次.分支预测不是最优的,因为m是随机的.如何删除分支,可能使用按位运算符？

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

Answer 1

无分支无除模可能很有用，但测试表明实际上并非如此。

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);

实际上，使用测试程序对此进行计时：

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

（注意：没有srand，因此结果是确定性的。）

我原来的答案：5.3s

问题中的代码：4.8s

查表：4.5s ( static unsigned lookup[2][k+1];)

查表：4.3s ( static unsigned lookup[k+1][2];)

艾里克的答案：4.2秒

本版本：4.0s