bounty将在6天后过期。回答此问题可获得+500声望奖励。Matthieu希望奖励现有回答:我希望答案能那么详细和彻底...
我需要在不使用编译器优化标志的情况下优化一些for循环以提高速度(用于学校作业)。
给定一个特定的Linux服务器(由学校拥有),一个令人满意的改进是让它运行在7秒以内,一个很大的改进是让它运行在5秒以内。我这里的代码运行了大约5.6秒。我想我可能需要以某种方式使用指针来让它运行得更快,但我不是很确定。我有什么选择?
文件必须保持50行或更少(不包括注解)。
#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;
}
3条答案
按热度按时间gwbalxhn1#
重新发布了我的optimized sum of an array of doubles in C答案的修改版本,因为该问题被投票否决为-5。另一个问题的操作员更倾向于“还有什么可能”,所以我相信了他的话,并对当前CPU硬件的矢量化和调优进行了信息转储。:)
那个问题的操作员最终说他不允许使用高于
-O0
的编译器选项,我猜这里也是这样。总结:
***为什么使用
-O0
会歪曲事实(不公平地惩罚了在普通代码中对普通编译器来说很好的东西)。**使用-O0
(gcc/clang的默认值),以便您的循环不会被优化掉,这不是一个有效的借口,也不是一个有用的方法来找出在启用正常优化的情况下什么会更快。(另请参阅 * Idiomatic way of performance evaluation? *,了解更多关于基准测试方法和缺陷的信息,例如如何启用优化,但仍阻止编译器优化掉您想要测量的工作。)-O0
只有一些评论。-ffast-math
的情况下获得良好的性能,使代码更接近我们希望编译器做的事情。我认为这个任务的重点是教汇编语言使用C语言进行性能优化,而没有编译器优化。这很愚蠢。它把编译器在真实的生活中为你做的事情和 * 确实 * 需要源代码级别更改的事情混在一起。
请参阅Why does clang produce inefficient asm with -O0 (for this simple floating point sum)?
-O0
不仅仅是“没有优化,”它使编译器在每条语句后将变量存储到内存中,而不是将它们保存在寄存器中。2这样做的目的是,如果你用gdb设置断点并 * 修改 * 值,你会得到“预期”的结果(在内存中)的一个C变量.或者即使你jump
到同一函数中的另一行。因此每个C语句都必须编译成一个独立的asm块,该块以内存中的所有变量开始和结束。对于像gcc这样的现代可移植编译器,它已经在从源代码到asm的过程中通过程序流的多个内部表示进行转换,-O0
的这一部分需要显式地将其数据流图 * 去优化 * 回单独的C语句。这些存储/重载会延长每个循环携带的依赖链,因此如果循环计数器保存在内存中,对于小循环来说是可怕的。(例如,对于inc reg
,每次迭代1个周期,而对于inc [mem]
,每次迭代6个周期,这在紧密循环中的循环计数器更新上产生了瓶颈)。在
gcc -O0
中,register
关键字让gcc将var保存在寄存器中而不是内存中,因此在紧循环(Example on the Godbolt Compiler explorer)中会有很大的不同。但这只是在-O0
中。在真实的代码中,register
是没有意义的:编译器尝试最佳地使用可用的寄存器来存储变量和临时变量。register
在ISO C++11(但不是C11)中已经被弃用,there's a proposal to remove it from the language和其他过时的东西(如三合字)沿着被弃用。由于涉及到额外的变量,
-O0
对数组索引的损害比指针递增多一点。数组索引通常使代码更容易阅读。编译器有时无法优化像
array[i*width + j*width*height]
这样的东西,所以改变源代码来做 * 强度降低 * 优化将乘法转换为+=
加法是个好主意。在asm级别,数组索引与指针递增的性能接近。(例如,x86具有
[rsi + rdx*4]
这样的寻址模式,其速度与[rdi]
. except on Sandybridge and later一样快。)编译器的工作是通过使用指针递增来优化代码,即使源代码使用数组索引,如果这样做更快的话。为了获得良好的性能,你必须知道编译器可以做什么和不能做什么。有些优化是“脆弱的”,对源代码的一个看似无害的小改动就会阻止编译器进行对某些代码快速运行至关重要的优化。(例如,从循环中提取常量计算,或者证明不同分支条件之间的关系,以及简化。)
除此之外,它还是一个垃圾示例,因为它没有任何东西可以阻止一个聪明的编译器优化整个过程。它甚至没有打印总和。甚至
gcc -O1
(而不是-O3
)也丢弃了一些循环。(You gcc和clang似乎没有意识到
calloc
返回的内存为零,并将其优化为0.0
。请参阅下面的代码。)通常你会把你的代码放在一个函数中,然后在另一个文件的
main()
中的一个循环中调用它。然后分别编译它们,而不进行整个程序的跨文件优化,所以编译器不能根据你调用它时使用的编译时常量进行优化。repeat-loop被紧紧地包裹在数组上的实际循环周围,这对gcc的优化器造成了严重的破坏(见下文)。另外,这个问题的另一个版本有一个未初始化的变量。看起来
long int help
是由那个问题的操作员引入的,而不是教授。所以我将不得不把我的“完全胡说八道”降级为仅仅是“愚蠢”,因为代码在最后都没有输出结果。这是让编译器在这样的微基准测试中不优化所有内容的最常用方法。我想你的教授提到了一些关于表现的事情。这里有很多不同的事情可以发挥作用,其中很多我想在二年级的CS课程中没有提到。
除了使用openmp进行多线程处理外,还使用SIMD进行矢量化。此外,还针对现代流水线CPU进行了优化:具体地说,避免具有一个长相关性链。
进一步的基本阅读:
你的编译器手册也是必不可少的,特别是对于浮点代码。浮点有有限的精度,并且 * 不是 * 关联的。最终的和**取决于你做加法的顺序。通常舍入误差的差别很小,所以如果你使用
-ffast-math
允许的话,编译器可以通过重新排序来获得很大的加速。keep multiple accumulators which you only add up at the end不像
sum0
..sum9
那样只进行展开,而是以10为单位展开。FP指令具有中等延迟,但吞吐量较高,因此需要保持多个FP操作处于运行状态,以使浮点执行单元保持饱和状态。如果您需要在下一个操作开始之前完成最后一个操作的结果,则会受到延迟的限制。对于FP add,这是每3个周期一个。在英特尔Sandybridge、IvB、Haswell和Broadwell中,FP add的吞吐量是每个周期一个。因此,您需要至少保持3个可以同时运行的独立操作,以使机器饱和。For Skylake,它是2 per cycle with latency of 4 clocks。(Skylake的优点是,FMA的延迟降低到4个周期。)
在这种情况下,还有一些基本的东西,比如从循环中取出一些东西,例如
help += ARRAY_SIZE
。编译器选项
让我们先来看看编译器能为我们做些什么。
我从最初的内部循环开始,只取出了
help += ARRAY_SIZE
,并在最后添加了一个printf
,这样gcc就不会优化所有内容。让我们尝试一些编译器选项,看看我们可以使用gcc 4.9.2实现什么(在我的i5 2500k Sandybridge上,3.8GHz最大加速(轻微OC),3.3GHz持续(与这个简短的基准测试无关)):gcc -O0 fast-loop-cs201.c -o fl
:16.43s性能完全是个笑话。变量在每次操作后都存储到内存中,并在下一次操作前重新加载。这是一个瓶颈,并增加了大量的延迟。更不用说失去了实际的优化。使用-O0
对代码进行计时/调优是没有用的。-O1
:4.87秒-O2
:4.89秒-O3
:2.453s(使用SSE一次执行2个任务。当然,我使用的是64位系统,因此对-msse2
的硬件支持是基线。)-O3 -ffast-math -funroll-loops
:2.439秒-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真实的,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 3.5版本太旧,不支持-march=sandybridge
。您应该更喜欢使用足够新的编译器版本,以了解您正在调整的目标架构,特别是如果使用-march
生成不需要在旧架构上运行的代码。)gcc -O3
以一种有趣的方式进行矢量化:内部循环并行执行外部循环的2次(或4次)迭代,方法是将一个数组元素广播给xmm(或ymm)寄存器的所有元素,并对该元素执行addpd
。因此,它看到相同的值被重复相加,但即使是-ffast-math
也不会让gcc将其转换为乘法,或者切换循环。clang-3.5 vectorizes a lot better: it vectorizes the inner loop, instead of the outer, so it doesn't need to broadcast. It even uses 4 vector registers as 4 separate accumulators. It knows that
calloc
only returns 16-byte aligned memory (on x86-64 System V), and when tuning for Sandybridge (before Haswell) it knows that 32-byte loads have a big penalty when misaligned. And that splitting them isn't too expensive since a 32-byte load takes 2 cycles in a load port anyway.This is worse on later CPUs, especially when the data does happen to be aligned at run-time; see Why doesn't gcc resolve _mm256_loadu_pd as single vmovupd? about GCC versions where
-mavx256-split-unaligned-load
was on by default with-mtune=generic
.It's actually slower when I tell it that the array is aligned. (with a stupid hack like
array = (double*)((ptrdiff_t)array & ~31);
which actually generates an instruction to mask off the low 5 bits, because clang-3.5 doesn't support gcc's__builtin_assume_aligned
.) In that case it uses a tight loop of 4xvaddpd mem, %ymm, %ymm
. It only runs about 0.65 insns per cycle (and 0.93 uops / cycle), according toperf
, so the bottleneck isn't front-end.I checked with a debugger, and
calloc
is indeed returning a pointer that's an odd multiple of 16. (glibc for large allocations tends to allocate new pages, and put bookkeeping info in the initial bytes, always misaligning to any boundary wider than 16.) So half the 32B memory accesses are crossing a cache line, causing a big slowdown. It is slightly faster to do two separate 16B loads when your pointer is 16B-aligned but not 32B-aligned, on Sandybridge. (gcc enables-mavx256-split-unaligned-load
and...-store
for-march=sandybridge
, and also for the default tune=generic with-mavx
, which is not so good especially for Haswell or with memory that's usually aligned by the compiler doesn't know about it.)Source level changes
As we can see from clang beating gcc, multiple accumulators are excellent. The most obvious way to do this would be:
and then don't collect the 4 accumulators into one until after the end of the outer loop.
Your (from the other question) source change of
actually has a similar effect, thanks to out-of-order execution. Each group of 10 is a separate dependency chain. order-of-operations rules say the
j
values get added together first, and then added tosum
. So the loop-carried dependency chain is still only the latency of one FP add, and there's lots of independent work for each group of 10. Each group is a separate dependency chain of 9 adds, and takes few enough instructions for the out-of-order execution hardware to see the start of the next chain and, and find the parallelism to keep those medium latency, high throughput FP execution units fed.With
-O0
, as your silly assignment apparently requires, values are stored to RAM at the end of every statement. Writing longer expressions without updating any variables, even temporaries, will make-O0
run faster, but it's not a useful optimisation. Don't waste your time on changes that only help with-O0
, esp. not at the expense of readability.Using 4 accumulator variables and not adding them together until the end of the outer loop defeats clang's auto-vectorizer. It still runs in only 1.66s (vs. 4.89 for gcc's non-vectorized
-O2
with one accumulator). Evengcc -O2
without-ffast-math
also gets 1.66s for this source change. Note that ARRAY_SIZE is known to be a multiple of 4, so I didn't include any cleanup code to handle the last up-to-3 elements (or to avoid reading past the end of the array, which would happen as written now). It's really easy to get something wrong and read past the end of the array when doing this.GCC, on the other hand, does vectorize this, but it also pessimises (un-optimises) the inner loop into a single dependency chain. I think it's doing multiple iterations of the outer loop, again.
Using gcc's platform-independent vector extensions, I wrote a version which compiles into apparently-optimal code:
The inner loop compiles to:
(For more, see online compiler output at the godbolt compiler explorer. The
-xc
compiler option compiles as C, not C++. The inner loop is from.L3
tojne .L3
. See the x86 tag wiki for x86 asm links. See also this q&a about micro-fusion not happening on SnB-family , which Agner Fog's guides don't cover).performance:
I still don't know why it's getting such low instructions per cycle. The inner loop is using 4 separate accumulators, and I checked with gdb that the pointers are aligned. So cache-bank conflicts shouldn't be the problem. Sandybridge L2 cache can sustain one 32B transfers per cycle, which should keep up with the one 32B FP vector add per cycle.
32B loads from L1 take 2 cycles (it wasn't until Haswell that Intel made 32B loads a single-cycle operation). However, there are 2 load ports, so the sustained throughput is 32B per cycle (which we're not reaching).
也许加载需要在使用之前进行流水线操作,以最大限度地减少加载暂停时ROB(重新排序缓冲区)被填满得情况?但是性能计数器显示一级缓存命中率相当高,因此从二级缓存到一级缓存得硬件预取似乎已经完成了它得工作.
0.65指令的循环周期数仅达到矢量FP加法器饱和的一半。这是令人沮丧的。即使IACA也说循环每次迭代应运行4个周期。(即,使加载端口和端口1(FP加法器所在的端口)饱和):/
更新:我猜L2带宽终究是问题所在。没有足够的行填充缓冲区来保持足够的未命中,以维持每个周期的峰值吞吐量。L2持续带宽低于英特尔SnB / Haswell / Skylake CPU的峰值带宽。
另请参阅Single Threaded Memory Bandwidth on Sandy Bridge(英特尔论坛线程,其中有很多关于什么限制了吞吐量以及
latency * max_concurrency
如何成为一个可能的瓶颈的讨论。另请参阅“延迟受限平台”部分Enhanced REP MOVSB for memcpy的答案有限的内存并发是加载和存储的瓶颈,但对于加载prefetch into L2 does mean you might not be limited purely by Line Fill buffers for outstanding L1D misses。将ARRAY_SIZE减少到1008(16的倍数),并将N_TIMES增加10倍,使运行时间减少到0.5秒。即每个周期1.68秒。(内部循环总共有7条指令用于4次FP加法,因此我们最终使向量FP加法单元和加载端口饱和。)循环平铺是一个更好的解决方案,请参见下文。
英特尔CPU只有32 k的L1数据和L1指令缓存。我认为你的阵列只能勉强适应64kiB L1D on an AMD K10 (Istanbul) CPU,但不能适应Bulldozer-family (16kiB L1D)或Ryzen(32 kiB L1 D)。
Gcc试图通过将相同的值广播到并行加法中来进行矢量化,这看起来并不疯狂。如果它成功地做到了这一点(使用多个累加器来隐藏延迟),那么它就可以用一半的内存带宽来饱和矢量FP加法器。照目前的情况看,这几乎是一场失败,可能是因为广播的开销。
另外,这也很愚蠢。
N_TIMES
只是一个简单的重复。我们实际上并不想为了多次完成相同的工作而进行优化。除非我们想在这样愚蠢的任务中获胜。一个源代码级的方法是在允许修改的代码部分增加i
:更实际地说,为了处理这个问题,您可以交换循环(在数组上循环一次,将每个值相加N_TIMES次)。我想我读到过英特尔的编译器有时会为您做这件事。
一种更通用的技术称为缓存分块或循环平铺。其思想是在适合缓存的小块中处理输入数据。根据您的算法,可以在一个块上执行不同阶段的操作,然后在下一个块上重复,而不是让每个阶段循环处理整个输入。与往常一样,一旦你知道了一个技巧的正确名称(并且它确实存在),你就可以在谷歌上搜索到大量的信息。
你可以用自己的方式在
if (i == 0)
块中允许修改的代码部分放置一个可交换的循环,它仍然会做同样数量的加法,但是以一个更优化缓存的顺序。aiazj4mn2#
你 * 可能 * 是在正确的轨道上,尽管你需要测量它来确定(我通常的建议是 * 测量,而不是猜测 * 在这里似乎有点多余,因为整个 * 点 * 的任务是测量)。
优化编译器可能不会看到太大的差异,因为他们在这方面很聪明,但是,由于我们不知道它将在什么优化水平上编译,你可能会得到实质性的改进。
要在内部循环中使用指针,只需首先添加一个指针变量:
然后将循环更改为:
这使得循环中的加法数量保持不变(当然,假设您将
+=
和++
作为加法运算符),但基本上使用指针而不是数组索引。在我的系统上没有优化1的情况下,它从9.868秒(CPU时间)下降到4.84秒。
1* 对于 * 优化级别
-O3
,* 两者 * 都被报告为花费0.001秒,因此,如前所述,优化器非常聪明。然而,考虑到您看到的是5+秒,我建议它没有在优化打开的情况下编译。顺便说一句,这就是为什么通常建议以可读的方式编写代码并让编译器负责让它运行得更快的一个很好的原因。虽然我在优化方面的微薄尝试大约使速度增加了一倍,但使用
-O3
使它运行得快了 * 一万 * 倍:-)yx2lnoni3#
在做其他事情之前,试着改变编译器的设置以产生更快的代码。有一般的优化,编译器可能会自动矢量化。
你总是会做的是尝试几种方法,并检查什么是最快的。作为一个目标,尝试达到一个周期,每次添加或更好。
每个循环的迭代次数:你同时加10个和。可能是你的处理器没有足够的寄存器,或者它有更多的寄存器。我会测量每个循环4,5,6,7,8,9,10,11,12,13,14个和的时间。
总和数目:有一个以上的和意味着延迟不会影响你,只有吞吐量。但是超过4个或6个可能没有帮助。尝试4个和,每个循环4、8、12、16次迭代。或者6个和,每个循环6、12、18次迭代。
快取:您正在执行一个80,000字节的数组。可能比L1快取还多。请将数组分割成2或4个部分。执行一个外部循环,在两个或四个子数组上重复,下一个循环从0到N_TIMES - 1,而内部循环则将值加总。
然后,您可以尝试使用矢量运算、多线程化代码或使用GPU来完成这些工作。
如果您被迫不使用优化,那么“register”关键字实际上可能会起作用。