分支还是乘法更有效率？

Question

我正在尝试优化一个小而高效的函数，该函数使用无符号短整型中的高位来指示要相加的数组的值。起初，我使用了下面显示的明显方法。请注意，循环展开没有明确显示，因为它应该由编译器执行。

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的乘法运算，并且还需要完成其余等式的计算。

哪个代码将运行得更快？

- Nixuz

---

如果编译器正常，它们应该编译成相同的东西。我会选择更易读的第一个选项。你的平台支持谓词执行吗？在这里它会很好用，因为只有一个指令需要谓词（加法），所以在这种情况下你不需要真正的分支。 - Matt J

需要注意的是：您可以用 !!(i & mask) 代替 ((i & mask) != 0)。 "!!" 是对 ! 运算符的滥用，通过两次应用它来创建一个“转换为bool”运算符。这不应该改变生成的汇编代码，但这是一种常见的习惯用法，并且对我来说更可读。 - kquinn

提醒一下，((i & mask) != 0) 可能不具有可移植性...... false 表示 0，true 表示非 0.... - Calyth

Answer 1

哪个代码会更快运行？

测试一下就知道了。

此外，查看编译器生成的汇编语言版本的代码，因为您可能会在其中看到令您惊讶的东西，并提示进一步的优化（例如，使用您正在使用的short可能需要更多指令来使用机器的自然整数大小）。

- ChrisW

Answer 2

两者都可能更快。对于某些处理器，实际输入数据可能会影响答案。您需要使用真实数据对两种方法进行性能测试。以下是一些可能影响x86硬件实际性能的因素。

假设你正在使用一款新型的 Pentium 4 处理器。该处理器在 CPU 中具有两级分支预测器。如果分支预测器能够正确地猜测分支方向，我认为第一种方法将会更快。这最有可能发生在标志几乎全是相同值或者在大多数情况下交替出现的非常简单的模式中。如果标志是真正随机的，则分支预测器错误的概率为一半。对于我们的假想32级 Pentium 4 来说，这将严重影响性能。对于 Pentium 3 芯片、Core 2 芯片、Core i7 和大多数 AMD 芯片，流水线较短，因此坏分支预测成本要低得多。

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

- Mr Fooz

Answer 3

您可以在不使用乘法的情况下使其成为无分支代码。看起来，对于每个设置的位，您都将该位位置用作数组中的索引。

首先，您可以轻松提取设置的位：

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

然后，您可以通过计算 (set_mask - 1) 中设置的位数来获取位索引。对于此操作，有一个常量时间公式。

一些平台还具有获取设置位的位索引的内在函数，这可能更快。x86具有 bsr，PPC具有 cntlz。

因此，无分支且不乘的版本可能最快 :)

- MSN

---

非常有趣，但我在想这个“常数时间公式”是否值得，您能提供一些关于这个公式的详细信息吗？ - Nixuz

谢谢，这是一个非常优雅的解决方案。 - Nixuz

这个解决方案实现了：unsigned int total = 0 while (i){ total += value[countBits((i & -i) - 1)]; i &= (i - 1); } - Nixuz

GCC有__builtin_popcount(x)函数，它返回x中设置位的数量。 - ephemient

不要计算“mask”中的位数；甚至创建“mask”本身就是一个错误。请参见我的答案。 - R.. GitHub STOP HELPING ICE

@R.，是的，您也可以生成一个~0或0掩码，具体取决于位是否设置。但是区别在于我的解决方案是O（位集），这是可变的，而生成选择器掩码是O（整数大小）。如果有人能够将您的答案标记为好答案，我也会建议这样做。 - MSN

Answer 4

这个版本怎么样？

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

我已将mask复制为i的副本，限制在16位无符号范围内，但代码检查mask的最后一位是否设置，如果设置，则将数组值乘以该位。这应该会更快，因为每次迭代的操作较少，只需要主循环分支和条件。此外，如果i开始时较小，循环可以提前退出。

---

这说明了为什么测量很重要。我正在使用过时的Sun SPARC。我编写了一个测试程序，如所示，采用来自问题的两个竞争者作为测试0和测试1，以及我的答案作为测试2。然后运行定时测试。打印“sum”是为了进行合理性检查-确保算法都给出相同的答案。

64位未优化：

gcc -m64 -std=c99 -I$HOME/inc -o x x.c -L$HOME/lib/sparcv9 -ljl -lposix4

Test 0: (sum = 1744366)  7.973411 us
Test 1: (sum = 1744366) 10.269095 us
Test 2: (sum = 1744366)  7.475852 us

很好：我的比原版略快，而升级版则更慢。

64位优化：

gcc -O4 -m64 -std=c99 -I$HOME/inc -o x x.c -L$HOME/lib/sparcv9 -ljl -lposix4

Test 0: (sum = 1744366)  1.101703 us
Test 1: (sum = 1744366)  1.915972 us
Test 2: (sum = 1744366)  2.575318 us

糟糕 - 我的版本现在变得极其缓慢。优化程序非常好！

32位优化：

gcc -O4 -std=c99 -I$HOME/inc -o x x.c -L$HOME/lib -ljl -lposix4

Test 0: (sum = 1744366)  0.839278 us
Test 1: (sum = 1744366)  1.905009 us
Test 2: (sum = 1744366)  2.448998 us

32位未优化：

gcc -std=c99 -I$HOME/inc -o x x.c -L$HOME/lib -ljl -lposix4

Test 0: (sum = 1744366)  7.493672 us
Test 1: (sum = 1744366)  9.610240 us
Test 2: (sum = 1744366)  6.838929 us

