尝试
total += (-((i & mask) != 0)) & value[j];
代替
total += ((i & mask) != 0) * value[j];
这避免了乘法。是否会有分支取决于编译器是否足够聪明,可以为 -(foo != 0) 找到无分支代码。(这是可能的,但我会有点惊讶。)
(当然,这取决于二进制补码表示;C 标准对此是不可知的。)
您可能会像这样帮助编译器,假设 32 位整数并且有符号 >> 传播符号位:
total += (((int)((i & mask) << (31 - j))) >> 31) & value[j];
也就是说,在上述实现定义的假设下,将可能设置的位向左移动到最高有效位置,转换为有符号整数,然后一直向右移动到最低有效位置,产生全 0 或全 1 . (我没有测试过这个。)
另一种可能性:一次考虑(比如说)4位的块。有16种不同的加法序列;您可以为它们中的每一个分派到展开的代码,而在每个代码块中根本不需要测试。这里的希望是一次间接跳转的成本低于 4 个测试和分支。
更新:使用 Jonathan Leffler 的脚手架,每次 4 位的方法在我的 MacBook 上是最快的。否定和结果与乘法大致相同。我想知道处理器是否会更快地将 0 和 1 之类的特殊情况相乘(或者如果对于大多数位清除或大多数位设置的被乘数来说通常更快,则不是这种特殊情况)。
我没有编写可接受的答案,因为它在这个特定的基准测试中不太可能是最快的(它应该从仅枚举集合位中获得最大的好处,在稀疏集合上做得最好,但完全有一半的位设置在这个基准)。以下是我对 Leffler 代码的更改,以防其他人有奇怪的动机花时间在这上面:
#include <stdio.h>
#include <time.h>
static int value[] =
{
12, 36, 79, 21, 31, 93, 24, 15,
56, 63, 20, 47, 62, 88, 9, 36,
};
static int test_1(int i)
{
int total = 0;
for (unsigned short mask = 0x0001, j = 0; mask != 0; mask <<= 1, j++)
{
if (i & mask)
total += value[j];
}
return(total);
}
static int test_2(int i)
{
int total = 0;
for (unsigned short mask = 0x0001, j = 0; mask != 0; mask <<= 1, j++)
{
total += ((i & mask) != 0) * value[j];
}
return(total);
}
static int test_3(int i)
{
int total = 0;
for (unsigned mask = i & 0xFFFF, j = 0; mask != 0; mask >>= 1, j++)
{
total += (mask & 0x0001) * value[j];
}
return(total);
}
static int test_4(int i)
{
int total = 0;
for (unsigned mask = i & 0xFFFF, j = 0; mask != 0; mask >>= 1, j++)
{
total += -(mask & 0x0001) & value[j];
}
return(total);
}
static int test_5(int i)
{
int total = 0;
const int *p = value;
for (unsigned mask = i & 0xFFFF; mask != 0; mask >>= 4, p += 4)
{
switch (mask & 0xF)
{
case 0x0: break;
case 0x1: total += p[0]; break;
case 0x2: total += p[1]; break;
case 0x3: total += p[1] + p[0]; break;
case 0x4: total += p[2]; break;
case 0x5: total += p[2] + p[0]; break;
case 0x6: total += p[2] + p[1]; break;
case 0x7: total += p[2] + p[1] + p[0]; break;
case 0x8: total += p[3]; break;
case 0x9: total += p[3] + p[0]; break;
case 0xA: total += p[3] + p[1]; break;
case 0xB: total += p[3] + p[1] + p[0]; break;
case 0xC: total += p[3] + p[2]; break;
case 0xD: total += p[3] + p[2] + p[0]; break;
case 0xE: total += p[3] + p[2] + p[1]; break;
case 0xF: total += p[3] + p[2] + p[1] + p[0]; break;
}
}
return(total);
}
typedef int(*func_pointer)(int);
static func_pointer test[] = { test_1, test_2, test_3, test_4, test_5 };
#define DIM(x)(sizeof(x)/sizeof(*(x)))
int main()
{
int i, j, k;
for (i = 0; i < DIM(test); i++)
{
long sum = 0;
clock_t start = clock();
for (j = 0; j <= 0xFFFF; j += 13)
{
int rv;
for (k = 0; k < 1000; k++)
rv = (*test[i])(j);
sum += rv;
}
clock_t stop = clock();
printf("(sum = %ld) Test %d: %8.6f s\n", sum, i + 1,
(stop - start) / (1.0 * CLOCKS_PER_SEC));
}
}
结果(gcc -O4 -std=c99 branchmult2.c
):
(sum = 1744366) Test 1: 0.225497 s
(sum = 1744366) Test 2: 0.221127 s
(sum = 1744366) Test 3: 0.126301 s
(sum = 1744366) Test 4: 0.124750 s
(sum = 1744366) Test 5: 0.064877 s
编辑 2:volatile
我认为没有限定符的测试会更现实。