问题：

C [duplicate]中双精度数组的优化和

曹嘉许

2023-03-14

我有一项任务，我必须参加一个项目，使其在时间方面更有效率。原始代码为：

#include <stdio.h>
#include <stdlib.h>

// You are only allowed to make changes to this code as specified by the comments in it.

// The code you submit must have these two values.
#define N_TIMES     600000
#define ARRAY_SIZE   10000

int main(void)
{
    double  *array = calloc(ARRAY_SIZE, sizeof(double));
    double  sum = 0;
    int     i;

    // You can add variables between this comment ...
    long int help;
    // ... and this one.

    // Please change 'your name' to your actual name.
    printf("CS201 - Asgmt 4 - I. Forgot\n");

    for (i = 0; i < N_TIMES; i++) {

        // You can change anything between this comment ...

        int     j;

        for (j = 0; j < ARRAY_SIZE; j++) {
            sum += array[j];
            help++;
            }

        // ... and this one. But your inner loop must do the same
        // number of additions as this one does.

        }
    // You can add some final code between this comment ...

    // ... and this one.

    return 0;
}

我几乎完全修改了第二个for循环，将其改为

double *j=array;
double *p=array+ARRAY_SIZE;

for(; j<p;j+=10){
    sum += j[0]+j[1]+j[2]+j[3]+j[4]+j[5]+j[6]+j[7]+j[8]+j[9];
{

这本身就能够将时间缩短到标准…它似乎已经起作用了，但有什么我没有看到的错误吗？

共有3个答案

巫马劲

2023-03-14

我认为如果您可以使用多线程，您应该阅读openmp库。但这是一个如此简单的例子，我认为无法优化。

可以肯定的是，您不需要在 for 循环之前声明 i 和 j。这将可以：

for (int i = 0; i < N_TIMES; i++)

方和豫

2023-03-14

我会尝试这个内部循环：

    double* tmp = array;
    for (j = 0; j < ARRAY_SIZE; j++) {
        sum += *tmp;  // Use a pointer
        tmp++;        // because it is faster to increment the pointer
                      // than it is to recalculate array+j every time
        help++;
    }

或者更好

double* tmp = array;
double* end = array + ARRAY_SIZE; // Get rid of variable j by calculating 
                                  // the end criteria and
while (tmp != end) {              // just compare if the end is reached
    sum += *tmp;
    tmp++;
    help++;
}

弘浩瀚

2023-03-14

我在这个问题的副本上发布了这个答案的改进版本：用于最终分配的C循环优化帮助。它最初只是一个重新发布，但后来我做了一些更改来回答那个问题中的差异。我忘记了有什么不同，但你可能应该读一下那个。也许我应该删除这个。

另请参阅x86标记wiki中的其他优化指南。

首先，这是一个非常糟糕的示例，因为它没有任何东西可以阻止智能编译器优化整个东西。它甚至不打印总和。甚至gcc-O1（而不是-O3）也丢弃了一些循环。

通常，您会将代码放在一个函数中，并在另一个文件中的< code>main()循环中调用它。并且单独编译它们，没有整个程序的跨文件优化，所以编译器不能基于你调用它的编译时常数进行优化。repeat-loop如此紧密地缠绕在数组上的实际循环周围，导致了gcc优化器的混乱(见下文)。

另外：

gcc -Wall -O3 -march=native  fast-loop-cs201.c -o fl
fast-loop-cs201.c: In function ‘main’:
fast-loop-cs201.c:17:14: warning: ‘help’ is used uninitialized in this function [-Wuninitialized]
     long int help;

我必须同意EOF对你的教授的贬低性言论，给出优化到无目的的代码，以及未初始化的变量，完全是无稽之谈。

有些人在评论中说“编译器不重要”，你应该为CPU微体系结构优化你的C源代码，而不是让编译器去做。这是废话:为了获得好的性能，你必须知道编译器能做什么，不能做什么。一些优化是“脆弱”的，对源代码的一个看似无害的小改变会阻止编译器做一些事情。

我想你的教授提到了一些关于性能的事情。这里有许多不同的东西可以发挥作用，其中许多我认为在二年级的CS课程中没有提到。

除了openmp的多线程，还有SIMD的矢量化。现代流水线CPU也有优化：特别是，避免有一个长的依赖链。

进一步的基本阅读：

< li>Agner Fog为x86优化C和asm的指南。其中一些适用于所有的CPU。 < li >每个程序员都应该知道的内存知识

您的编译器手册也是必不可少的，尤其是。对于浮点代码。浮点精度有限，并且不是关联的。最终的总和确实取决于您添加的顺序。然而，通常舍入误差的差异很小。因此，如果您使用-ffast-Mathematic允许编译器重新排序，编译器可以通过重新排序来获得很大的加速。这可能是您的unroll by-10所允许的。

不只是展开，而是保留多个累加器（只在末尾累加）可以使浮点执行单元保持饱和，因为FP指令有延迟！=吞吐量如果您需要在下一个操作开始之前完成上一个操作的结果，那么您会受到延迟的限制。对于FP加法，这是每3个周期一次。在Intel Sandybridge、IvB、Haswell和Broadwell中，FP add的吞吐量是每个周期一个。因此，您需要保留至少3个可以同时运行的独立操作，以使机器饱和。对于天湖，每周期2个，延迟为4个时钟。（天湖的好处是，FMA延迟降低到4个周期。）

在这种情况下，还有一些基本的东西，比如从循环中取出东西，例如< code>help = ARRAY_SIZE。

我从最初的内部循环开始，只取出help=ARRAY_SIZE，并在末尾添加printfgcc，这样gcc就不会对所有内容进行优化。让我们尝试一些编译器选项，看看gcc 4.9.2（在我的i5 2500k Sandybridge上，最大3.8GHz的turbo（轻微OC），持续3.3GHz（与这个短基准测试无关）可以实现什么：

gcc -O0 快速循环 cs201.c -o fl： 16.43s 的性能完全是一个笑话。变量在每次操作后存储到内存中，并在下一次操作之前重新加载。这是一个瓶颈，并增加了很多延迟。更不用说失去实际的优化了。使用 -O0 的计时/调整代码没有用。

-O1： 4.87 秒

-O2： 4.89 秒

-O3： 2.453 秒（使用 SSE 一次执行 2 个。我当然使用的是 64 位系统，因此对 -msse2 的硬件支持是基准。

-O3 -快速数学 -功能卷-循环： 2.439s

-O3 -行进=桑迪布里奇 -快速数学 -函数循环： 1.275s （使用 AVX 一次执行 4 个。

-奥法斯特...：没有增益

-O3 -ftree-并行化循环=4 -行进=沙桥-法斯特-数学-funroll-循环：0m2.375s真实，0m8.500s用户。看起来锁定头顶杀死了它。它只生成总共 4 个线程，但内部循环太短，无法获胜（因为它每次都会收集总和，而不是给一个线程提供外部循环迭代的前 1/4）。

-奥菲斯特 -fprofile-生成 -行进 =桑迪布里奇 -快速数学，运行它，然后
-Ofast -f轮廓-使用 -行进 -沙桥-法斯特-数学： 1.275s

clang-3.5-Ofast-march=native-ffast math:1.070秒。（clang不支持-march=sandybridge）。

gcc-O3以一种有趣的方式进行矢量化：内部循环并行地对外部循环进行2（或4）次迭代，方法是将一个数组元素广播到xmm（或ymm）寄存器的所有元素，然后对其执行addpd。因此，它看到相同的值被重复添加，但即使-fast-math也不允许gcc将其转换为乘法。或者切换循环。

clang-3.5向量化效果更好：它向量化了内部循环，而不是外部循环，因此不需要广播。它甚至使用4个向量寄存器作为4个单独的累加器。然而，它不假设calloc返回对齐的内存，出于某种原因，它认为最好的选择是一对128b加载。

vmovupd -0x60(%rbx,%rcx,8),%xmm4`
vinsertf128 $0x1,-0x50(%rbx,%rcx,8),%ymm4,%ymm4

当我告诉它阵列已对齐时，它实际上会变慢。（使用类似于array=（double*）（（ptrdifftt）数组的愚蠢方法

啊，我用调试器检查了一下，calloc只返回了一个16B对齐的指针。所以32B一半的内存访问都跨越了缓存行，导致速度大大降低。我想在Sandybridge上，当你的指针16B对齐但没有32B对齐时，进行两次单独的16B加载会稍微快一点。编译器在这里做了一个很好的选择。

正如我们从clang敲打gcc中看到的，多个累加器非常好。最明显的方法是：

for (j = 0; j < ARRAY_SIZE; j+=4) {  // unroll 4 times
    sum0 += array[j];
    sum1 += array[j+1];
    sum2 += array[j+2];
    sum3 += array[j+3];
}

然后不要将4个累加器收集成一个，直到外循环结束。

您的源更改

sum += j[0]+j[1]+j[2]+j[3]+j[4]+j[5]+j[6]+j[7]+j[8]+j[9];

由于无序执行，实际上也有类似的效果。每组10人是一个单独的依赖链。操作顺序规则表示j值首先相加，然后再相加到总和。因此，循环依赖链仍然只是一个FP加法的延迟，每个10个加法组有很多独立的工作。每个组是一个9个加法的独立依赖链，对于无序的执行硬件来说，只需要很少的指令就可以看到下一个链的开始，并找到并行性来保持这些中等延迟、高吞吐量的FP执行单元。

使用-O0，就像愚蠢的赋值显然需要的那样，值在每个语句结束时存储到RAM。（技术上，在C标准所称的每个“序列点”。）编写更长的表达式而不更新任何变量，甚至临时变量，将使-O0运行更快，但这不是一个有用的优化。不要把时间浪费在只对-O0有帮助的更改上，尤其不要以可读性为代价。

使用4个累加器，直到外循环结束时才将它们相加，这会击败clang的自动矢量器。它仍然只运行1.66秒（而gcc的非矢量化-O2只有一个累加器，运行时间为4.89秒）。即使没有-ffast-math的gcc-O2-fast-math也可以获得1.66s的源代码更改。请注意，已知ARRAY_SIZE是4的倍数，因此我没有包含任何清理代码来处理最后的最多3个元素（或者避免读取数组末尾之后的内容，这将在写入时发生）。在执行此操作时，很容易出错并读取超过数组末尾的内容。

另一方面，gcc确实对此进行了矢量化，但是它也将内部循环简化(取消优化)为一个依赖链。我认为它又一次重复了外部循环。

使用gcc的平台无关的向量扩展，我编写了一个编译成明显最佳代码的版本：

// compile with gcc -g -Wall -std=gnu11 -Ofast -fno-tree-vectorize -march=native fast-loop-cs201.vec.c -o fl3-vec

#include <stdio.h>
#include <stdlib.h>
#include <stddef.h>
#include <assert.h>
#include <string.h>

// You are only allowed to make changes to this code as specified by the comments in it.

// The code you submit must have these two values.
#define N_TIMES     600000
#define ARRAY_SIZE   10000

int main(void)
{
    double  *array = calloc(ARRAY_SIZE, sizeof(double));
    double  sum = 0;
    int     i;

    // You can add variables between this comment ...
    long int help = 0;

    typedef double v4df __attribute__ ((vector_size (8*4)));
    v4df sum0={0}, sum1={0}, sum2={0}, sum3={0};

    const size_t array_bytes = ARRAY_SIZE*sizeof(double);
    double *aligned_array = NULL;

    // this more-than-declaration could go in an if(i == 0) block for strict compliance with the rules
    if ( posix_memalign((void**)&aligned_array, 32, array_bytes) ) {
        exit (1);
    }
    memcpy(aligned_array, array, array_bytes);  // In this one case: faster to align once and have no extra overhead for N_TIMES through the loop

    // ... and this one.

    // Please change 'your name' to your actual name.
    printf("CS201 - Asgmt 4 - I. Forgot\n");

    for (i = 0; i < N_TIMES; i++) {

        // You can change anything between this comment ...
    /*
    #if defined(__GNUC__) && (__GNUC__ * 100 + __GNUC_MINOR__) >= 407 // GCC 4.7 or later.
        array = __builtin_assume_aligned(array, 32);
    #else
        // force-align for other compilers.  This loop-invariant will be done outside the loop.
        array = (double*) ((ptrdiff_t)array & ~31);
    #endif
    */

        assert ( ARRAY_SIZE / (4*4) == (ARRAY_SIZE+15) / (4*4) );  // We don't have a cleanup loop to handle where the array size isn't a multiple of 16


        // incrementing pointers can be more efficient than indexing arrays
        // esp. on recent Intel where micro-fusion only works with one-register addressing modes
        // of course, the compiler can always generate pointer-incrementing asm from array-indexing source
        const double *start = aligned_array;

        while ( (ptrdiff_t)start & 31 ) {
            // annoying loops like this are the reason people use aligned buffers
            sum += *start++;        // scalar until we reach 32B alignment
            // in practice, this loop doesn't run, because we copy into an aligned buffer
            // This will also require a cleanup loop, and break our multiple-of-16 doubles assumption.
        }

        const v4df *end = (v4df *)(aligned_array+ARRAY_SIZE);
        for (const v4df *p = (v4df *)start ; p+3 < end; p+=4) {
            sum0 += p[0];   // p+=4 increments the pointer by 4 * 4 * 8 bytes
            sum1 += p[1];       // make sure you keep track of what you're incrementing
            sum2 += p[2];
            sum3 += p[3];

        }

        // the compiler might be smart enough to pull this out of the inner loop
        // in fact, gcc turns this into a 64bit movabs outside of both loops :P
        help+= ARRAY_SIZE;

            // ... and this one. But your inner loop must do the same
            // number of additions as this one does.

        /* You could argue legalese and say that
         if (i == 0) {
             for (j ...)
                 sum += array[j];
             sum *= N_TIMES;
         }
         * still does as many adds in its *INNER LOOP*, but it just doesn't run it as often
         */
    }

    // You can add some final code between this comment ...
    sum0 = (sum0 + sum1) + (sum2 + sum3);
    sum += sum0[0] + sum0[1] + sum0[2] + sum0[3];
    printf("sum = %g; help=%ld\n", sum, help);  // defeat the compiler.

    free (aligned_array);
    free (array);  // not strictly necessary, because this is the end of main().  Leaving it out for this special case is a bad example for a CS class, though.
    // ... and this one.

    return 0;
}

内部循环编译为：

  4007c0:       c5 e5 58 19             vaddpd (%rcx),%ymm3,%ymm3
  4007c4:       48 83 e9 80             sub    $0xffffffffffffff80,%rcx   # subtract -128, because -128 fits in imm8 instead of requiring an imm32 to encode add $128, %rcx
  4007c8:       c5 f5 58 49 a0          vaddpd -0x60(%rcx),%ymm1,%ymm1   # one-register addressing mode can micro-fuse
  4007cd:       c5 ed 58 51 c0          vaddpd -0x40(%rcx),%ymm2,%ymm2
  4007d2:       c5 fd 58 41 e0          vaddpd -0x20(%rcx),%ymm0,%ymm0
  4007d7:       4c 39 c1                cmp    %r8,%rcx  # compare with end with p
  4007da:       75 e4                   jne    4007c0 <main+0xb0>

（有关详细信息，请参阅 godbolt 中的联机编译器输出。注意我必须转换 calloc 的返回值，因为 godbolt 使用 C 编译器，而不是 C 编译器。内部循环来自。L3 到 jne .L3.请参阅 x86 asm 链接的 https://stackoverflow.com/tags/x86/info。另请参阅微融合和寻址模式，因为桑迪布里奇的这一变化尚未进入Agner Fog的手册。

性能:

$ perf stat -e task-clock,cycles,instructions,r1b1,r10e,stalled-cycles-frontend,stalled-cycles-backend,L1-dcache-load-misses,cache-misses ./fl3-vec 
CS201 - Asgmt 4 - I. Forgot
sum = 0; help=6000000000

 Performance counter stats for './fl3-vec':

       1086.571078      task-clock (msec)         #    1.000 CPUs utilized          
     4,072,679,849      cycles                    #    3.748 GHz                    
     2,629,419,883      instructions              #    0.65  insns per cycle        
                                                  #    1.27  stalled cycles per insn
     4,028,715,968      r1b1                      # 3707.733 M/sec  # unfused uops
     2,257,875,023      r10e                      # 2077.982 M/sec  # fused uops.  lower than insns because of macro-fusion
     3,328,275,626      stalled-cycles-frontend   #   81.72% frontend cycles idle   
     1,648,011,059      stalled-cycles-backend    #   40.47% backend  cycles idle   
       751,736,741      L1-dcache-load-misses     #  691.843 M/sec                  
            18,772      cache-misses              #    0.017 M/sec                  

       1.086925466 seconds time elapsed

我仍然不知道为什么它每个周期的指令如此之低。内部循环使用4个单独的累加器，我用gdb检查指针是否对齐。因此，缓存库冲突应该不是问题所在。桑迪布里奇 L2 缓存每个周期可以维持一个 32B 传输，这应该与每个周期一个 32B FP 向量添加保持同步。

从L1加载32B需要2个周期（直到Haswell，Intel制造的32B才加载单周期操作）。然而，有两个加载端口，因此每个周期的持续吞吐量为32B（我们还没有达到）。

也许负载需要在使用之前流水线化，以最大限度地减少负载停止时ROB（重新排序缓冲区）的填满？但是性能计数器表明L1缓存命中率相当高，因此从L2到L1的硬件预取似乎正在发挥作用。

每个周期0.65条指令只是矢量FP加法器饱和的一半左右。这是令人沮丧的。甚至IACA也表示，循环每次迭代应该以4个周期运行。（即使加载端口和端口1饱和（FP加法器所在的位置））：/

更新：我想L2延迟毕竟是个问题。将ARRAY_SIZE减少到1008（16的倍数），并将N_TIMES增加10倍，使运行时间降至0.5。这是每个周期1.68 inns。（内部循环是4个FP添加的7条总指令，因此我们最终饱和了向量FP添加单元和加载端口。）IDK为什么硬件预取器在一次停滞后无法领先，然后保持领先。可能软件预取会有所帮助？也许以某种方式避免硬件预取器运行超过数组，而是再次开始预取数组的开始。（循环平铺是一个更好的解决方案，见下文。）

英特尔CPU只有32k的L1数据和L1指令高速缓存。我认为你的阵列只能勉强适应AMD CPU上的L1。

Gcc试图通过将相同的值广播到并行加法中来进行矢量化，这似乎并不疯狂。如果它成功做到了这一点（使用多个累加器来隐藏延迟），那么它只需一半的内存带宽就可以使矢量FP加法器饱和。事实上，这几乎是一场洗礼，可能是因为广播的开销。

另外，这也很愚蠢。N_TIMES只是一个制造工作的重复。我们实际上不想优化多次做相同的工作。除非我们想在这样愚蠢的任务中获胜。做到这一点的源代码级方法是在我们被允许修改的代码部分增加i：

for (...) {
    sum += a[j] + a[j] + a[j] + a[j];
}
i += 3;  // The inner loop does 4 total iterations of the outer loop

更现实地说，为了解决这个问题，你可以交换你的循环（循环数组一次，将每个值添加N_TIMES次）。我想我已经读到英特尔的编译器有时会为你做这件事。

一种更通用的技术称为缓存分块，或循环分块。这个想法是在适合缓存的小块中处理输入数据。根据您的算法，可以对一个块执行不同阶段的操作，然后对下一个块重复，而不是让每个阶段循环整个输入。和往常一样，一旦你知道了一个魔术的正确名称(并且它确实存在)，你就可以通过谷歌搜索到大量的信息。

您可以使用规则律师将交换循环放入允许您修改的代码部分的if（i==0）块中。它仍然会进行相同数量的添加，但顺序更有利于缓存。

C [duplicate]中双精度数组的优化和

共有3个答案

相关问答

相关文章

相关阅读

相关工具

相关文档