编程实现从 1 加到 100 和从 100 加到 1 两个程序,哪个更快?为什么?
该问题系中国科学技术大学软体学院考研面试问题。
据悉某考生回答一样快,被教授怼了,教授问「有没有复习机器码?」。
各位大佬可以参考回答。
在x86/ARM之类的主流架构上和RISC-V这种较新的架构上,如果不做任何优化,直接硬算,100加到1指令数会少一些。在单发射顺序执行的处理器上,100加到1会更快。
比如说RISC-V汇编,从1加到100:li a0, 0
li a1, 100
li a2, 0
L0:
addi a0, a0, 1
add a2, a2, a0
beq a0, a1, L0
li a0, 0
li a1, 100
L1:
add a0, a0, a1
addi a1, a1, -1
beqz a1, L1
4/23 7:10PM补充一下:
循环体中的三条指令在乱序执行的处理器中完全也可以重新排序后同时执行。对于从100加到1的程序而言,循环体内a0 a1之间是不存在显式的数据依赖的,因此两条加法指令是可以同时运行的。对于beqz指令而言,即使是简单的前跳后不跳分支预测器在这个场景下也能猜对99次,设计较为激进的处理器甚至可以同时运行这三条指令。
而对于从1加到100的程序而言,其实在流水线dispatch这一步把指令顺序做一个重排,和从100加到1的循环体就完全一样了。场景也应该是完全一样的。
综上所述,硬算100加到1对于嵌入式应用或者较老的处理器来讲,应该是比硬算1加到100快的。对于比较现代的处理器来讲,应该是不会有显著差别,甚至执行时间是完全相同的。
答案是一样快,因为
int sum1() {
int sum = 0;
for (int i = 1; i &<= 100; ++i) {
sum += i;
}
return sum;
}
int sum2() {
int sum = 0;
for (int i = 100; i &>= 1; --i) {
sum += i;
}
return sum;
}
使用g++ -O2编译后得到
sum1():
mov eax, 5050
ret
sum2():
mov eax, 5050
ret
这是个没有上下文的问题,也没说用什么语言,运行在什么平台上。那我就 assume 语言是 C++,目标平台为 x86-64,编译器为 gcc 8.3。
首先单纯的 1 加到 100 是没有意义的,因为开 -O3 的情况下编译器直接 emit:
mov eax, 5050
ret
所以问题变成,从 1 加到 n 快还是从 n 加到 1 快。
首先是 1 加到 n:
test edi, edi
jle .L4
add edi, 1
mov edx, 1
xor eax, eax
.L3:
add eax, edx
add edx, 1
cmp edx, edi
jne .L3
ret
.L4:
xor eax, eax
ret
然后是 n 加到 1:
xor eax, eax
test edi, edi
jle .L10
.L9:
add eax, edi
sub edi, 1
jne .L9
ret
.L10:
ret
显然后者指令更少,尤其是循环体内比前者少了一个 cmp 指令。其实这个问题在实际应用场景下意义不大,因为对于 n 很大的情况,直接用等差数列求和公式明显比任何用循环的方式都快。即便是必须要用循环的场景,也可以通过循环展开(参考:Duffs device)来优化。
而且编译器比你想像地要强大,开了 -O3 之后的 gcc 甚至会对循环次数大于一定阈值的代码直接开启 SIMD 指令优化,理论上比一遍一遍简单地循环还要快。
不过话说回来,我不太懂教授反问的「有没有复习机器码?」是什么意思,这跟机器码有什么关系吗?
补充:
刚才试了一下,clang -O3 优化的时候直接就是高斯求和公式:
test edi, edi
jle .LBB0_1
lea eax, [rdi - 1]
lea ecx, [rdi - 2]
imul rcx, rax
imul eax, eax
shr rcx
add eax, edi
sub eax, ecx
ret
.LBB0_1:
xor eax, eax
ret
这是一个非常有趣的问题——而且也一直以来都很有争论。
认为「100加到1比1加到100」快的人,往往是基于这样一个事实:
jnz指令要明显快于cmp之后再jne
但是,这里有一个问题:编译器是否真的会把循环中的「不等于零」用nz指令来替换?
这里以C语言为实验对象。
好的,我现在在wsl上运行了gcc (Ubuntu 7.4.0-1ubuntu1~18.04) 7.4.0
然后,用下面这段程序作为例子。
int sum;
int i;
int main(){
sum=0;
for(i=100;i!=0;i--)
sum+=i;
return 0;
}
一个很简单的C程序。
我们用gcc来进行一下汇编。
gcc -O0 -S 1.c
好的,我猜不会有多少人愿意看……那就摘一下重点吧。
比较的地方的汇编如下:
movl i(%rip), %eax
testl %eax, %eax
jne .L3
而对于「从1加到100」而言,这一段则是
movl i(%rip), %eax
cmpl $100, %eax
jle .L3
并没有本质的区别。
为了保险起见,我们把循环中的
for(i=100;i!=0;i--)
改成
for(i=101;--i;)
于是,对比输出的汇编结果,除了循环体内的减法操作跑到了比较的地方之外,并没有更多的差别。
那么,如果打开/O1呢…会不会把nz这种东西优化进来
movl $5050, sum(%rip)
当我没说…
于是现在,我们使用msvc试一试。(19.16.27030.1)
cl /Od /FAs /c /Fonul 1.c
和刚才类似地,对于一路减下去的做法,汇编里依然多了个cmp指令
cmp DWORD PTR i, 0
je SHORT $LN3@main
而,如果是一路加上来,比较也并不会复杂很多
cmp DWORD PTR i, 100 ; 00000064H
jg SHORT $LN3@main
至于那种非要把--i放到循环条件里的…enmmm…您别说,还真的少了一行汇编…
我找了半天才看出来差在哪…
别人是先jmp到循环条件那里检查一下…不知道为啥,到了这里就是一个大循环…
不过…要执行上千行汇编的事…您给我说这一行jmp…不太好吧…
好的,看到有人说到了「上古时代」的编译器会有这种特性。
于是在DOSBOX中运行Turbo C 1.0进行实验。
TCC -S 1.c
一如既往,同样的行数,同样的快乐。
cmp word ptr dgroup:_i,0
jne @4
cmp word ptr dgroup:_i,100
jle @4
然而,在最后一种「奇葩」方法的测试中,我们终于如愿以偿收获了惊喜。
dec word ptr dgroup:_i
jne @4
在循环体内,确实就像想像的那样,少了一个cmp指令。
不过先不要急著下结论。我们继续我们的实验。
这次我们用刚刚下载的icc来测试(Version 19.0.3.203 Build 20190206)
test eax, eax ;5.15
je .B1.4 ; Prob 50% ;5.15
cmp eax, 100 ;5.13
jg .B1.4 ; Prob 50% ;5.13
而--i的做法这次…
我看了好半天…有点没看明白为什么会出现这种智障操作…
mov DWORD PTR [rbp], eax ;5.14
mov eax, DWORD PTR [rbp] ;5.14
mov DWORD PTR [i], eax ;5.14
mov eax, DWORD PTR [rbp] ;5.14
不过从结果上来看…它每次循环比另外两种写法要多执行两条语句…
以后我想做一下其它语言和编译器的测试
不过就目前的结果来看…
这名学生完全可以问面试官具体的架构环境编译器参数…
嗯,如果面试官认为没开优化的编译器都可以…那么…
「老师,您预习编译原理了吗?」
如果完全从汇编的角度看,从 100 加到 1 要比从 1 加到 100 要快一点。
因为汇编有单独令 cx 和 0 比较进行跳转的指令 jz 和 jnz。从 100 加到 1,加数每次自减 1,最后加数会变成 0。假设加数用的是 cx 寄存器,在比较的时候用 jnz l 一条指令跳转就够了。
如果从 1 加到 100,那么在比较加数寄存器的时候,先要写一句 cmp cx, 100,然后再 jnb l,无形中多了一条指令。
如果是高级语言的话,那要看最终编译器汇编成的代码是什么样子的才能得出结论。
推荐阅读: