我有一个任务,我必须采取一个程序,并使其在时间上更有效。 原始代码是:
#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. Forgotn"); 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也有优化:具体来说,避免使用一个长的依赖链。
进一步必读:
您的编译器手册也很重要,尤其是 用于浮点代码。 浮点的精度有限,并且不是关联的。 最终总和取决于您添加的顺序。但是,通常舍入误差的差异很小。 因此,如果使用-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 -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. Forgotn"); 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=%ldn", 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
。 那样做:
需要了解更多c/c++开发分享C中双精度数组的优化和,也可以关注C/ C++技术分享栏目---计算机技术网(www.ctvol.com)!
for (int i = 0; i < N_TIMES; i++)
以上就是c/c++开发分享C中双精度数组的优化和相关内容,想了解更多C/C++开发(异常处理)及C/C++游戏开发关注计算机技术网(www.ctvol.com)!)。
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/980602.html