相同的代码在（32位）Cygwin和不那么老旧的笔记本电脑上（32位，经过优化）运行

Test 0: (sum = 1744366)  0.557000 us
Test 1: (sum = 1744366)  0.553000 us
Test 2: (sum = 1744366)  0.403000 us

现在我的代码是最快的。这就是为什么你要进行测量！这也说明了为什么专门进行基准测试的人会感到沮丧。

测试工具（如果需要，可以提供timer.h和timer.c代码）：

#include <stdio.h>
#include "timer.h"

static volatile 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);
}

typedef int(*func_pointer)(int);

static func_pointer test[] = { test_1, test_2, test_3 };

#define DIM(x)(sizeof(x)/sizeof(*(x)))

int main()
{
    int i, j, k;
    char buffer[32];
    for (i = 0; i < DIM(test); i++)
    {
        Clock t;
        long sum = 0;
        clk_init(&t);
        clk_start(&t);
        for (j = 0; j < 0xFFFF; j += 13)
        {
            int rv;

            for (k = 0; k < 1000; k++)
                rv = (*test[i])(j);
            sum += rv;
        }
        clk_stop(&t);
        printf("Test %d: (sum = %ld) %9s us\n", i, sum,
               clk_elapsed_us(&t, buffer, sizeof(buffer)));
    }
}

我还没有花时间弄清楚为什么我的代码在优化后变得更慢。

- Jonathan Leffler

---

我尝试了一个test_4()，它与test_3()相似，但是total += -(mask & 1) & value[j]。在MacBook上，在-O4下，4比3稍微慢一些，未经优化时略快。浏览反汇编代码显示实际进行了乘法和按位与操作，所以我感到惊讶：MUL比NEG和AND更快！很酷。 - Darius Bacon

顺便提一下，我会在内部循环中使用 j <= 0xFFFF，而不是 <（并不重要）。此外，我不得不将其更改为使用 clock.h。感谢你的修改 - 我太懒了。 - Darius Bacon

嗯，来自 time.h 的 clock()。 - Darius Bacon

由于我不能满足于现状，我也尝试了我的按4位一组的建议，结果只用了test_3() 53% 的时间。 - Darius Bacon

Answer 5

这完全取决于编译器、机器指令集，以及可能的月相。因此，没有明确的正确答案。如果你真的想知道，可以检查编译器生成的汇编输出。从简单的角度来看，我会说第二种方法比较慢，因为它需要进行第一步所有计算加上乘法运算。但是编译器可能足够聪明，可以将其优化掉。因此，正确答案是：这取决于具体情况。

- Pax

---

+1。此外，展开循环几乎肯定比玩弄分支与乘法来提高性能更有效。 - Zooba

除了我通过卷起循环来提高性能的时间（该函数占用了运行时间的80％，因此我迫切需要优化），传统的优化智慧已经过时需要进行彻底改革。 - David Thornley

Answer 6

明显的解决方案：

int total = 0;
for(unsigned j = 0; j < 16; j++){
    total += -(i>>j & 1) & value[j];
}

- R.. GitHub STOP HELPING ICE

Answer 7

尽管第二个示例没有显式的分支，但可能存在一个隐式分支来将比较结果转换为布尔值。您可以通过打开编译器的汇编列表输出并查看它来获得一些见解。

当然，确切了解需要两种方法都进行时间测试。

- Mark Ransom

---

是的，我认为你是正确的，存在隐式分支。谢谢你指出来。 - Nixuz

这取决于架构 - 在x86上，int-to-bool可以使用两个指令'cmp'和'setne'无需分支来完成。 - Adam Rosenfield

Answer 8

答案肯定是：在目标硬件上尝试并查看结果。一定要遵循最近几周在SO上发布的大量微基准/秒表基准问题的建议。

一个基准测试问题的链接：秒表基准测试是否可接受？ 个人而言，我会选择if，除非有非常充分的理由使用“混淆”的替代方案。

- Software Monkey

Answer 9

唯一确定陈述的真相的方法是测试。考虑到这一点，我同意之前的帖子中所说的尝试一下！

在大多数现代处理器上，分支是一个昂贵的过程，特别是不经常采取分支。这是因为流水线必须被清除，导致CPU实际上无法尝试同时执行一个或多个指令 - 简单地因为它不知道下一条指令将从哪里来。对于几个分支，可能的控制流变得太复杂，以至于CPU无法同时尝试所有可能性，因此必须进行分支，然后在此之后开始同时执行许多指令。

- mP

Answer 10

为了达到极致的速度，您可以避免使用循环、移位和乘法 - 使用 switch。

switch (i) {
    case 0: break;
    case 1: total = value[0]; break;
    case 2: total = value[1]; break;
    case 3: total = value[1] + value[0]; break;
    case 4: total = value[2]; break;
    case 5: total = value[2] + value[0]; break;
    ...
}

虽然需要输入很多，但我猜在运行时会更快。查找表的性能是无法超越的！

我宁愿编写一个小的Perl脚本来为我生成这段代码 - 只是为了避免打字错误。

如果你认为这有点极端，你可以使用较小的表 - 4位，多次查找并每次移动掩码。性能会稍微受到影响，但代码会小得多。

- qrdl

---

直到 switch 语句变得太大以至于超出代码缓存行，从而性能受到影响。 - David Thornley

在这种情况下，您可以使用较小的查找表（如我所提到的），并进行多次查找。 - qrdl

代码可能更快，但由于这个版本占用了更多的高速缓存，附近的代码可能会变得更慢。 :-) - Darron