我正在重新发布我在
C中一组双精度数组的优化求和的答案的修改版本,因为那个问题被投票降到了-5。另一个问题的提问者更多地表达了“还有什么其他可能性”,所以我按照他的意思进行了信息倾泻,介绍了关于向量化和针对当前CPU硬件进行调优的内容。:)
那个问题的提问者最终表示他不被允许使用高于
-O0
的编译器选项,我猜这里也是一样的情况。
总结:
为什么使用-O0
会扭曲事物(对正常代码和正常编译器来说,不公平地惩罚那些本来没问题的东西)。 使用-O0
(gcc/clang的默认选项)让循环不被优化掉并不是一个有效的借口,也不是一个有用的方法来找出在启用正常优化的情况下哪个更快(也可以参考性能评估的惯用方法?,了解更多关于基准测试方法和陷阱的信息,比如如何启用优化但仍然阻止编译器优化掉你想要测量的工作)。
作业中存在的问题。
优化的类型。FP延迟与吞吐量,以及依赖链。链接到Agner Fog的网站(优化的必读资料)。
通过修复以防止优化掉来使编译器进行优化的实验。最佳结果是自动向量化(无源代码更改):gcc:比最佳向量化循环慢一半。clang:与手动向量化循环速度相同。
关于为什么使用-O0
时更大的表达式会带来性能优势的一些评论。
源代码更改以在不使用-ffast-math
的情况下获得良好性能,使代码更接近我们希望编译器执行的方式。还有一些在实际环境中无用的规则法律概念。
使用GCC架构中性向量化循环,以查看自动向量化编译器在性能上与理想的汇编代码相比有多接近(因为我检查了编译器的输出)。
我认为这个任务的重点是通过使用没有编译器优化的C语言来教授汇编语言性能优化。这很愚蠢。它混淆了编译器在现实生活中为你做的事情和需要在源代码级别进行更改的事情。
参见
为什么clang在-O0(对于这个简单的浮点数求和)时会产生低效的汇编代码?
-O0
不仅仅是“不进行优化”,它使编译器在每个语句之后将变量存储到内存中,而不是保留在寄存器中。它这样做是为了在使用gdb设置断点并修改C变量的内存值时获得“预期”的结果。甚至在同一个函数中jump
到另一行时也是如此。因此,每个C语句都必须编译为一个独立的汇编块,该块的起始和结束都包含所有变量在内存中的状态。对于像gcc这样的现代可移植编译器来说,它已经通过多个内部表示形式从源代码到汇编代码的过程中进行了转换,-O0
的这一部分需要明确地将其数据流图重新优化回独立的C语句。这些存储/加载操作会延长每个循环传递的依赖链,因此对于循环计数器保留在内存中的小循环来说是非常糟糕的(例如,对于inc reg
每次迭代1个周期,而对于inc [mem]
每次迭代6个周期,这在紧密循环中会创建循环计数器更新的瓶颈)。
使用gcc -O0
,register
关键字允许gcc将变量保存在寄存器中而不是内存中,因此在紧密循环中可能会产生很大的差异(在Godbolt编译器探索器上的示例)。但这仅适用于-O0
。在实际代码中,register
是无意义的:编译器会尝试最优地使用可用的寄存器来存储变量和临时值。register
在ISO C++11中已经被弃用(但不包括C11),有一个提案将其从语言中移除,以及其他过时的东西,如三字符。
当涉及到额外的变量时,-O0
对数组索引的影响要比指针递增更大一些。
数组索引通常使代码更易读。编译器有时无法优化像
array[i*width + j*width*height]
这样的代码,所以将源代码更改为执行
强度降低优化,将乘法转换为
+=
加法是一个好主意。
在汇编级别上,数组索引与指针递增的性能几乎相同。(例如,x86具有像
[rsi + rdx*4]
这样的寻址模式,与
[rdi]
一样快。
除了Sandybridge及更高版本。)编译器的工作是通过使用指针递增来优化代码,即使源代码使用数组索引,当这样做更快时。
为了获得良好的性能,您必须了解编译器能够做什么和不能做什么。有些优化是“脆弱”的,对源代码进行一个看似无害的小改动就会阻止编译器执行某些必要的优化,以使某些代码运行更快。(例如,将常量计算从循环中提取出来,或者证明不同的分支条件如何相互关联并简化代码。)
除此之外,这个示例很糟糕,因为它没有任何东西可以阻止一个聪明的编译器将整个东西优化掉。它甚至没有打印出总和。即使是使用
gcc -O1
(而不是
-O3
),也会丢弃一些循环。
(你可以通过在最后打印
sum
来修复这个问题。gcc和clang似乎没有意识到
calloc
返回的是零内存,并将其优化为
0.0
。请参见下面的代码。)
通常情况下,你会将代码放在一个函数中,并从另一个文件的
main()
中的循环中调用它。并且分别编译它们,不进行整个程序跨文件的优化,这样编译器就不能根据你调用它时的编译时常量进行优化。将重复循环紧密包裹在实际数组循环周围会对gcc的优化器造成混乱(请参见下面的内容)。
此外,这个问题的另一个版本存在一个未初始化的变量。看起来
long int help
是由那个问题的提问者引入的,而不是教授。所以我将把我的“完全胡说八道”降级为“愚蠢”,因为代码甚至没有在最后打印结果。这是在微基准测试中防止编译器将所有内容优化掉的最常见方法。
我猜你的教授提到了一些关于性能的事情。在这里可能有很多不同的因素,其中很多我猜在二年级的计算机科学课上没有提到。
除了使用OpenMP进行多线程处理,还可以使用SIMD进行向量化。还有一些针对现代流水线CPU的优化方法:具体来说,要避免长的依赖链。
进一步的必读资料:
- 优化C和x86汇编的
Agner Fog指南。其中一些内容适用于所有CPU。
-
每个程序员都应该了解的内存知识。
你的编译器手册也是必不可少的,特别是对于浮点数代码。浮点数具有有限的精度,并且不是关联的。最终的求和结果取决于你进行加法的顺序。通常舍入误差的差异很小,所以如果你使用
-ffast-math
来允许编译器重新排序,它可以获得很大的加速效果。
不仅仅是展开,而是像你在sum0..sum9展开的那样,保留多个累加器,只在最后加起来。浮点指令具有中等延迟但高吞吐量,因此您需要保持多个浮点操作以保持浮点执行单元的饱和。
如果您需要在下一个操作开始之前完成上一个操作的结果,那么您受到延迟的限制。对于浮点加法,每3个周期只能进行一次。在Intel Sandybridge、IvB、Haswell和Broadwell中,FP加法的吞吐量为每个周期一次。因此,您需要至少保持3个可以同时进行的独立操作以饱和机器。对于Skylake来说,每个周期是2个,延迟为4个时钟周期。 (对于Skylake来说,好消息是FMA的延迟降低到4个周期。)
在这种情况下,还有一些基本的东西,比如从循环中提取出来的东西,例如
help += ARRAY_SIZE
。
编译器选项
让我们先看看编译器能为我们做些什么。
我从原始的内部循环开始,只是将help += ARRAY_SIZE
提取出来,并在最后添加了一个printf
,这样gcc就不会将所有东西都优化掉。让我们尝试一些编译器选项,看看我们可以在gcc 4.9.2上实现什么(在我的i5 2500k Sandybridge上。最大睿频3.8GHz(轻微超频),持续3.3GHz(对于这个短期基准测试来说不相关)):
gcc -O0 fast-loop-cs201.c -o fl
: 16.43秒 性能简直是个笑话。每次操作后,变量都会存储到内存中,然后在下一次操作之前重新加载。这是一个瓶颈,会增加很多延迟。更不用说错过了实际的优化了。使用-O0
来计时/调整代码是没有用的。
-O1
: 4.87秒
-O2
: 4.89秒
-O3
: 2.453秒(使用SSE同时处理2个。当然,我使用的是64位系统,所以对-msse2
的硬件支持是基准。)
-O3 -ffast-math -funroll-loops
: 2.439秒
-O3 -march=sandybridge -ffast-math -funroll-loops
: 1.275秒(使用AVX同时处理4个。)
-Ofast ...
: 没有收益
-O3 -ftree-parallelize-loops=4 -march=sandybridge -ffast-math -funroll-loops
: 0m2.375s 实际时间,0m8.500s 用户时间。看起来锁的开销太大了。它只会生成4个线程,但内部循环太短,无法获得胜利:它每次都会收集总和,而不是给每个线程外部循环迭代的1/4。
-Ofast -fprofile-generate -march=sandybridge -ffast-math
,运行它,然后-Ofast -fprofile-use -march=sandybridge -ffast-math
:1.275秒。当您可以执行所有相关代码路径时,基于配置文件的优化是一个好主意,这样编译器可以做出更好的展开/内联决策。
clang-3.5 -Ofast -march=native -ffast-math
: 1.070秒。(clang 3.5版本太旧,不支持-march=sandybridge
。如果使用-march
来生成不需要在旧架构上运行的代码,应优先使用足够新的编译器版本。)
gcc -O3
以一种令人发笑的方式进行向量化:内部循环并行地执行外部循环的2(或4)次迭代,通过将一个数组元素广播到xmm(或ymm)寄存器的所有元素,并对其进行addpd
操作。因此,它看到相同的值被重复相加,但即使使用-ffast-math
,gcc也不能将其简化为乘法,或者交换循环。
clang-3.5的向量化效果要好得多:它向量化内部循环,而不是外部循环,因此不需要广播。它甚至将4个向量寄存器用作4个独立的累加器。它知道calloc
只返回16字节对齐的内存(在x86-64 System V上),并且在针对Sandybridge(Haswell之前)进行优化时,它知道32字节的加载在对齐错误时会有很大的惩罚。而且,由于32字节的加载在加载端口中需要2个周期,所以将它们分割开来并不太昂贵。
vmovupd -0x60(%rbx,%rcx,8),%xmm4
vinsertf128 $0x1,-0x50(%rbx,%rcx,8),%ymm4,%ymm4
这在后期的CPU上更糟糕,尤其是当数据在运行时确实对齐时;参见关于GCC版本的问题,其中
-mavx256-split-unaligned-load
在
-mtune=generic
下默认开启,详见
为什么gcc不将_mm256_loadu_pd解析为单个vmovupd?。
当我告诉它数组是对齐的时候,实际上会更
慢。(例如使用愚蠢的hack,如
array = (double*)((ptrdiff_t)array & ~31);
,它实际上会生成一条指令来屏蔽低5位,因为clang-3.5不支持gcc的
__builtin_assume_aligned
。)在这种情况下,它使用一个紧凑的循环,4倍的
vaddpd mem, %ymm, %ymm
。根据
perf
的数据,它每个周期只执行约0.65条指令(和0.93个微操作/周期),所以瓶颈不在前端。
我用调试器检查了一下,
calloc
确实返回了一个奇数倍于16的指针。(对于大内存分配,glibc倾向于分配新的页面,并将管理信息放在初始字节中,总是使得对齐超过16的边界。)因此,有一半的32B内存访问会跨越缓存行,导致速度变慢。在Sandybridge上,当指针对齐于16B但不对齐于32B时,进行两个单独的16B加载确实稍微快一些。(gcc在
-march=sandybridge
下启用
-mavx256-split-unaligned-load
和
...-store
,在默认的
-mavx
和
tune=generic
下也是如此,这对于Haswell或者编译器通常不知道对齐的内存来说不是很好。)
源代码级别的更改
从clang击败gcc可以看出,多个累加器是很好的。最明显的方法是:
for (j = 0; j < ARRAY_SIZE; j+=4) {
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个加法的依赖链,并且指令足够少,以便乱序执行硬件可以看到下一链的开始,并找到并行性以保持这些中等延迟、高吞吐量的FP执行单元的供给。
使用
-O0
,就像你愚蠢的任务要求一样,值在每个语句结束时存储到RAM中。编写更长的表达式而不更新任何变量,即使是临时变量,也会使
-O0
运行更快,但这并不是一个有用的优化。不要浪费时间在
只有对
-O0
有帮助的更改上,尤其不要以可读性为代价。
使用4个累加器变量,并且直到外部循环结束才将它们相加,这样做会使clang的自动向量化功能失效。尽管如此,它仍然只需要1.66秒的运行时间(相比于gcc的非向量化
-O2
和一个累加器需要的4.89秒)。即使对于这个源代码更改,
gcc -O2
没有使用
-ffast-math
,也只需要1.66秒的运行时间。请注意,已知ARRAY_SIZE是4的倍数,因此我没有包含任何清理代码来处理最后的最多3个元素(或者避免读取超出数组末尾的情况,这在当前写法下会发生)。这样做时很容易出错并读取超出数组末尾。
另一方面,GCC确实对此进行了向量化,但它也将内部循环悲观地(非优化地)转换为单个依赖链。我认为它再次执行了多次外部循环的迭代。
使用gcc的平台无关向量扩展,我编写了一个版本,可以编译出看似最优的代码。
#include <stdio.h>
#include <stdlib.h>
#include <stddef.h>
#include <assert.h>
#include <string.h>
#define N_TIMES 600000
#define ARRAY_SIZE 10000
int main(void)
{
double *array = calloc(ARRAY_SIZE, sizeof(double));
double sum = 0;
int i;
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;
if ( posix_memalign((void**)&aligned_array, 32, array_bytes) ) {
exit (1);
}
memcpy(aligned_array, array, array_bytes);
printf("CS201 - Asgmt 4 - I. Forgot\n");
for (i = 0; i < N_TIMES; i++) {
assert ( ARRAY_SIZE / (4*4) == (ARRAY_SIZE+15) / (4*4) );
const double *start = aligned_array;
while ( (ptrdiff_t)start & 31 ) {
sum += *start++;
}
const v4df *end = (v4df *)(aligned_array+ARRAY_SIZE);
for (const v4df *p = (v4df *)start ; p+3 < end; p+=4) {
sum0 += p[0];
sum1 += p[1];
sum2 += p[2];
sum3 += p[3];
}
help+= ARRAY_SIZE;
}
sum0 = (sum0 + sum1) + (sum2 + sum3);
sum += sum0[0] + sum0[1] + sum0[2] + sum0[3];
printf("sum = %g; help=%ld\n", sum, help);
free (aligned_array);
free (array);
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编译器探索器上。编译器选项
-xc
编译为C语言,而不是C++。内部循环从
.L3
到
jne .L3
。请参阅x86标签wiki以获取x86汇编链接。还请参阅关于SnB系列上未发生微融合的这个问题和答案,这是Agner Fog的指南没有涵盖的。)
Sandybridge的性能表现:
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
(使用更现代的perf,我会使用uops_issued.any(融合域)和uops_executed.thread(非融合域)代替r10e和r1b1。使用perf list命令查看在您的CPU上可用的事件及其描述。)
低指令每周期是L2缓存带宽的瓶颈。内部循环使用了4个独立的累加器,并且我通过gdb检查了指针的对齐。因此,缓存冲突不是问题所在。Sandybridge L2缓存每个周期可以传输32B,这可以跟上每个周期的32B浮点向量加法。但是,L2带宽无法维持在Intel SnB / Haswell / Skylake CPU上每个时钟周期的峰值1次传输。没有足够的线填充缓冲区来保持足够的缺失以维持每个周期的峰值吞吐量,或者存在其他限制因素。
从L1加载32B需要2个周期(直到Haswell,Intel才将32B加载变为单周期操作)。然而,有2个加载端口,因此持续吞吐量为每个周期32B(我们没有达到这个水平)。
性能计数器显示L1缓存命中率相当高,所以从L2到L1的硬件预取似乎在发挥作用。
每个周期0.65条指令只能达到向量FP加法器饱和的一半。
IACA表示,如果所有加载都在L1d缓存中命中,则循环每次迭代需要4个周期。即饱和加载端口和端口1(FP加法器所在位置)。
另请参阅
Sandy Bridge上的单线程内存带宽(Intel论坛帖子,讨论了限制吞吐量的因素以及
延迟 * 最大并发数
是一个可能的瓶颈。还请参阅
增强的REP MOVSB用于memcpy答案中的“延迟限制平台”部分,有关内存并发限制对于加载和存储都是一个瓶颈,但对于加载来说,
预取到L2意味着您可能不仅仅受到Line Fill缓冲区对于未完成的L1D缺失的限制。
将ARRAY_SIZE减小到1008(16的倍数),并将N_TIMES增加10倍,将运行时间缩短到0.5秒。这是每个周期1.68个指令。(内部循环总共有4个FP加法指令,因此我们最终饱和了矢量FP加法单元和加载端口。)循环分块是一个更好的解决方案,请参见下文。
Intel的CPU只有32k的L1数据缓存和L1指令缓存。我认为你的数组刚好可以放在AMD K10(Istanbul)CPU的64kiB L1D中,但无法放在Bulldozer家族(16kiB L1D)或Ryzen(32kiB L1D)中。
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)
块内,以规避规则限制。这样做仍然会执行相同数量的加法操作,但顺序更加适合缓存。
sum+=array[j]
?还有,总和始终为0
。 - twentylemonsum = 0 + 0 + 0 + 0 + 0 + 0 + 0 + 0 + 0 + 0 + 0 + 0 + 0 + 0 + 0 + 0 + 0 + 0 + 0 + 0
:-) - paxdiablo