C循环优化有助于最终分配
因此，对于我的计算机系统类的最终任务，我们需要优化这些forloops比原来的更快。 我们的linux服务器基本等级在7秒以下，全部等级在5秒以内。 这个代码，我在这里得到大约5.6秒。 我想我可能需要用某种方式使用指针来使它更快，但我不太确定。 任何人都可以提供任何提示或选项，我有？ 非常感谢！
QUICKEDIT：文件必须保留50行或更less，我忽略了教师所包含的那些注释行。
#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 ... register double sum1 = 0, sum2 = 0, sum3 = 0, sum4 = 0, sum5 = 0, sum6 = 0, sum7 = 0, sum8 = 0, sum9 = 0; register int j; // ... and this one. printf("CS201 - Asgmt 4 - \n"); for (i = 0; i < N_TIMES; i++) { // You can change anything between this comment ... for (j = 0; j < ARRAY_SIZE; j += 10) { sum += array[j]; sum1 += array[j + 1]; sum2 += array[j + 2]; sum3 += array[j + 3]; sum4 += array[j + 4]; sum5 += array[j + 5]; sum6 += array[j + 6]; sum7 += array[j + 7]; sum8 += array[j + 8]; sum9 += array[j + 9]; } // ... 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 ... sum += sum1 + sum2 + sum3 + sum4 + sum5 + sum6 + sum7 + sum8 + sum9; // ... and this one. return 0; } 你可能走在正确的轨道上，虽然你需要测量它是确定的（我的正常build议来衡量，而不是猜测似乎有点多余，因为整个任务的重点是衡量）。
优化编译器可能看不出什么区别，因为他们对这类东西非常聪明，但是由于我们不知道要编译的优化级别，所以可能会有很大的改进。
要在内部循环中使用指针，首先需要添加一个指针variables：
register double *pj;
然后改变循环为：
for (pj = &(array[0]); pj < &(array[ARRAY_SIZE]); j++) { sum += *j++; sum1 += *j++; sum2 += *j++; sum3 += *j++; sum4 += *j++; sum5 += *j++; sum6 += *j++; sum7 += *j++; sum8 += *j++; sum9 += *j; }
这样可以在循环中保持相同的添加量（当然，假设您将+=和++作为加法运算符），但基本上使用指针而不是数组索引。
在我的系统上没有优化1 ，这从9.868秒（CPU时间）下降到4.84秒。 你的旅费可能会改变。
1优化级别-O3 ， 都报告为0.001秒，如上所述，优化者是非常聪明的。 然而，如果你看到5秒以上，我build议它没有编译优化。
顺便说一句，这是为什么通常build议以可读方式编写代码并让编译器负责让代码更快运行的一个很好的理由。 虽然我微不足道的尝试在优化大概加倍速度，使用-O3使它运行快一万倍:-)
在C中重新发布我的答案，因为这个问题的投票结果是-5。 我没有重新编辑所有的问题，因为他做了类似的优化。 另一个问题的OP更多地表述为“还有什么可能”，所以我把他的话和信息转向了关于当前CPU硬件的vector化和调优。
那个问题的OP最终说他不允许使用高于-O0编译器选项，我想这也是这种情况。
概要：
-
为什么使用
-O0会扭曲事物（不正当地惩罚正常编译器的正常代码中的事情）。 -
东西是错误的任务。
-
优化types。 FP等待时间与吞吐量以及依赖关系链。 链接到Agner雾的网站。 （基本阅读优化）。
-
让编译器优化它的实验（修复之后不能优化）。 自动vector化的最佳结果（无源变化）：gcc：与最佳vector化循环一样快。 铛：与手vector化循环相同的速度。
-
一些更多的评论，为什么更大的expression式是一个只有
-O0perf的胜利。 -
源代码的变化，以获得良好的性能没有
-ffast-math，使代码更接近我们想要的编译器。 还有一些在现实世界中无用的规则 – 律师的想法。 -
使用GCC体系结构中性向量向量化循环，以查看自动向量化编译器与理想的asm代码（因为我检查了编译器输出）的性能相匹配的程度。
我认为这个任务的重点是用C语言来进行汇编语言性能优化，而不需要编译器优化。 这很愚蠢。 它将现实生活中编译器为你做的事情与需要源代码更改的东西混合在一起。
-O0使编译器在每个expression式之后将variables存储到内存中，而不是将它们保存在寄存器中。 涉及更多的variables，这会伤害数组索引而不是增加指针。
数组索引通常会使代码更易于阅读。 编译器有时不能优化像array[i*width + j*width*height]这样的东西，所以最好将source改为将multiply转换为adds的强度优化优化。
在优化的代码中，即使在asm级别，数组索引与指针增量大致相同。 （例如，x86的寻址模式像[rsi + rdx*4] ， 除了在Sandybridge和之后的版本之外，其速度与[rdi]一样快）。无论如何，编译器的工作是通过使用指针递增而不是数组来优化代码索引，当时更快。 多个指针递增指令可能比使用单个循环计数器的索引寻址模式花费更多。
如果gcc -O0实际上对variables的register关键字做任何事情，那就会有所作为。 在真正的代码中，为了使用优化进行编译，编译器可以很好地决定寄存器中的内容，忽略register关键字。 因此，我没有浪费时间讨论使用它。
为了获得良好的性能，您必须了解编译器可以做什么和不可以做什么。 有些优化是“脆弱”的，而对源代码的一个看似无害的小改变将会停止编译器的运行和优化，这对于一些代码运行起来是非常重要的。 （例如，从循环中抽出一个常量计算，或者certificate不同的分支条件是如何相互关联的，以及简化的。）
除此之外，这是一个废话示例，因为它没有任何东西阻止智能编译器优化整个事情。 它甚至不打印总和。 甚至gcc -O1 （而不是-O3 ）扔掉了一些循环。
（你可以通过在最后打印sum来解决这个问题，gcc和clang似乎并没有意识到calloc返回归零内存，并将其优化为0.0 ，请参阅下面的代码。
通常你会把你的代码放到一个函数中，然后在另一个文件的main()循环中调用它。 如果不进行全程序跨文件优化，那么编译器就不能根据您调用的编译时常量进行优化。 重复循环如此紧密地缠绕在数组的实际循环上会对gcc的优化器造成严重破坏（见下文）。
此外，这个问题的另一个版本有一个未初始化的variables踢。 这个问题的OP看起来好像是long int help ，而不是prof。 所以我必须把我的“胡言乱语”降级到“愚蠢”，因为代码甚至不会在最后打印结果。 这是使编译器不像以上那样在微处理器上优化所有东西的最常用方法。
我假设你的教授提到了一些关于性能的事情。 有不同的东西可以在这里发挥作用，其中许多我认为没有在第二年的CS类中提到。
除了使用openmp进行multithreading外，还有使用SIMD进行向量化。 还有现代stream水线CPU的优化：特别是，避免有一个长的依赖链。
进一步的必读：
- Agner Fog的优化C和asm for x86 的指南 。 其中一些适用于所有的CPU。
- 每个程序员应该知道的内存
您的编译器手册也是必不可less的，尤其是， 用于浮点代码。 浮点精度有限， 不关联。 最后的总和取决于你添加的顺序。然而，通常舍入误差的差别很小。 所以如果你使用-ffast-math来允许的话，编译器可以通过重新sorting来获得大的加速。 这可能是你的10倍以上允许的。
不要只展开，而是保留多个累加器，最后只添加累加器。 FP指令具有中等延迟，但吞吐量很高，因此您需要保留多个FP操作以保持浮点执行单元饱和。
如果您需要在下一个操作完成之前完成最后一个操作的结果，则会受到延迟的限制。 对于FP添加，这是每3个周期一个。 在英特尔Sandybridge，IvB，Haswell和Broadwell中，FP添加的吞吐量是每个周期一个。 所以你需要保持至less3个可以立即在飞行中的独立操作来饱和机器。 对于Skylake ， 每个周期有4个时钟的延迟 。 （在Skylake的优势方面，FMA降至4周期延迟。）
在这种情况下，还有一些基本的东西，例如help += ARRAY_SIZE 。
编译器选项
让我们看看编译器能为我们做什么。
我从最初的内部循环开始，只是help += ARRAY_SIZE拉出，并在最后添加一个printf ，所以gcc不会优化所有的东西。 让我们尝试一些编译器选项，看看我们可以用gcc 4.9.2（在我的i5 2500k Sandybridge上 ，3.8GHz的最大turbo（微小的OC），3.3GHz的持续时间（与这个短基准无关））：
-
gcc -O0 fast-loop-cs201.c -o fl：16.43s的performance完全是个玩笑。 variables在每次操作之后都会存储到内存中，并在下一次之前重新加载。 这是一个瓶颈，并增加了很多延迟。 更不用说在实际的优化上失利了。 使用-O0定时/调谐代码无用。 - -O1：4.87s
-
-O2：4.89s -
-O3：2.453s（用SSE做2次，我当然用的是64bit系统，所以硬件支持-msse2就是基准） -
-O3 -ffast-math -funroll-loops：2.439s -
-O3 -march=sandybridge -ffast-math -funroll-loops：1.275s（使用AVX一次做4个） -
-Ofast ...：没有收获 -
-O3 -ftree-parallelize-loops=4 -march=sandybridge -ffast-math -funroll-loops：0m2.375s real，0m8.500s用户。 看起来像locking头顶上杀了它。 它只产生了总共4个线程，但是内部循环太短而不能成为赢（因为它每次收集总和，而不是给一个线程外环迭代的第一个1/4）。 -
-Ofast -fprofile-generate -march=sandybridge -ffast-math，然后运行它
-Ofast -fprofile-use -march=sandybridge -ffast-math： 1.275s 。 当您可以执行所有相关的代码path时， configuration文件引导优化是一个好主意 ，因此编译器可以做出更好的展开/内联决策。 -
clang-3.5 -Ofast -march=native -ffast-math：1.070s。 （clang 3.5太老了，不能支持-march=sandybridge，你应该更喜欢使用足够新的编译器版本来了解你正在debugging的目标架构，特别是如果使用-march来创build不需要的代码在较旧的架构上运行。）
gcc -O3以热闹的方式进行vector化：内部循环通过向xmm（或ymm）寄存器的所有元素广播一个数组元素并在其上执行addpd ，并行执行外部循环的2（或4）次迭代。 所以它看到相同的值被重复添加，但即使-ffast-math也不会让gcc把它变成一个乘法。 或者切换循环。
铿锵-3.5vector化好多了：vector化的内部循环，而不是外部，所以它不需要广播。 它甚至使用4个vector寄存器作为4个独立的累加器。 然而，它并不假定calloc返回alignment的内存，由于某种原因，它认为最好的赌注是一对128b的负载。
vmovupd -0x60(%rbx,%rcx,8),%xmm4` vinsertf128 $0x1,-0x50(%rbx,%rcx,8),%ymm4,%ymm4
当我告诉它arrays是alignment的时，它实际上比较慢 。 （有一个像array = (double*)((ptrdiff_t)array & ~31);的愚蠢的黑客array = (double*)((ptrdiff_t)array & ~31);它实际上会生成一个屏蔽掉低5位的指令，因为clang-3.5不支持gcc的__builtin_assume_aligned 。） 4x vaddpd mem, %ymmX,%ymmXalignment的vaddpd mem, %ymmX,%ymmX是把cmp $0x271c,%rcx跨越一个32B的边界，所以它不能和jnemacros – 熔合。 但是，uop吞吐量不应该成为问题，因为这个代码每个周期只能达到0.65insns（和0.93 uops / cycle）。
啊，我用debugging器检查， calloc只返回一个16Balignment的指针。 因此，一半的32B内存访问正在穿越caching线，导致大幅减速。 我猜在Sandybridge上，当你的指针是16Balignment的而不是32Balignment的时候，做两个单独的16B加载会稍微快一些。 编译器在这里做出了一个不错的select。
源级别更改
正如我们从叮当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值首先被加在一起，然后被加到sum 。 因此，循环依赖链仍然只是一个FP添加的延迟，并且每组10个独立的工作很多。每个组是一个单独的9个附加的依赖链，看看下一个链的开始，并find并行性来保持这些中等延迟的高吞吐量的FP执行单元。
用-O0 ，因为你的愚蠢的任务显然需要，值在每个语句结束时存储到RAM。 （从技术上说，在每个“顺序点”，就像C标准所称的那样）。写更长的expression式而不更新任何variables，甚至是临时值，将会使-O0运行得更快，但这不是一个有用的优化。 不要浪费你的时间在只有 -O0帮助的变化上， 不以可读性为代价。
使用4个累加器variables，而不是将它们加在一起，直到外循环结束，才能击败clang的自动向量化器。 它仍然只运行在1.66s（对于海湾合作委员会的非vector化-O2为4.89，有一个累加器）。 即使gcc -O2没有-ffast-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编译器资源pipe理器的在线编译器输出，-xc编译器选项编译为C，而不是C ++，内部循环是从.L3到jne .L3 ，请参阅x86标记wiki获取x86 asm链接。 这个关于微型融合的问题不在SnB系列上发生 ，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的指针是alignment的。 所以caching库冲突不应该成为问题。 Sandybridge L2caching每个周期可以维持一个32B的传输，这应该跟上每个周期一个32B的FP向量。
32B从L1的负载需要2个周期（直到Haswell，英特尔使32B加载单周期操作）。 但是，有2个加载端口，所以每个周期的持续吞吐量是32B（我们没有达到）。
也许负载需要在使用之前进行stream水线操作，以尽量减less负载失速时ROB（重新sorting缓冲区）的填满？ 但是性能指标表明L1caching的命中率相当高，所以从L2到L1的硬件预取似乎正在完成其工作。
每个周期0.65条指令只是使向量FP加法器饱和的一半。 这令人沮丧。 即使IACA说循环应该在每个迭代中运行4个周期。 （即饱和加载端口和端口1（FP加法器所在的地方））：/
更新：我想L2带宽是毕竟的问题 。 没有足够的行填充缓冲区来保持足够的错过飞行，以维持每个周期的峰值吞吐量。 Intel的SnB / Haswell / Skylake处理器的L2持续带宽低于峰值 。
另请参阅Sandy Bridge上的单线程内存带宽 （Intel论坛线程，有关吞吐量的限制以及latency * max_concurrency是一个可能的瓶颈的问题进行了许多讨论。另请参阅“ Enhanced REP MOVSB for memcpy ”的“Latency Bound Platforms”部分;有限的内存并发性是加载和存储的瓶颈，但是对于预加载到L2中的加载意味着您可能不会被纯粹的行填充缓冲区限制，从而导致未完成的L1D未命中 。
将ARRAY_SIZE减less到1008（16的倍数），并将N_TIMES增加10倍，使运行时间降低到0.5s。 每个周期1.68次。 （对于4个FP加法，内部循环总共有7条指令，因此我们最终使vectorFP加法单元和加载端口饱和。）循环平铺是一个更好的解决scheme，见下文。
英特尔CPU只有32k的L1数据和L1指令caching。 我认为你的arrays几乎不适合AMD K10（伊斯坦布尔）CPU的64kiB L1D ，但不适合推土机族（16kiB L1D）或Ryzen（32kiB L1D）。
海湾合作委员会试图通过广播相同的价值并行添加似乎并不疯狂。 如果它设法正确（使用多个累加器来隐藏等待时间），那么它可以使得向量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次）。 我想我已经读过英特尔的编译器有时会为你做这个。
更通用的技术称为caching阻塞或循环平铺 。 这个想法是在适合caching的小块中处理input数据。 根据你的algorithm，可以在一个块上做不同的事情，然后重复下一个块，而不是让每个阶段在整个input上循环。 和往常一样，一旦你知道了一个把戏的正确名称（而且它存在），你可以谷歌了一吨的信息。
你可以用规则律师的方式，在你允许修改的代码部分的if (i == 0)块中放置一个互换的循环。 它仍然会执行相同数量的添加，但以更高的caching优化顺序。
在其他之前，尝试更改编译器设置以生成更快的代码。 有一般的优化，编译器可能会做自动vector化。
你总是会尝试几种方法，并检查最快的。 作为一个目标，尝试达到一个周期或更好。
每个循环的迭代次数：同时加10个和。 这可能是你的处理器没有足够的寄存器，或者它有更多。 我会测量每个循环4,5,6,7,8,9,10,11,12,13,14 …个和的时间。
总和数量：有多个总和意味着延迟不会咬你，只是吞吐量。 但是，超过四六个可能没有帮助。 尝试四个和，每个循环有4,8,12,16次迭代。 或者6次，总共6次，12次，18次。
caching：您正在运行一个80,000字节的数组。 可能超过一级caching。 将数组拆分成2或4个部分。 做一个外部循环遍历两个或四个子arrays，下一个循环从0到N_TIMES – 1，内部循环加起来的值。
然后你可以尝试使用vector操作，或者multithreading代码，或者使用GPU来完成工作。
如果您不得不使用优化，那么“注册”关键字可能实际上工作。
