分支或乘法更有效吗？

我正在尝试优化一个小的,高度使用的函数,该函数使用无符号short int中的高位来指示要一起求和的数组值.起初我使用下面显示的明显方法.请注意,循环展开未明确显示,因为它应由编译器完成.

int total = 0;
for(unsigned short mask = 0x0001, j = 0; mask != 0; mask <<= 1, j++){
    if (i & mask){
        total += value[j];
    }
}

但是,后来我认为删除分支以帮助CPU流水线操作可能会更好,并提出以下建议.

int total = 0;
for(unsigned short mask = 0x0001, j = 0; mask != 0; mask <<= 1, j++){
    total += ((i & mask) != 0) * value[j];
}

请注意,由于(i&mask)不会产生布尔答案,因此与0的比较会强制结果为1或0.虽然第二种方法从代码的这一部分中删除了if语句,但第二种解决方案需要除了等式的其余部分之外,在每次迭代时运行0或1的乘法.

哪个代码运行得更快？

哪个代码运行得更快？

测试它找出来.

另外,请查看编译器发出的代码的汇编语言版本,因为您可能会看到其中的内容让您感到惊讶,并提示进一步优化(例如,short在使用时使用可能需要更多使用的指令)机器的自然整数大小).

两者都可能更快.对于某些处理器,实际输入数据可能会改变答案.您需要使用实际数据来分析这两种方法.以下是一些可能影响x86硬件实际性能的因素.

让我们假设您正在使用最新型号的Pentium 4.该处理器在CPU中有两级分支预测器.如果分支预测器可以正确猜出分支方向,我怀疑第一个将是最快的.如果标志几乎都是相同的值,或者如果它们在大多数时间以非常简单的模式交替,则最有可能发生这种情况.如果标志是真正随机的,那么分支预测器将在一半时间内出错.对于我们假设的32阶段奔腾4,这将扼杀性能.对于Pentium 3芯片,Core 2芯片,Core i7和大多数AMD芯片,管道更短,因此坏分支预测的成本要低得多.

如果您的值向量明显大于处理器的缓存,则任何一种方法都将受到内存带宽的限制.它们都具有基本相同的性能特征.如果值向量适合缓存,请注意如何进行任何分析,以便其中一个测试循环不会因填充缓存而受到惩罚而另一个从中受益.

如果没有乘法,你可以使它无分支.看起来对于每个位集,您使用该位位置作为数组的索引.

首先,您可以轻松提取设置的位:

unsigned short set_mask= i & -i;
i&= i - 1;

然后,您可以通过计算设置的位来获取位索引(set_mask - 1).这是一个恒定的时间公式.

某些平台也有一个内在函数来获取位集的位索引,这可能更快.x86有bsr,PPC有cntlz.

所以答案是无分支无乘版本可能是最快的:)