我选择了大卫的答案,因为他是唯一一个给出了没有优化标志的for循环的解决方案的人。
Jerry Coffin的回答解释了在为这个例子设置优化标志时会发生什么。仍然没有答案的是,当B为每次迭代执行一个额外的内存引用和一个加法时,为什么superCalculationA比superCalculationB运行得慢。Nemo的帖子显示了汇编器的输出。我在我的PC上用-S
标志确认了这一编译,2.9GHz桑迪桥(i5-2310),运行Ubuntu 12.04 64位,由Matteo Italia建议。
我在试验for循环的性能时,偶然发现了以下情况。
我有下面的代码,用两种不同的方式做同样的计算。
#include <cstdint>
#include <chrono>
#include <cstdio>
using std::uint64_t;
uint64_t superCalculationA(int init, int end)
{
uint64_t total = 0;
for (int i = init; i < end; i++)
total += i;
return total;
}
uint64_t superCalculationB(int init, int todo)
{
uint64_t total = 0;
for (int i = init; i < init + todo; i++)
total += i;
return total;
}
int main()
{
const uint64_t answer = 500000110500000000;
std::chrono::time_point<std::chrono::high_resolution_clock> start, end;
double elapsed;
std::printf("=====================================================\n");
start = std::chrono::high_resolution_clock::now();
uint64_t ret1 = superCalculationA(111, 1000000111);
end = std::chrono::high_resolution_clock::now();
elapsed = (end - start).count() * ((double) std::chrono::high_resolution_clock::period::num / std::chrono::high_resolution_clock::period::den);
std::printf("Elapsed time: %.3f s | %.3f ms | %.3f us\n", elapsed, 1e+3*elapsed, 1e+6*elapsed);
start = std::chrono::high_resolution_clock::now();
uint64_t ret2 = superCalculationB(111, 1000000000);
end = std::chrono::high_resolution_clock::now();
elapsed = (end - start).count() * ((double) std::chrono::high_resolution_clock::period::num / std::chrono::high_resolution_clock::period::den);
std::printf("Elapsed time: %.3f s | %.3f ms | %.3f us\n", elapsed, 1e+3*elapsed, 1e+6*elapsed);
if (ret1 == answer)
{
std::printf("The first method, i.e. superCalculationA, succeeded.\n");
}
if (ret2 == answer)
{
std::printf("The second method, i.e. superCalculationB, succeeded.\n");
}
std::printf("=====================================================\n");
return 0;
}
字符串
编译此代码时,
g++ main.cpp -o输出--std=c++11
导致以下结果:
=====================================================
Elapsed time: 2.859 s | 2859.441 ms | 2859440.968 us
Elapsed time: 2.204 s | 2204.059 ms | 2204059.262 us
The first method, i.e. superCalculationA, succeeded.
The second method, i.e. superCalculationB, succeeded.
=====================================================
型
我的第一个问题是:为什么第二个循环比第一个循环快23%?
另一方面,如果我用
g++ main.cpp -o输出--std=c++11 -O 1
结果改善了很多,
=====================================================
Elapsed time: 0.318 s | 317.773 ms | 317773.142 us
Elapsed time: 0.314 s | 314.429 ms | 314429.393 us
The first method, i.e. superCalculationA, succeeded.
The second method, i.e. superCalculationB, succeeded.
=====================================================
型
时间差几乎消失了。
但我不敢相信我的眼睛当我设置了-O2标志,
g++ main.cpp -o输出--std=c++11 -O2
得到了这个
=====================================================
Elapsed time: 0.000 s | 0.000 ms | 0.328 us
Elapsed time: 0.000 s | 0.000 ms | 0.208 us
The first method, i.e. superCalculationA, succeeded.
The second method, i.e. superCalculationB, succeeded.
=====================================================
型
所以,我的第二个问题是:当我设置-O 1和-O2标志时,编译器做了什么,导致了如此巨大的性能提升?
我检查了Optimized Option - Using the GNU Compiler Collection (GCC),但这并没有澄清事情。
顺便说一下,我正在用g++(GCC)4.9.1编译这段代码。
编辑以确认Basile Starynkevitch的假设
我编辑了代码,现在main
看起来像这样:
int main(int argc, char **argv)
{
int start = atoi(argv[1]);
int end = atoi(argv[2]);
int delta = end - start + 1;
std::chrono::time_point<std::chrono::high_resolution_clock> t_start, t_end;
double elapsed;
std::printf("=====================================================\n");
t_start = std::chrono::high_resolution_clock::now();
uint64_t ret1 = superCalculationB(start, delta);
t_end = std::chrono::high_resolution_clock::now();
elapsed = (t_end - t_start).count() * ((double) std::chrono::high_resolution_clock::period::num / std::chrono::high_resolution_clock::period::den);
std::printf("Elapsed time: %.3f s | %.3f ms | %.3f us\n", elapsed, 1e+3*elapsed, 1e+6*elapsed);
t_start = std::chrono::high_resolution_clock::now();
uint64_t ret2 = superCalculationA(start, end);
t_end = std::chrono::high_resolution_clock::now();
elapsed = (t_end - t_start).count() * ((double) std::chrono::high_resolution_clock::period::num / std::chrono::high_resolution_clock::period::den);
std::printf("Elapsed time: %.3f s | %.3f ms | %.3f us\n", elapsed, 1e+3*elapsed, 1e+6*elapsed);
std::printf("Results were %s\n", (ret1 == ret2) ? "the same!" : "different!");
std::printf("=====================================================\n");
return 0;
}
型
这些修改确实增加了计算时间,无论是-O1
还是-O2
。现在两者都给了我大约620 ms。这证明-O2确实在编译时进行了一些计算。
我仍然不明白这些标志是如何提高性能的,-Ofast
做得更好,大约320毫秒。
另外请注意,我已经改变了函数A和B的调用顺序,以测试Jerry Coffin的假设。在没有优化器标志的情况下编译这段代码,B和A的时间分别为2.2秒和2.8秒。因此,我认为这不是缓存问题。只是强调一下,我不是在谈论第一种情况下的优化(没有标志的那个),我只是想知道是什么让秒循环比第一个运行得更快。
7条答案
按热度按时间lnlaulya1#
我的直接猜测是第二个更快,不是因为对循环所做的更改,而是因为它是第二个,所以该高速缓存在运行时已经准备好了。
为了测试这个理论,我重新排列了你的代码,以颠倒调用这两个计算的顺序:
字符串
我得到的结果是:
型
所以,当版本A首先运行时,它会慢一些。当版本B首先运行时,它会慢一些。
为了确认,我在对版本A或版本B进行计时之前,添加了一个对
superCalculationB
的额外调用。之后,我尝试运行程序三次。对于这三次运行,我认为结果是平局(版本A快一次,版本B快两次,但既没有赢得依赖性,也没有获得足够大的优势,没有意义)。这并不能证明这实际上是一种缓存情况,但给予一个相当强的指示,即这是函数调用顺序的问题,而不是代码本身的差异。
至于编译器为了使代码更快而做的事情:它做的主要事情是展开循环的几次迭代。如果我们手工展开几次迭代,我们可以得到几乎相同的效果:
型
这有一个属性,有些人可能会觉得很奇怪:实际上用-O2编译比用-O3编译快。用-O2编译时,它也比用-O3编译的其他两个快五倍。
与编译器的循环展开相比,速度提高了约5倍的主要原因是我们展开了与编译器不同的循环(更智能,IMO)。我们计算
f_end
来告诉我们展开的循环应该执行多少次。我们执行这些迭代,* 然后 * 我们执行一个单独的循环来“清理”结束时的任何奇数迭代。相反,编译器生成的代码大致相当于这样的代码:
型
虽然这比循环根本没有展开时快得多,但从主循环中消除这些额外的检查并为任何奇数迭代执行单独的循环仍然快得多。
考虑到这样一个微不足道的循环体被执行了如此多的次数,你还可以通过展开更多的循环迭代来进一步提高速度(当使用-O2编译时)。展开16次迭代时,它的速度大约是上面代码展开8次迭代时的两倍:
型
我还没有尝试探索展开这个特定循环的增益极限,但是展开32次迭代几乎使速度再次翻倍。根据您使用的处理器,您可能会通过展开64次迭代获得一些小的增益,但我猜我们开始接近极限-在某个时候,性能增益可能会趋于平稳,然后(如果你展开更多的迭代)可能会下降,很可能是戏剧性的。
总结:使用
-O3
,编译器展开循环的多次迭代。在这种情况下,这是非常有效的,主要是因为我们有 * 许多 * 几乎最琐碎的循环体的执行。手动展开循环甚至比让编译器做它更有效-我们可以更智能地展开,我们可以简单地展开比编译器更多的迭代。额外的智能可以给予我们大约5:1的改进,额外的迭代可以再增加4:1左右(代价是代码更长,可读性稍差)。最后警告:和优化一样,你的收益可能会有所不同。编译器和/或处理器的差异意味着你可能会得到至少与我不同的结果。我希望我的手展开循环在大多数情况下比其他两个快得多,但具体快多少可能会有所不同。
1.但请注意,这是将使用-O2的手动展开循环与使用-O3的原始循环进行比较。当使用-O3编译时,手动展开循环运行得慢得多。
bfhwhh0e2#
检查程序集输出实际上是阐明这些问题的唯一方法。
更好的优化将做很多事情,包括不严格“符合标准”的事情(尽管,据我所知,
-O1
和-O2
不是这种情况)-例如检查,-Ofast
开关。我发现这很有帮助:http://gcc.godbolt.org/,并且使用演示代码here
bkhjykvo3#
-氧气
解释-O2结果很容易,查看从godbolt更改为-O2的代码
字符串
没有调用这两个函数,也没有比较结果。
为什么会这样呢?这当然是优化的力量,程序太简单了。
首先应用内联的力量,之后编译器可以看到所有参数实际上都是文字值(111,1000000111,100000000,50000011050000000),因此是常量。
它发现init + todo是一个循环不变量,并将它们替换为end,将end定义为end = init + todo = 111 + 1000000000 = 1000000111
现在我们知道这两个循环都只包含编译时的值。它们完全相同:
型
编译器认为它是一个求和,total是累加器,它是一个等步长的求和,所以编译器使最终的循环展开,即all,但它知道这种形式的求和是
重写高斯公式s=n*(n+1)
型
循环= 1000000111-111 = 1 E9
一半,因为我们得到了寻找的两倍
1000000221 * 1E9 / 2 = 50000011050000000
也就是查找50000011050000000的结果
现在它有了一个编译时常量的结果,它可以将它与想要的结果进行比较,并注意它总是为true,因此它可以删除它。
记录的时间是您PC上system_clock的最短时间。
-O0
型
在A的循环前面,2-3可能会起作用。存储转发也喜欢它们的值自然对齐。
tv6aics14#
编辑:在了解了更多关于处理器流水线中的依赖关系之后,我修改了我的答案,删除了一些不必要的细节,并提供了一个更具体的解释。
看来-O 0情况下的性能差异是由于处理器流水线。
首先,汇编(用于-O 0构建),从Nemo的答案复制,并内联了一些我自己的注解:
字符串
在这两个函数中,堆栈布局看起来像这样:
型
(Note
total
是一个64位整数,因此占用了两个4字节的插槽。)以下是
superCalculationA()
的关键行:型
堆栈地址
-12(%rbp)
(保存i
的值)在addl
指令中写入,然后在下一条指令中立即读取。读指令在写入完成之前不能开始。这表示流水线中的块,导致superCalculationA()
比superCalculationB()
慢。你可能会好奇为什么
superCalculationB()
没有这个相同的流水线块。它实际上只是gcc如何在-O 0中编译代码的一个工件,并不代表任何有趣的东西。基本上,在superCalculationA()
中,比较i<end
是通过从寄存器阅读i
来执行的,而在superCalculationB()
中,通过从堆栈阅读i
来执行比较i<init+todo
。为了证明这只是一个人工制品,让我们替换
型
与
型
然后生成的程序集看起来是一样的,只是对键行做了以下更改:
型
现在
i
从堆栈中读取,管道块消失了。下面是进行此更改后的性能数据:型
应该注意的是,这实际上是一个玩具示例,因为我们使用-O 0进行编译。在现实世界中,我们使用-O2或-O3进行编译。在这种情况下,编译器以最小化流水线块的方式对指令进行排序,我们不需要担心是否要写
i<end
或end>i
。gijlo24d5#
(This并不完全是一个答案,但它确实包含了更多的数据,包括一些与Jerry Coffin相冲突的数据。
有趣的问题是,为什么未优化的例程执行起来如此不同和违反直觉。
-O2
和-O3
的情况相对容易解释,其他人也这样做了。为了完整起见,here is the assembly(感谢@Rutan Kax)用于GCC 4.9.1生成的
superCalculationA
和superCalculationB
:字符串
在我看来,B确实做了更多的工作。
我的测试平台是运行Red Hat Enterprise 6 Update 3的2.9GHz桑迪桥EP处理器(E5-2690)。我的编译器是GCC 4.9.1,并生成上面的程序集。
为了确保Turbo Boost和相关的CPU频率欺骗技术不会干扰测量,我运行了:
型
这将CPU频率固定到2.0 GHz并禁用Turbo Boost。
Jerry观察到这两个例程运行得更快或更慢,这取决于他执行它们的顺序。* 我无法重现这个结果。* 对我来说,
superCalculationB
始终比superCalculationA
快25-30%,无论Turbo Boost或时钟速度设置如何。这包括以任意顺序多次运行它们。例如,在2.0GHz时,superCalculationA
始终需要4500 ms多一点,superCalculationB
始终需要3600 ms以下一点。我还没有看到任何理论,甚至开始解释这一点。
mitkmikd6#
处理器很复杂。执行时间取决于许多因素,其中许多因素超出了您的控制范围。仅列出几种可能性:
a.您的计算机可能没有恒定的时钟速度。这可能是因为时钟速度通常设置得相当低,以避免浪费能源/电池寿命/产生过多的热量。当您的程序开始运行时,操作系统会计算出需要电源并增加时钟速度。为了验证,请更改调用的顺序-如果执行的第二个循环总是比第一个快,这可能是原因。
B.确切的执行速度,特别是对于像你这样的紧循环,取决于指令在内存中的对齐方式。如果它完全包含在一个缓存行而不是两个缓存行中,或者在两个缓存行而不是三个缓存行中,一些处理器可能会运行得更快。一些编译器会添加nop指令来对齐缓存行上的循环以优化这一点,很可能其中一个循环纯粹是运气好,因此跑得更快。
c.确切的执行速度可能取决于指令被分派的确切顺序。由于代码中的细微差异,稍微不同的代码可能以不同的速度运行,这可能是处理器相关的,并且无论如何编译器可能很难考虑。
d.有证据表明,英特尔处理器可能存在人工短循环的问题,这可能只发生在人工基准测试中。您的代码非常接近“人工”。在其他线程中讨论过非常短的循环运行速度意外缓慢的情况,添加指令可以使它们运行得更快。
58wvjzkj7#
对第一个问题的答复:
1.它做一次for循环后更快,但我不确定只是根据我的实验结果进行评论。(实验1更改它们的名称(B->A,A->B)实验2在时间检查前运行一个函数有for循环,实验3在时间检查前启动一个for循环)
1.第一个程序应该工作得更快,原因是第二个功能是当第一个功能做1个操作时做2个操作。
我在这里留下更新的代码来解释我的答案。
回答第二个问题:
我不确定,但我想到了两种方法,
它可以以某种方式形式化你的函数,并摆脱循环,因为这种方式可以消除差异(比如“return end-init”或“return todo”我不知道,我不确定)
它有-fauto_inc_dec,它可以产生这种差异,因为这些函数都是关于增量和减量的。
希望能帮上忙。
字符串