|
某日一个同学在做算法题，（旅游背包）在OJ系统提交时超时
我们在设法优化代码减少运行时间时，发现貌似If-else比三目运算?: 更快一点。
于是，用VC写了一段简短的测试。同样是双重循环中执行 if-else与三目运算，计算其花费的时间。
a=100,b=50,n为测试变量
start=clock();
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(a>b)
temp=a;
else
temp=b;
}
}
end=clock();
cout << "Time=
"<<end-start<<endl;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
temp=a>b?a:b;
}
}
以下是测试结果：
time单位为
ms
n=100
If time =
0
The :? time =
0
n=1000
If time =
2
The :? time =
4
n=10,000
If time =
253
The :? time =
360
n=50,000
If time =
6209
The :? time =
8941
n=100,000
If time =
24343
The :? time =
35807
可以见到，随着n越大，两者差距越来越明显（未经多台电脑测试，仅经自己台试，神奇的是在Ubuntu下没多大差别，这问题在后面说），然后我通过反编译，查看它们的汇编代码，发现一件令我不解的神奇事。
以下分别是If-else与三目运算的汇编代码。
37:
if(a>b)
00401079 mov
ecx,dword ptr [ebp-10h]
0040107C cmp
ecx,dword ptr [ebp-14h]
0040107F jle
main+79h (00401089)
38:
temp=a;
00401081 mov
edx,dword ptr [ebp-10h]
00401084 mov
dword ptr [ebp-18h],edx
39:
else
00401087 jmp
main+7Fh (0040108f)
40:
temp=b;
00401089 mov
eax,dword ptr [ebp-14h]
0040108C mov
dword ptr [ebp-18h],eax
51:
temp=a>b?a:b;
004010F3 mov
edx,dword ptr [ebp-10h]
004010F6 cmp
edx,dword ptr [ebp-14h]
004010F9 jle
main+0F3h (00401103)
004010FB mov
eax,dword ptr [ebp-10h]
004010FE mov
dword ptr [ebp-24h],eax
00401101 jmp
main+0F9h (00401109)
00401103 mov
ecx,dword ptr [ebp-14h]
00401106 mov
dword ptr [ebp-24h],ecx
00401109 mov
edx,dword ptr [ebp-24h]
0040110C mov
dword ptr [ebp-18h],edx
可见后者比前者多了两条指令。
If-else无论在何种情况下（在if中或者else中），都是通过先将需要赋的变量值传给寄存器然后再通过寄存器赋值给temp变量
。即
mov edx,b； mov temp,edx ；
然而，对于三目运算，它其中一步却增加多了一个临时变量。
mov ecx,b；mov NEWTEMP,ecx；
mov edx,NEWTEMP；mov temp；edx；
以下是一个同学给我的答案（他从编译原理课上学的）：
因为三目运算是先运算，再赋值！
例如
：
temp = a > b ? a : b
;
a > b ? a : b 是运算，
temp = （a > b ? a : b ）是赋值。
所以在三目的汇编里面
a,b,temp地址 为10h,14h 18h
无论a>b的结果怎样，都有先将它后
面的结果保存在地址为
24h 的中间变量里面 ，然后再 赋值给地址为 18h
的temp变量中！
而 if 语句是直接赋值 ，不存在运算，所以快了一点。
然后根据这原理，可以知道 ++i 比 i++ 快， x+=y 比
x=x+y 快。
不过，我们写程序的时候可以忽略它们，因为这种东西，编译器已经帮我们优化了！！！
所以不管你写 i++ 还是 ++i ，它都是一样的
，以下是证明。
00401048 mov
dword ptr [ebp-4],1
32:
33:
++i;
0040104F mov
eax,dword ptr [ebp-4]
00401052 add
eax,1
00401055 mov
dword ptr [ebp-4],eax
34:
35:
i++;
00401058 mov
ecx,dword ptr [ebp-4]
0040105B add
ecx,1
0040105E mov
dword ptr [ebp-4],ecx
可是为什么VC没有优化这个三目运算？把它改成if形式？
回到上面遗留的问题，为何Ubuntu下运行没区别？----> 或许Ubuntu下的编译器把它优化了
之前在百度找了一下答案，说是如果将三目赋的值变为常量，这样的话执行起来无需要像if-else那样跳转，利于CPU执行。（这涉及到硬件，我不懂，也没兴趣继续刨根问底了~这问题，到此结束吧。）
以下是常量的汇编代码。 确实没有跳转指令
将1:0换成其他数字，经测试也是没有，虽然指令会多了几条。
38:
z=x>y?1:0;
0040106E mov
ecx,dword ptr [ebp-8]
00401071 xor
edx,edx
00401073 cmp
ecx,dword ptr [ebp-0Ch]
00401076 setg
dl
00401079 mov
dword ptr [ebp-4],edx
本文转载自http://blog.sina.com.cn/s/blog_6cf502aa0101e7mx.html，非原创
|
