我在2009年首先注意到GCC(至少在我的项目和我的机器上)如果我优化尺寸(-Os
)而不是速度(-O2
或-O3
),那么它倾向于产生明显更快的代码,而且我一直想知道为什么。
我设法创建(相当愚蠢)代码,显示这种令人惊讶的行为,并且足够小,无法在此处发布。
const int LOOP_BOUND = 200000000;
__attribute__((noinline))
static int add(const int& x, const int& y) {
return x + y;
}
__attribute__((noinline))
static int work(int xval, int yval) {
int sum(0);
for (int i=0; i<LOOP_BOUND; ++i) {
int x(xval+sum);
int y(yval+sum);
int z = add(x, y);
sum += z;
}
return sum;
}
int main(int , char* argv[]) {
int result = work(*argv[1], *argv[2]);
return result;
}
如果我用-Os
编译它,执行这个程序需要0.38秒,如果用-O2
或-O3
编译它需要0.44秒。这些时间一致且几乎没有噪声(gcc 4.7.2,x86_64 GNU / Linux,Intel Core i5-3320M)。
(更新:我已将所有汇编代码移至GitHub:由于fno-align-*
标志具有相同的效果,因此它们使得帖子变得臃肿并显然对问题增加了很少的价值。)
不幸的是,我对装配的理解是非常有限的,所以我不知道我接下来做了什么是正确的:我抓住-O2
的装配并将其所有差异合并到-Os
的装配中,除了.p2align
线,结果here。这段代码仍然在0.38s运行,唯一的区别是.p2align
的东西。
如果我猜对了,这些是用于堆栈对齐的填充。根据Why does GCC pad functions with NOPs?的说法,它是希望代码运行得更快,但显然这种优化在我的情况下适得其反。
在这种情况下,填充物是否是罪魁祸首?为什么以及如何?
它产生的噪声几乎使得时序微观优化变得不可能。
当我在C或C ++源代码上进行微优化(与堆栈对齐无关)时,如何确保这种偶然的幸运/不幸对齐不会干扰?
更新:
在Pascal Cuoq's answer之后,我对齐了一点点。通过将-O2 -fno-align-functions -fno-align-loops
传递给gcc,所有.p2align
都从程序集中消失,生成的可执行文件在0.38秒内运行。根据gcc documentation:
-Os启用所有-O2优化[但] -Os禁用以下优化标志:
-falign-functions -falign-jumps -falign-loops <br/> -falign-labels -freorder-blocks -freorder-blocks-and-partition <br/> -fprefetch-loop-arrays <br/>
所以,它几乎就像是一个(错误的)对齐问题。
我仍然对-march=native
建议的Marat Dukhan's answer持怀疑态度。我不相信它不只是干扰这个(错误的)对齐问题;它对我的机器完全没有影响。 (尽管如此,我还是赞成了他的答案。)
更新2:
我们可以从图片中取出-Os
。通过编译获得以下时间
-O2 -fno-omit-frame-pointer
然后在-O2 -fno-align-functions -fno-align-loops
0.37s之后手动移动-S -O2
的组件add()
0.44s在我看来,work()
与通话网站的距离非常重要。我尝试过-O2
,但add()
和perf
的输出对我来说没什么意义。但是,我只能得到一个一致的结果:
perf stat
:
perf report
对于-O2
:
602,312,864 stalled-cycles-frontend # 0.00% frontend cycles idle
3,318 cache-misses
0.432703993 seconds time elapsed
[...]
81.23% a.out a.out [.] work(int, int)
18.50% a.out a.out [.] add(int const&, int const&) [clone .isra.0]
[...]
¦ __attribute__((noinline))
¦ static int add(const int& x, const int& y) {
¦ return x + y;
100.00 ¦ lea (%rdi,%rsi,1),%eax
¦ }
¦ ? retq
[...]
¦ int z = add(x, y);
1.93 ¦ ? callq add(int const&, int const&) [clone .isra.0]
¦ sum += z;
79.79 ¦ add %eax,%ebx
对于fno-align-*
:
604,072,552 stalled-cycles-frontend # 0.00% frontend cycles idle
9,508 cache-misses
0.375681928 seconds time elapsed
[...]
82.58% a.out a.out [.] work(int, int)
16.83% a.out a.out [.] add(int const&, int const&) [clone .isra.0]
[...]
¦ __attribute__((noinline))
¦ static int add(const int& x, const int& y) {
¦ return x + y;
51.59 ¦ lea (%rdi,%rsi,1),%eax
¦ }
[...]
¦ __attribute__((noinline))
¦ static int work(int xval, int yval) {
¦ int sum(0);
¦ for (int i=0; i<LOOP_BOUND; ++i) {
¦ int x(xval+sum);
8.20 ¦ lea 0x0(%r13,%rbx,1),%edi
¦ int y(yval+sum);
¦ int z = add(x, y);
35.34 ¦ ? callq add(int const&, int const&) [clone .isra.0]
¦ sum += z;
39.48 ¦ add %eax,%ebx
¦ }
在缓慢的情况下,看起来我们正在停止对-fno-omit-frame-pointer
的调用。
我检查了 404,625,639 stalled-cycles-frontend # 0.00% frontend cycles idle
10,514 cache-misses
0.375445137 seconds time elapsed
[...]
75.35% a.out a.out [.] add(int const&, int const&) [clone .isra.0] ¦
24.46% a.out a.out [.] work(int, int)
[...]
¦ __attribute__((noinline))
¦ static int add(const int& x, const int& y) {
18.67 ¦ push %rbp
¦ return x + y;
18.49 ¦ lea (%rdi,%rsi,1),%eax
¦ const int LOOP_BOUND = 200000000;
¦
¦ __attribute__((noinline))
¦ static int add(const int& x, const int& y) {
¦ mov %rsp,%rbp
¦ return x + y;
¦ }
12.71 ¦ pop %rbp
¦ ? retq
[...]
¦ int z = add(x, y);
¦ ? callq add(int const&, int const&) [clone .isra.0]
¦ sum += z;
29.83 ¦ add %eax,%ebx
可以在我的机器上吐出的所有东西;不仅仅是上面给出的统计数据。
对于相同的可执行文件,add()
显示与执行时间的线性相关;我没有注意到任何其他与此相关的内容。 (比较perf -e
的不同可执行文件对我来说没有意义。)
我将缓存未命中列为第一条评论。我检查了stalled-cycles-frontend
可以在我的机器上测量的所有缓存未命中,而不仅仅是上面给出的。高速缓存未命中非常非常嘈杂,并且与执行时间几乎没有相关性。
默认情况下,编译器优化“平均”处理器。由于不同的处理器支持不同的指令序列,stalled-cycles-frontend
启用的编译器优化可能会使普通处理器受益,但会降低特定处理器的性能(同样适用于perf
)。如果你在不同的处理器上尝试相同的例子,你会发现其中一些受益于-O2
,而其他更有利于-Os
优化。
以下是-O2
在几个处理器上的结果(报告的用户时间):
-Os
在某些情况下,您可以通过要求time ./test 0 0
针对您的特定处理器进行优化(使用选项Processor (System-on-Chip) Compiler Time (-O2) Time (-Os) Fastest
AMD Opteron 8350 gcc-4.8.1 0.704s 0.896s -O2
AMD FX-6300 gcc-4.8.1 0.392s 0.340s -Os
AMD E2-1800 gcc-4.7.2 0.740s 0.832s -O2
Intel Xeon E5405 gcc-4.8.1 0.603s 0.804s -O2
Intel Xeon E5-2603 gcc-4.4.7 1.121s 1.122s -
Intel Core i3-3217U gcc-4.6.4 0.709s 0.709s -
Intel Core i3-3217U gcc-4.7.3 0.708s 0.822s -O2
Intel Core i3-3217U gcc-4.8.1 0.708s 0.944s -O2
Intel Core i7-4770K gcc-4.8.1 0.296s 0.288s -Os
Intel Atom 330 gcc-4.8.1 2.003s 2.007s -O2
ARM 1176JZF-S (Broadcom BCM2835) gcc-4.6.3 3.470s 3.480s -O2
ARM Cortex-A8 (TI OMAP DM3730) gcc-4.6.3 2.727s 2.727s -
ARM Cortex-A9 (TI OMAP 4460) gcc-4.6.3 1.648s 1.648s -
ARM Cortex-A9 (Samsung Exynos 4412) gcc-4.6.3 1.250s 1.250s -
ARM Cortex-A15 (Samsung Exynos 5250) gcc-4.7.2 0.700s 0.700s -
Qualcomm Snapdragon APQ8060A gcc-4.8 1.53s 1.52s -Os
或gcc
)来减轻不利优化的影响:
-mtune=native
更新:在基于Ivy Bridge的Core i3上,三个版本的-march=native
(Processor Compiler Time (-O2 -mtune=native) Time (-Os -mtune=native)
AMD FX-6300 gcc-4.8.1 0.340s 0.340s
AMD E2-1800 gcc-4.7.2 0.740s 0.832s
Intel Xeon E5405 gcc-4.8.1 0.603s 0.803s
Intel Core i7-4770K gcc-4.8.1 0.296s 0.288s
,gcc
和4.6.4
)生成具有显着不同性能的二进制文件,但汇编代码只有微妙的变化。到目前为止,我没有解释这个事实。
来自4.7.3
的集会(执行时间为0.709秒):
4.8.1
来自gcc-4.6.4 -Os
的集会(执行时间为0.822秒):
00000000004004d2 <_ZL3addRKiS0_.isra.0>:
4004d2: 8d 04 37 lea eax,[rdi+rsi*1]
4004d5: c3 ret
00000000004004d6 <_ZL4workii>:
4004d6: 41 55 push r13
4004d8: 41 89 fd mov r13d,edi
4004db: 41 54 push r12
4004dd: 41 89 f4 mov r12d,esi
4004e0: 55 push rbp
4004e1: bd 00 c2 eb 0b mov ebp,0xbebc200
4004e6: 53 push rbx
4004e7: 31 db xor ebx,ebx
4004e9: 41 8d 34 1c lea esi,[r12+rbx*1]
4004ed: 41 8d 7c 1d 00 lea edi,[r13+rbx*1+0x0]
4004f2: e8 db ff ff ff call 4004d2 <_ZL3addRKiS0_.isra.0>
4004f7: 01 c3 add ebx,eax
4004f9: ff cd dec ebp
4004fb: 75 ec jne 4004e9 <_ZL4workii+0x13>
4004fd: 89 d8 mov eax,ebx
4004ff: 5b pop rbx
400500: 5d pop rbp
400501: 41 5c pop r12
400503: 41 5d pop r13
400505: c3 ret
来自gcc-4.7.3 -Os
的集会(执行时间为0.994秒):
00000000004004fa <_ZL3addRKiS0_.isra.0>:
4004fa: 8d 04 37 lea eax,[rdi+rsi*1]
4004fd: c3 ret
00000000004004fe <_ZL4workii>:
4004fe: 41 55 push r13
400500: 41 89 f5 mov r13d,esi
400503: 41 54 push r12
400505: 41 89 fc mov r12d,edi
400508: 55 push rbp
400509: bd 00 c2 eb 0b mov ebp,0xbebc200
40050e: 53 push rbx
40050f: 31 db xor ebx,ebx
400511: 41 8d 74 1d 00 lea esi,[r13+rbx*1+0x0]
400516: 41 8d 3c 1c lea edi,[r12+rbx*1]
40051a: e8 db ff ff ff call 4004fa <_ZL3addRKiS0_.isra.0>
40051f: 01 c3 add ebx,eax
400521: ff cd dec ebp
400523: 75 ec jne 400511 <_ZL4workii+0x13>
400525: 89 d8 mov eax,ebx
400527: 5b pop rbx
400528: 5d pop rbp
400529: 41 5c pop r12
40052b: 41 5d pop r13
40052d: c3 ret
我的同事帮助我找到了一个可信的答案。他注意到了256字节边界的重要性。他没有在这里注册,并鼓励我自己发布答案(并取得所有成名)。
简短回答:
在这种情况下,填充物是否是罪魁祸首?为什么以及如何?
这一切都归结为对齐。对齐会对性能产生重大影响,这就是我们首先使用gcc-4.8.1 -Os
标志的原因。
我已提交00000000004004fd <_ZL3addRKiS0_.isra.0>:
4004fd: 8d 04 37 lea eax,[rdi+rsi*1]
400500: c3 ret
0000000000400501 <_ZL4workii>:
400501: 41 55 push r13
400503: 41 89 f5 mov r13d,esi
400506: 41 54 push r12
400508: 41 89 fc mov r12d,edi
40050b: 55 push rbp
40050c: bd 00 c2 eb 0b mov ebp,0xbebc200
400511: 53 push rbx
400512: 31 db xor ebx,ebx
400514: 41 8d 74 1d 00 lea esi,[r13+rbx*1+0x0]
400519: 41 8d 3c 1c lea edi,[r12+rbx*1]
40051d: e8 db ff ff ff call 4004fd <_ZL3addRKiS0_.isra.0>
400522: 01 c3 add ebx,eax
400524: ff cd dec ebp
400526: 75 ec jne 400514 <_ZL4workii+0x13>
400528: 89 d8 mov eax,ebx
40052a: 5b pop rbx
40052b: 5d pop rbp
40052c: 41 5c pop r12
40052e: 41 5d pop r13
400530: c3 ret
。事实证明,默认行为是“我们默认情况下将循环对齐到8字节,但如果我们不需要填充超过10个字节,请尝试将其对齐到16字节。”显然,在这种特殊情况下和我的机器上,这个默认值不是最佳选择。使用-falign-*
的Clang 3.4(trunk)进行了适当的对齐,生成的代码没有显示出这种奇怪的行为。
当然,如果进行了不恰当的对齐,则会使事情变得更糟。不必要/错误的对齐只是无缘无故地占用字节,并可能增加缓存未命中等。
它产生的噪声几乎使得时序微观优化变得不可能。
当我对C或C ++源代码进行微优化(与堆栈对齐无关)时,如何确保这种意外的幸运/不幸对齐不会干扰?
只需告诉gcc做正确的对齐:
a (bogus?) bug report to the gcc developers
答案很长:
如果:
-O3
字节边界在中间削减g++ -O2 -falign-functions=16 -falign-loops=16
(XX
是机器依赖的)。add()
的调用必须跳过XX
字节边界并且目标未对齐。add()
不对齐。前2个在XX
的代码和结果上非常明显。在这种情况下,add()
(执行0.994秒):
Marat Dukhan kindly posted
一个256字节的边界在中间切割gcc-4.8.1 -Os
,00000000004004fd <_ZL3addRKiS0_.isra.0>:
4004fd: 8d 04 37 lea eax,[rdi+rsi*1]
400500: c3
和循环都没有对齐。惊喜,惊喜,这是最慢的情况!
在add()
(在0.822秒内执行)的情况下,256字节边界仅切入冷段(但是没有循环,也没有切割add()
):
gcc-4.7.3 -Os
没有任何对齐,并且对add()
的调用必须跳过256字节边界。这段代码是第二慢的。
在00000000004004fa <_ZL3addRKiS0_.isra.0>:
4004fa: 8d 04 37 lea eax,[rdi+rsi*1]
4004fd: c3 ret
[...]
40051a: e8 db ff ff ff call 4004fa <_ZL3addRKiS0_.isra.0>
(在0.709秒内执行)的情况下,虽然没有对齐,但是对add()
的调用不必跳过256字节边界并且目标正好在32字节之外:
gcc-4.6.4 -Os
这是三者中最快的。为什么256字节边界在他的机器上是特殊的,我将由他来决定它。我没有这样的处理器。
现在,在我的机器上,我没有得到这个256字节的边界效果。只有功能和循环对齐才能在我的机器上启动。如果我通过add()
然后一切都恢复正常:我总是得到最快的情况,时间对 4004f2: e8 db ff ff ff call 4004d2 <_ZL3addRKiS0_.isra.0>
4004f7: 01 c3 add ebx,eax
4004f9: ff cd dec ebp
4004fb: 75 ec jne 4004e9 <_ZL4workii+0x13>
旗不再敏感。我可以通过g++ -O2 -falign-functions=16 -falign-loops=16
或任何16的倍数,代码也不敏感。
我在2009年首先注意到gcc(至少在我的项目和我的机器上)如果我优化尺寸(-Os)而不是速度(-O2或-O3),我倾向于产生明显更快的代码,我一直在想从那以后。
一个可能的解释是我有热点对齐对象,就像本例中的热点一样。通过弄乱旗帜(通过-fno-omit-frame-pointer
而不是g++ -O2 -falign-functions=32 -falign-loops=32
),这些热点偶然以幸运的方式对齐,代码变得更快。它与优化尺寸无关:这些都是由于热点事故变得更加紧密。从现在开始,我将检查对齐对我的项目的影响。
哦,还有一件事。这样的热点如何出现,如示例中所示?像-Os
这样的小功能的内联如何失败?
考虑一下:
-O2
并在一个单独的文件中:
add()
编译为:// add.cpp
int add(const int& x, const int& y) {
return x + y;
}
。
gcc不会内联// main.cpp
int add(const int& x, const int& y);
const int LOOP_BOUND = 200000000;
__attribute__((noinline))
static int work(int xval, int yval) {
int sum(0);
for (int i=0; i<LOOP_BOUND; ++i) {
int x(xval+sum);
int y(yval+sum);
int z = add(x, y);
sum += z;
}
return sum;
}
int main(int , char* argv[]) {
int result = work(*argv[1], *argv[2]);
return result;
}
!
就是这样,很容易无意中创建像OP中那样的热点。当然这部分是我的错:gcc是一个优秀的编译器。如果编译上面为:g++ -O2 add.cpp main.cpp
,也就是说,如果我执行链接时优化,代码运行在0.19s!
(在OP中人为禁用内联,因此,OP中的代码慢了2倍)。
我正在添加这个后接受指出,已经研究了对齐对程序整体性能的影响 - 包括大的程序。例如,add()
(我相信它的一个版本也出现在CACM中)显示了链接顺序和操作系统环境大小变化如何足以显着改变性能。他们将此归因于“热循环”的对齐。
本文的标题是“制作错误的数据而不做任何明显错误的事情!”他说,由于程序运行环境中几乎无法控制的差异而导致的无意的实验偏差可能会使许多基准测试结果变得毫无意义。
我认为你在同一个观察中遇到了不同的角度。
对于性能关键代码,对于在安装或运行时评估环境并在不同优化版本的关键例程中选择本地最佳的系统,这是一个非常好的论据。
我认为你可以获得与你所做的相同的结果:
我抓住-O2的程序集并将其所有差异合并到除-p2align行之外的-Os的程序集中:
...通过使用g++ -O2 -flto add.cpp main.cpp
。我一直在用这些选项编译所有内容,这些选项在每次我费心测量时都比普通的this article快15年。
此外,对于完全不同的上下文(包括不同的编译器),我注意到-O2 -falign-functions=1 -falign-jumps=1 -falign-loops=1 -falign-labels=1
:应该“优化代码大小而不是速度”的选项优化代码大小和速度。
如果我猜对了,这些是用于堆栈对齐的填充。
不,这与堆栈无关,默认情况下生成的NOP以及选项-falign - * = 1 prevent用于代码对齐。
根据为什么GCC垫功能与NOP?它是希望代码运行得更快,但显然这种优化在我的情况下适得其反。
在这种情况下,填充物是否是罪魁祸首?为什么以及如何?
填充物很可能是罪魁祸首。填充被认为是必要的并且在某些情况下有用的原因是代码通常以16字节的行提取(有关详细信息,请参阅-O2
,这取决于处理器的型号)。在16字节边界上对齐函数,循环或标签意味着在统计上增加的机会是需要少一行来包含函数或循环。显然,它会因为这些NOP降低代码密度并因此降低缓存效率而适得其反。在循环和标签的情况下,NOP甚至可能需要执行一次(当执行正常到达循环/标签时,而不是从跳转)。
如果你的程序受到CODE L1缓存的限制,那么优化大小突然开始付出代价。
当我最后检查时,编译器不够智能,无法在所有情况下解决这个问题。
在您的情况下,-O3可能会为两个缓存行生成足够的代码,但-Os适合一个缓存行。
我不是这方面的专家,但我似乎记得现代处理器在the situation is similar方面非常敏感。用于预测分支的算法(或者至少在我编写汇编代码的时候回归)基于代码的几个属性,包括目标的距离和方向。
想到的场景是小循环。当分支向后移动并且距离不是太远时,分支预测正在针对这种情况进行优化,因为所有小循环都是以这种方式完成的。当您在生成的代码中交换Agner Fog's optimization resources和branch prediction的位置或两者的位置稍有变化时,相同的规则可能会发挥作用。
也就是说,我不知道如何验证,我只是想让你知道这可能是你想要研究的东西。