它是更有效的分支或繁殖？

StackOverflow https://stackoverflow.com/questions/514637

题

我试图优化其使用高比特在无符号短整数来指示数组的值求和在一起的小的，高度使用的功能。起初我是用如下的明显的方法。请注意，循环展开没有明确地显示，因为它应该由编译器来完成。

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＆掩模）不在布尔答案导致，其中0力的结果的比较是1或0。虽然这第二种方法从代码的这一部分消除了if语句，则第二解决方案需要在除了方程的其余部分在每个迭代上运行的0或1的乘法。

哪个代码将运行得更快？

有帮助吗？

解决方案

您可以使它网点没有一个乘法。它看起来像您使用的位位置的一个索引的阵列，每个位集合。

首先，可以很容易地提取与设定的位：

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

然后，可以通过计数在(set_mask - 1)设置的位得到位索引。有一个恒定的时间公式此。

一些平台也具有内在变得有点一套大概是更快的位索引。 86具有bsr，PPC具有cntlz。

所以答案是网点multiplyless版本可能是最快的：）

其他提示

  

哪个代码将运行得更快？

测试它找出。

另外，看看它的编译器生成的代码的汇编语言版本，因为你可能会看到令你感到惊讶于它的东西，并在进一步的优化提示（例如，使用short与您使用可以根据需要在使用机器的自然整数大小以上指令）。

要么可能会更快。对于一些处理器，实际输入的数据可能会改变答案。你需要用真实的数据这两种方法的轮廓。这里有一些事情，可以影响在x86硬件的实际性能。

让我们假设对于您使用的是最新型号的Pentium 4，该处理器具有分支预测器的两级烘焙到CPU的时刻。如果分支预测器能够正确地猜出分支方向，我怀疑是第一个将是最快的。这是最有可能的，如果标志几乎都是相同的值出现，或者如果他们在一个非常简单的模式大部分时间交替。如果标志是真正随机的，那么分支预测器将是错误的一半的时间。对于我们假设32级的Pentium 4，这会杀了性能。奔腾3芯片，核心2芯片，酷睿i7，最AMD芯片，管道较短，所以不好分支预测的成本要低得多。

如果您的值向量是明显比处理器的高速缓存越大，则两种方法将被存储器带宽的限制。他们俩都具有大致相同的性能特性。如果该值向量缓存舒适适合，小心你怎么做任何分析，以便测试循环之一是没有得到惩罚从它填充缓存，另一个好处。

这个版本是什么？

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

我已完成mask成i限于16位无符号范围的副本，但代码检查是否掩码的最后位被设置，由该比特的阵列值乘以。这应该是更快的，只是因为有每次迭代更少的操作，并且只需要在主回路分支和条件。另外，环可以提前退出如果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.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)));
    }
}

我没有花时间的工作，为什么优化时，我的代码比较慢。

这取决于的完全在编译器，机器指令集和，可能的是，月相。

有就是因为这个没有具体的正确答案。如果你真的想知道，检查从编译器输出的程序集。

从一个简单的点，我会说，第二个是较慢的，因为它涉及的第一的加乘法的所有计算。但是，编译器可能是足够聪明来优化了。

所以，正确的答案是：这取决于

虽然第二示例不具有明确的分支，也可能是隐式的一个于所述比较的布尔的结果进行转换。你可能会通过打开汇编列表输出你的编译器，并看着那得到一点点的见解。

当然，肯定知道的唯一途径是采取一些计时两种方式。

，以确定发言的真相的唯一途径是测试。考虑到这一点，我会与以前的职位，说试试吧同意！

在大多数现代处理器的分支是一个昂贵的过程尤其分支很少采取。这是因为管道必须冲洗造成的CPU在效果不能够尝试同时执行一个或多个指令 - 仅仅是因为它不知道下一个指令将从何而来。通过几个分支可能的控制流程变得复杂的CPU同时尝试所有的可能性，因此必须做的，因此该分支，然后开始之后做一次许多指令。

为什么不能做到这一点（假设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];
  }

其中地方是大小的表2 ^ 15 + 1，使得 放置[0] = 0，代替[1] = 1，代替[2] = 2，代替[4] = 3，代替[8] = 4 ...去处[15] =值别”的16（其余牛逼事）。和big_place几乎是相同的： big_place [0] = 0，big_place [1] = 17 .... big_place [15] = 32。

要被uberfast可以避开环，移位和乘法 - 使用开关

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位，并且进行查找几次，每次移动掩模。性能将受到了一点，但代码会小很多。

答案肯定是：尝试在目标硬件上看看。而且一定要遵循的微基准/秒表基准的问题在这里张贴在SO过去几周在众人的意见。

链接到一个基准的问题：是秒表基准可接受

就个人而言，我会一起去的，如果，除非有一个非常令人信服的理由来使用“模糊”的选择。

尝试

total += (-((i & mask) != 0)) & value[j];

代替

total += ((i & mask) != 0) * value[j];

这避免了乘法。是否会有分支或不可达的编译器是否足够聪明找到免费的分支代码 - （！富= 0）。 （这是可能的，但我会有些意外。）

（当然，这取决于二进制补码表示; C标准是对不可知）

您可以帮忙编译器像这样，假设32位整数，并签署>>传播符号位：

total += (((int)((i & mask) << (31 - j))) >> 31) & value[j];

也就是说，移位可能集位左到最-显著位置，铸造成符号int，则右一路回到最小显著位置，得到全部为0或全部为1，在上述实施下-defined假设。 （I没有测试此。）

另一种可能性：在一个时间考虑的（比方说）4位的数据块。有16个不同的添加顺序;你可以派遣他们每个人展开代码，与所有在每个代码块没有测试。这里，希望是一个间接跳转到成本低于4测试和分支。

<强>更新是乔纳森莱弗勒的脚手架，在 4位 - 在一次一个方法是最快按我的MacBook大幅。否定和原来是大致相同的乘法。不知处理器相乘特殊情况下，像在0和1更快（或不如果它的速度更快这样一种特殊情况中一般大多数比特透明或最比特集被乘数）。

我没有编写了公认的答案，因为它是不太可能最快在这个特别的基准（它应该得到它的大部分利益由枚举只设置位，做最好的稀疏集，但完全一半的比特是在这个基准设置）。下面是我对莱弗勒的代码更改，万一别人是奇怪的动机把时间花在这一点：

#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限定符更逼真

明显的解决方案：

int total = 0;
for(unsigned j = 0; j < 16; j++){
    total += -(i>>j & 1) & value[j];
}
许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top