9

我正在尝试优化一个小型、高度使用的函数,它使用 unsigned 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 的乘法。

哪个代码运行得更快?

4

12 回答 12

13

哪个代码运行得更快?

测试一下就知道了。

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

于 2009-02-05T05:10:06.460 回答
9

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

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

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

于 2009-02-05T05:15:29.240 回答
8

您可以在没有乘法的情况下使其无分支。看起来对于每个位集,您都使用该位位置作为数组的索引。

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

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

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

一些平台还具有获取位集的位索引的内在特性,这可能更快。x86 有bsr,PPC 有cntlz

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

于 2009-02-05T05:19:15.737 回答
4

这次改版怎么样?

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

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


这说明了为什么测量很重要。我正在使用过时的 Sun SPARC。如图所示,我编写了一个测试程序,问题中的两个竞争者作为测试 0 和测试 1,我自己的答案作为测试 2。然后运行计时测试。“总和”被打印为完整性检查 - 以确保算法都给出相同的答案。

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.htimer.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)));
    }
}

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

于 2009-02-05T06:15:16.873 回答
3

完全取决于编译器、机器指令集,可能还取决于月相。

因此,没有具体的正确答案。如果您真的想知道,请检查编译器的程序集输出。

从简单的角度来看,我会说第二个比较慢,因为它涉及第一个加上乘法的所有计算。但是编译器可能足够聪明,可以优化掉它。

所以正确的答案是:视情况而定。

于 2009-02-05T05:06:47.400 回答
1

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

当然,唯一确定的方法是双向计算一些时间。

于 2009-02-05T05:07:00.193 回答
1

答案肯定是:在目标硬件上试试看。并且一定要遵循过去几周在 SO 上发布的大量微基准/秒表基准问题的建议。

链接到一个基准测试问题:秒表基准测试是否可以接受?

就个人而言,我会选择 if,除非有一个真正令人信服的理由来使用“混淆”替代方案。

于 2009-02-05T05:07:21.767 回答
1

确定陈述的真实性的唯一真正方法是测试。考虑到这一点,我同意以前的帖子说试试看!

在大多数现代处理器上,分支是一个代价高昂的过程,尤其是很少采用的分支。这是因为必须刷新流水线,导致 CPU 实际上无法尝试同时执行一条或多条指令——仅仅是因为它不知道下一条指令来自何处。有了几个分支,可能的控制流变得复杂,CPU 需要同时尝试所有可能性,因此它必须执行分支,然后在此之后立即开始执行许多指令。

于 2009-02-05T06:11:53.340 回答
1

为什么不这样做(假设 i 是 32 位)

  for (i2 = i; i2; i2 = i3) {
    i3 = i2 & (i2-1);
    last_bit = i2-i3;
    a = last_bit & 0xffff;
    b = (last_bit << 16);
    j = place[a] + big_place[b];
    total += value[j];
  }

其中 place 是大小为 2^15+1 的表,其中 place[0] = 0,place[1] = 1,place[2] = 2,place[4] = 3,place[8] = 4.. .place[15] = 16(其余值无关紧要)。和 big_place 几乎相同:big_place[0] = 0,big_place[1] = 17.... big_place[15] = 32。

于 2009-02-05T06:16:25.437 回答
1

尝试

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我认为没有限定符的测试会更现实。

于 2009-02-05T06:18:42.530 回答
1

要超快,您可以避免循环、移位和乘法 - 使用 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 位,并进行多次查找,每次移动掩码。性能会受到一点影响,但代码会小得多。

于 2009-02-05T07:41:09.213 回答
1

明显的解决方案:

int total = 0;
for(unsigned j = 0; j < 16; j++){
    total += -(i>>j & 1) & value[j];
}
于 2011-02-10T11:10:17.433 回答