为什么我不能达到最大的性能与整数相加？

Question

这里是一个基本函数，它与整数的向量相加。当使用gcc进行第三级优化(-O3)编译时，我可以实现 0.51，这是我们所能得到的最大值。

int sum_basic(int a[], long n)
{
    int acc = 0;
    for (long i = 0; i < n; i++) {
        acc += a[i];
    }
    return acc;
}

下面是这个函数的优化版本，它应用4x4循环展开。我所能得到的最好结果是CPE 0.84。我尝试过其他类型的优化，但无法接近 0.51。用整数乘法，我可以打败gcc，用浮点运算，我可以达到最大的性能，gcc不能，但是用整数加法，我会赢。有什么问题吗？

int sum_optimized(int a[], long n) {
    int acc1 = 0;
    int acc2 = 0;
    int acc3 = 0;
    int acc4 = 0;

    for (long i = 0; i < n; i+=4) {
        acc1 += a[i];
        acc2 += a[i+1];
        acc3 += a[i+2];
        acc4 += a[i+3];
    }

    return acc1 + acc2 + acc3 + acc4;
}

我使用这个代码来度量CPE：

// get CPU cycle counter
static __inline__ unsigned long long rdtsc(void)
{
    unsigned hi, lo;
    __asm__ __volatile__ ("rdtsc" : "=a"(lo), "=d"(hi));
    return ( (unsigned long long)lo)|( ((unsigned long long)hi)<<32 );
}

#define SIZE  10000
int a[SIZE];

int main(void)
{
    // cache warm up + initialize array
    for (long i = 0; i < SIZE; i++)
        a[i] = rand();

    long r_begin = rdtsc();
    //---------- MEASURE THIS ------------
    int res = sum_optimized(a, SIZE);
    //------------------------------------
    long r_end = rdtsc();
    long cycles = r_end - r_begin;
    double cpe = cycles / (double)SIZE;
    printf("CPE:    %.2f \n", cpe);

    return res;
}

Answer 1

TL:这可能是一个已知的遗漏优化错误(gcc不使用带符号整数的关联数学优化)，与普通的旧编译器结合在一起，实际上并不是人工智能，而是生成缓慢的代码。

首先，RDTSC测量墙壁时钟时间，不一定是核心时钟周期.使用perf计数器来测量微基准测试中的核心时钟周期，这样您就不必担心CPU频率的缩放了。(除非您的微基准测试涉及L2缓存丢失，因为相同的时间(以纳秒为单位)是更高频率的更多时钟周期。也就是说，高频意味着缓存丢失的伤害更大，而主内存带宽每周期以字节为单位减少。)

gcc 5.3 (没有-march=nehalem或-mtune=haswell或其他任何内容)将基本版本自动向量化到它通常选择的标量，直到一个对齐边界，然后向量化的内环：

来自戈德波特编译器浏览器

 # gcc5.3  -O3 -fverbose-asm   (-mtune=generic; only SSE2 because no -march used)

 sum_basic:
 ... scalar prologue
.L14:   ### inner loop
    add     rdx, 1    # ivtmp.39,
    paddd   xmm0, XMMWORD PTR [r9]        # vect_acc_10.34, MEM[base: _156, offset: 0B]
    add     r9, 16    # ivtmp.40,
    cmp     r8, rdx   # bnd.28, ivtmp.39
    ja      .L14        #,

  ... horizontal sum and scalar epilogue

所以，傻gcc，保留两个单独的循环计数器，而不是只检查r9是否到达a+n。或者至少使用dec rdx / jnz循环以避免cmp。但是没有，所以循环有4个融合域uop，它们都需要一个ALU端口。因此，它可以在Intel Core2上每时钟执行一次迭代，但每次只在Haswell和以后执行一次迭代(这增加了第4个ALU端口)。

在SnB和更高版本上，两个向量ALU的展开将使小数组的吞吐量翻倍，因为PADDD有一个周期延迟，但每个周期吞吐量有两个(或三个)，负载也是如此。在较大的数组中，您仍然只是内存带宽的瓶颈。

当您使用4个累加器手动展开时，gcc决定保留这些语义，只需在内部循环中使用未对齐的负载。令人遗憾的是，gcc 5.3最后做了一项非常糟糕的工作：

# gcc5.3 -O3 -fverbose-asm   (-mtune=generic, same lack of enabling SSE4/AVX/AVX2)
sum_optimized:
   zero xmm0 and some other minor setup
.L3:
    mov     rdx, rax
    add     rax, 1
    sal     rdx, 4           # what the hell gcc?  just add 16 instead of copying and shifting a separate instructions.  Even if it takes two loop counters like in the basic version.
    cmp     rcx, rax         # cmp not next to ja, can't macro-fuse.  (-mtune=haswell fixes this)
    movdqu  xmm1, XMMWORD PTR [rdi+rdx]    # separate load, not folded into paddd because it's unaligned.
    paddd   xmm0, xmm1
    ja      .L3
    ...
    A hilarious horizontal sum that uses MOVD on each element separately and sums with scalar integer ops.  (With -march=nehalem, it uses PEXTRD)

这是英特尔Nehalem和更高版本上的7个融合域uop。在Core2上，它是9 uops。在Nehalem之前，movdqu是多个uop，运行速度比movdqa慢，即使在运行时数据是对齐的。

无论如何，假设Nehalem或更高版本，这可以在每2个周期迭代一次，这是瓶颈。每2个周期执行最多可处理6个ALU uops。即使指针没有对齐，也不应该再慢下来，因为gcc的代码已经太慢了。

，我的理论是，这是因为gcc中一个已知的遗漏优化错误:以不同的顺序添加数字会导致溢出。最终一切都会好起来的，这要归功于2的补充，但是gcc不知道如何利用这个优势。C中的签名溢出是未定义的行为，但在x86上不是。

在理查德·比纳( Richard )对a+b+c+d+e+f+g+h的回应中，他说：

这是一个长期存在的问题，理由是不相关的！TYPE_OVERFLOW_WRAPS链。这是一个长期存在的问题，不相关！TYPE_OVERFLOW_WRAPS链它可以在一定程度上做到这一点(只有取消不影响溢出的操作)，或者在提交时将操作重写为未签名的算术。为了避免将所有有符号的整数运算重写为无符号的，需要某种方法来检测所需的或仅仅是规范化的转换(嗯，也许实际上并不是那么糟糕，谁知道呢)。

这两个版本所使用的水平和算法为这一理论提供了一些支持: sum_basic使用的是一个正常的移位-向下-上半和向量加法。sum_optimized分别提取每个向量元素。

如何使它运行得更快：

使用-march=native编译，特别是如果您有一个支持AVX2的CPU。

正如我前面提到的，多个矢量累加器，只要有正确的展开量，就可以在英特尔SnB家族或AMD K10或更高版本上为每个时钟添加两个负载和两个128或256 b矢量。(IIRC，AMD K8每个时钟可以执行两个负载，但没有128 B级的执行单元。)

和往常一样，运行微基准的硬件和数组大小都很重要！