C中双精度数组的优化和
我有一个任务，我必须采取一个程序，并使其在时间上更有效。 原始代码是：
#include #include // 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]; {
这本身就能够将时间减少到标准…… 它似乎已经起作用但是我有没有看到错误？
我发布了这个答案的改进版本的副本： C循环优化帮助最终分配 。 它最初只是一个转发，但后来我做了一些修改来回答这个问题的不同之处。 我忘了有什么不同，但你应该读一下。 也许我应该删除这个。
另请参阅x86标记wiki中的其他优化指南。
首先，它是一个非常废话的样本，因为它没有任何东西阻止智能编译器优化掉整个事物。 它甚至不打印总和。 即使是gcc -O1 （而不是-O3 ）也会丢掉一些循环。
通常，您将代码放在一个函数中，并在另一个文件中从main()循环调用它。 并且单独编译它们，没有整个程序的跨文件优化，因此编译器无法根据您调用它的编译时常量进行优化。 重复循环被紧紧缠绕在arrays上的实际循环周围，这会对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进行multithreading处理外，还有使用SIMD进行矢量化。 现代流水线CPU也有优化：具体来说，避免使用一个长的依赖链。
进一步必读：
- Agner Fog的优化C和asm for x86 的指南 。 其中一些适用于所有CPU。
- 每个程序员应该了解的内存
您的编译器手册也很重要，尤其是 用于浮点代码。 浮点的精度有限，并且不是关联的。 最终总和取决于您添加的顺序。但是，通常舍入误差的差异很小。 因此，如果使用-ffast-math来允许它，编译器可以通过重新排序来获得大的加速。 这可能是你的unrol-by-10允许的。
保留多个累加器而不仅仅是展开，保留最后只能添加的累加器可以使浮点执行单元保持饱和，因为FP指令具有延迟！=吞吐量。 如果您需要在下一个操作开始之前完成最后一个操作的结果，那么您将受到延迟的限制。 对于FP add，这是每3个周期一个。 在Intel Sandybridge，IvB，Haswell和Broadwell中，FP add的吞吐量是每个周期一个。 因此，您需要保留至少3个独立操作，这些操作可以同时在飞行中以使机器饱和。 对于Skylake来说 ， 每个周期2个，延迟为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性能是个笑话。 变量在每次操作后都存储到内存中，并在下一次操作之前重新加载。 这是一个瓶颈，并增加了很多延迟。 更不用说失去实际的优化。 使用-O0定时/调整代码没有用。 - -O1：4.87s
-
-O2：4.89s -
-O3：2.453s（使用SSE一次执行2.我当然使用64位系统，因此-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 user。 看起来像锁定头顶杀了它。 它只产生4个线程总数，但内部循环太短而不能成为胜利（因为它每次都收集总和，而不是给一个线程外部循环迭代的前1/4）。 -
-Ofast -fprofile-generate -march=sandybridge -ffast-math，然后运行它
-Ofast -fprofile-use -march=sandybridge -ffast-math：1.275s -
clang-3.5 -Ofast -march=native -ffast-math：1.070s。 （clang不支持-march=sandybridge）。
gcc -O3以一种搞笑的方式进行矢量化：内部循环通过将一个数组元素广播到xmm（或ymm）寄存器的所有元素，并在其上执行addpd ，并行地执行外部循环的2（或4）次迭代。 因此它看到重复添加相同的值，但即使是-ffast-math也不会让gcc将其转换为乘法。 或者切换循环。
clang-3.5矢量化更好：它矢量化内部循环，而不是外部，所以它不需要广播。 它甚至使用4个向量寄存器作为4个独立的累加器。 但是，它并不假设calloc返回对齐的内存，并且由于某种原因它认为最好的选择是一对128b负载。
vmovupd -0x60(%rbx,%rcx,8),%xmm4` vinsertf128 $0x1,-0x50(%rbx,%rcx,8),%ymm4,%ymm4
当我告诉它arrays是对齐时，它实际上更慢 。 （有一个像array = (double*)((ptrdiff_t)array & ~31);这样的愚蠢的hack array = (double*)((ptrdiff_t)array & ~31);它实际上生成一个屏蔽低5位的指令，因为clang-3.5不支持gcc的__builtin_assume_aligned 。）我认为4x vaddpd mem, %ymmX,%ymmX的紧密循环vaddpd mem, %ymmX,%ymmX对齐放置cmp $0x271c,%rcx越过32B边界，因此它不能与jne宏融合。 不过，uop吞吐量应该不是问题，因为这个代码每个周期只能得到0.65insns（和0.93 uops /周期）。
啊，我用调试器检查过，而calloc只返回一个16B对齐的指针。 因此，32B内存访问的一半正在跨越缓存线，导致大幅减速。 我想在Sandybridge上你的指针是16B对齐而不是32B对齐时，做两个单独的16B加载会稍快一些。 编译器在这里做出了不错的选择。
源级别更改
正如我们从铿锵打击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个添加的依赖链，并且几乎没有足够的指令用于out-of - 订单执行硬件，以查看下一个链的开始，并找到并行性以保持这些中等延迟，高吞吐量FP执行单元馈送。
使用-O0 ，正如您的愚蠢分配显然需要的那样，值会在每个语句的末尾存储到RAM中。 （从技术上讲，在每个“序列点”，正如C标准所称。）编写更长的表达式而不更新任何变量，即使是临时变量，也会使-O0运行得更快，但这不是一个有用的优化。 不要把时间浪费在仅对 -O0帮助的变化上，尤其是 不以牺牲可读性为代价。
使用4累加器而不是将它们加在一起，直到外循环结束，才能击败clang的自动矢量化器。 它仍然只运行1.66秒（对于gcc的非矢量化-O2与一个累加器相比为4.89）。 即使没有-ffast-math gcc -O2也会因此源变化而获得1.66秒。 请注意，已知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 #include #include #include #include // 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
（有关更多内容， 请参阅godbolt的在线编译器输出 。注意我必须转换calloc的返回值，因为godbolt使用C ++编译器，而不是C编译器。内部循环是从.L3到jne .L3 。请参阅https：// stackoverflow .com / tags / x86 / info for x86 asm links。另请参见微融合和寻址模式 ，因为Sandybridge的更改还没有进入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检查指针是否对齐。 所以缓存库冲突不应该是问题。 Sandybridge L2缓存每个周期可以支持一次32B传输，这应该跟上每个周期一个32B FP矢量的增加。
从L1加载32B负载需要2个周期（直到Haswell，直到英特尔制造32B加载单周期操作）。 但是，有2个加载端口，因此每个周期的持续吞吐量为32B（我们没有达到）。
也许负载需要在使用之前进行流水线操作，以便在负载停止时最小化ROB（重新排序缓冲区）填满？ 但是，perf计数器表明L1缓存命中率相当高，因此从L2到L1的硬件预取似乎正在起作用。
每个周期0.65指令只是使矢量FP加法器饱和的一半。 这令人沮丧。 即使是IACA ，循环也应该在每次迭代中运行4个周期。 （即饱和装载端口和端口1（FP加法器所在的位置））：/
更新：我认为L2延迟毕竟是问题所在。 将ARRAY_SIZE减少到1008（16的倍数），并将N_TIMES增加10倍，使运行时间缩短到0.5秒。 这是每周期1.68次。 （内部循环是4个FP添加的总指令，因此我们最终使矢量FP添加单元和加载端口饱和。）IDK为什么HW预取器在一个停顿后无法前进，然后保持领先。 可能软件预取可能会有所帮助吗？ 也许以某种方式避免让HW预取器运行通过数组，而是再次开始预取数组的开始。 （循环平铺是一个更好的解决方案，见下文。）
Intel CPU每个L1数据和L1指令缓存只有32k。 我认为你的arrays几乎不适合AMD CPU上的L1。
Gcc尝试通过将相同的值广播到并行添加来进行矢量化并不是那么疯狂。 如果它设法做到这一点（使用多个累加器来隐藏延迟），这将使其仅使用一半的内存带宽使矢量FP加法器饱和。 原来，它几乎是一种洗漱，可能是因为广播的开销。
而且，这很傻。 N_TIMES只是一个make-work重复。 我们实际上并不想优化多次完成相同的工作。 除非我们想要赢得像这样的愚蠢任务。 执行此操作的源级方法是在我们允许修改的代码部分中增加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)块中。 它仍将执行相同数量的添加，但是以更高的缓存最佳顺序。
我会尝试这个内循环：
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++; }
我想如果你可以使用multithreading，你应该阅读openmp库。 但这是一个非常简单的例子，我认为无法进行优化。
某些事情是你不需要在循环之前声明i和j 。 那样做：
for (int i = 0; i < N_TIMES; i++)