【揭秘】為什么switch...case比if...else執(zhí)行效率高
作者：李肖遙​
在C語言中，條件判斷語句是程序的重要組成部分，也是系統(tǒng)業(yè)務(wù)邏輯的控制手段，教科書告訴我們switch...case...語句比if...else if...else執(zhí)行效率要高。本文嘗試從匯編的角度予以分析并揭曉其中的奧秘。
switch...case與if...else的根本區(qū)別
switch...case會生成一個跳轉(zhuǎn)表來指示實際的case分支的地址，而這個跳轉(zhuǎn)表的索引號與switch變量的值是相等的。從而，switch...case不用像if...else那樣遍歷條件分支直到命中條件，而只需訪問對應(yīng)索引號的表項從而到達定位分支的目的。
具體地說，switch...case會生成一份大小（表項數(shù)）為最大case常量＋1的跳表，程序首先判斷switch變量是否大于最大case 常量，若大于，則跳到default分支處理；否則取得索引號為switch變量大小的跳表項的地址（即跳表的起始地址＋表項大小＊索引號），程序接著跳到此地址執(zhí)行，到此完成了分支的跳轉(zhuǎn)。
第一步，寫一個demo程序：foo.c
- #include <stdio.h>
- static int
- foo_ifelse(char c)
- {
- if (c == '0' || c == '1') {
- c += 1;
- } else if (c == 'a' || c == 'b') {
- c += 2;
- } else if (c == 'A' || c == 'B') {
- c += 3;
- } else {
- c += 4;
- }
- return (c);
- }
- static int
- foo_switch(char c)
- {
- switch (c) {
- case '1':
- case '0': c += 1; break;
- case 'b':
- case 'a': c += 2; break;
- case 'B':
- case 'A': c += 3; break;
- default: c += 4; break;
- }
- return (c);
- }
- int
- main(int argc, char **argv)
- {
- int m1 = foo_ifelse('0');
- int m2 = foo_ifelse('1');
- int n1 = foo_switch('a');
- int n2 = foo_switch('b');
- (void) printf("%c %c %c %c\n", m1, m2, n1, n2);
- return (0);
- }
第二步，在Ubuntu上使用gcc編譯
$ gcc -g -o foo foo.c
第三步，使用gdb對二進制文件foo反匯編 (使用intel語法)
- o 反匯編foo_ifelse（）
- (gdb) set disassembly-flavor intel
- (gdb) disas /m foo_ifelse
- Dump of assembler code for function foo_ifelse:
- 4 {
- 0x0804841d <+0>: push ebp
- 0x0804841e <+1>: mov ebp,esp
- 0x08048420 <+3>: sub esp,0x4
- 0x08048423 <+6>: mov eax,DWORD PTR [ebp+0x8]
- 0x08048426 <+9>: mov BYTE PTR [ebp-0x4],al
- 5 if (c == '0' || c == '1') {
- 0x08048429 <+12>: cmp BYTE PTR [ebp-0x4],0x30
- 0x0804842d <+16>: je 0x8048435 <foo_ifelse+24>
- 0x0804842f <+18>: cmp BYTE PTR [ebp-0x4],0x31
- 0x08048433 <+22>: jne 0x8048441 <foo_ifelse+36>
- 6 c += 1;
- 0x08048435 <+24>: movzx eax,BYTE PTR [ebp-0x4]
- 0x08048439 <+28>: add eax,0x1
- 0x0804843c <+31>: mov BYTE PTR [ebp-0x4],al
- 0x0804843f <+34>: jmp 0x804847b <foo_ifelse+94>
- 7 } else if (c == 'a' || c == 'b') {
- 0x08048441 <+36>: cmp BYTE PTR [ebp-0x4],0x61
- 0x08048445 <+40>: je 0x804844d <foo_ifelse+48>
- 0x08048447 <+42>: cmp BYTE PTR [ebp-0x4],0x62
- 0x0804844b <+46>: jne 0x8048459 <foo_ifelse+60>
- 8 c += 2;
- 0x0804844d <+48>: movzx eax,BYTE PTR [ebp-0x4]
- 0x08048451 <+52>: add eax,0x2
- 0x08048454 <+55>: mov BYTE PTR [ebp-0x4],al
- 0x08048457 <+58>: jmp 0x804847b <foo_ifelse+94>
- 9 } else if (c == 'A' || c == 'B') {
- 0x08048459 <+60>: cmp BYTE PTR [ebp-0x4],0x41
- 0x0804845d <+64>: je 0x8048465 <foo_ifelse+72>
- 0x0804845f <+66>: cmp BYTE PTR [ebp-0x4],0x42
- 0x08048463 <+70>: jne 0x8048471 <foo_ifelse+84>
- 10 c += 3;
- 0x08048465 <+72>: movzx eax,BYTE PTR [ebp-0x4]
- 0x08048469 <+76>: add eax,0x3
- 0x0804846c <+79>: mov BYTE PTR [ebp-0x4],al
- 0x0804846f <+82>: jmp 0x804847b <foo_ifelse+94>
- 11 } else {
- 12 c += 4;
- 0x08048471 <+84>: movzx eax,BYTE PTR [ebp-0x4]
- 0x08048475 <+88>: add eax,0x4
- 0x08048478 <+91>: mov BYTE PTR [ebp-0x4],al
- 13 }
- 14
- 15 return (c);
- 0x0804847b <+94>: movsx eax,BYTE PTR [ebp-0x4]
- 16 }
- 0x0804847f <+98>: leave
- 0x08048480 <+99>: ret
- End of assembler dump.
- (gdb)o 反匯編foo_ifelse（）
- (gdb) set disassembly-flavor intel
- (gdb) disas /m foo_ifelse
- Dump of assembler code for function foo_ifelse:
- 4 {
- 0x0804841d <+0>: push ebp
- 0x0804841e <+1>: mov ebp,esp
- 0x08048420 <+3>: sub esp,0x4
- 0x08048423 <+6>: mov eax,DWORD PTR [ebp+0x8]
- 0x08048426 <+9>: mov BYTE PTR [ebp-0x4],al
- 5 if (c == '0' || c == '1') {
- 0x08048429 <+12>: cmp BYTE PTR [ebp-0x4],0x30
- 0x0804842d <+16>: je 0x8048435 <foo_ifelse+24>
- 0x0804842f <+18>: cmp BYTE PTR [ebp-0x4],0x31
- 0x08048433 <+22>: jne 0x8048441 <foo_ifelse+36>
- 6 c += 1;
- 0x08048435 <+24>: movzx eax,BYTE PTR [ebp-0x4]
- 0x08048439 <+28>: add eax,0x1
- 0x0804843c <+31>: mov BYTE PTR [ebp-0x4],al
- 0x0804843f <+34>: jmp 0x804847b <foo_ifelse+94>
- 7 } else if (c == 'a' || c == 'b') {
- 0x08048441 <+36>: cmp BYTE PTR [ebp-0x4],0x61
- 0x08048445 <+40>: je 0x804844d <foo_ifelse+48>
- 0x08048447 <+42>: cmp BYTE PTR [ebp-0x4],0x62
- 0x0804844b <+46>: jne 0x8048459 <foo_ifelse+60>
- 8 c += 2;
- 0x0804844d <+48>: movzx eax,BYTE PTR [ebp-0x4]
- 0x08048451 <+52>: add eax,0x2
- 0x08048454 <+55>: mov BYTE PTR [ebp-0x4],al
- 0x08048457 <+58>: jmp 0x804847b <foo_ifelse+94>
- 9 } else if (c == 'A' || c == 'B') {
- 0x08048459 <+60>: cmp BYTE PTR [ebp-0x4],0x41
- 0x0804845d <+64>: je 0x8048465 <foo_ifelse+72>
- 0x0804845f <+66>: cmp BYTE PTR [ebp-0x4],0x42
- 0x08048463 <+70>: jne 0x8048471 <foo_ifelse+84>
- 10 c += 3;
- 0x08048465 <+72>: movzx eax,BYTE PTR [ebp-0x4]
- 0x08048469 <+76>: add eax,0x3
- 0x0804846c <+79>: mov BYTE PTR [ebp-0x4],al
- 0x0804846f <+82>: jmp 0x804847b <foo_ifelse+94>
- 11 } else {
- 12 c += 4;
- 0x08048471 <+84>: movzx eax,BYTE PTR [ebp-0x4]
- 0x08048475 <+88>: add eax,0x4
- 0x08048478 <+91>: mov BYTE PTR [ebp-0x4],al
- 13 }
- 14
- 15 return (c);
- 0x0804847b <+94>: movsx eax,BYTE PTR [ebp-0x4]
- 16 }
- 0x0804847f <+98>: leave
- 0x08048480 <+99>: ret
- End of assembler dump.
- (gdb)
o 反匯編foo_switch（）
- (gdb) set disassembly-flavor intel
- (gdb) disas /m foo_switch
- Dump of assembler code for function foo_switch:
- 20 {
- 0x08048481 <+0>: push ebp
- 0x08048482 <+1>: mov ebp,esp
- 0x08048484 <+3>: sub esp,0x4
- 0x08048487 <+6>: mov eax,DWORD PTR [ebp+0x8]
- 0x0804848a <+9>: mov BYTE PTR [ebp-0x4],al
- 21 switch (c) {
- 0x0804848d <+12>: movsx eax,BYTE PTR [ebp-0x4]
- 0x08048491 <+16>: sub eax,0x30
- 0x08048494 <+19>: cmp eax,0x32
- 0x08048497 <+22>: ja 0x80484c6 <foo_switch+69>
- 0x08048499 <+24>: mov eax,DWORD PTR [eax*4+0x80485f0]
- 0x080484a0 <+31>: jmp eax
- 22 case '1':
- 23 case '0': c += 1; break;
- 0x080484a2 <+33>: movzx eax,BYTE PTR [ebp-0x4]
- 0x080484a6 <+37>: add eax,0x1
- 0x080484a9 <+40>: mov BYTE PTR [ebp-0x4],al
- 0x080484ac <+43>: jmp 0x80484d1 <foo_switch+80>
- 24 case 'b':
- 25 case 'a': c += 2; break;
- 0x080484ae <+45>: movzx eax,BYTE PTR [ebp-0x4]
- 0x080484b2 <+49>: add eax,0x2
- 0x080484b5 <+52>: mov BYTE PTR [ebp-0x4],al
- 0x080484b8 <+55>: jmp 0x80484d1 <foo_switch+80>
- 26 case 'B':
- 27 case 'A': c += 3; break;
- 0x080484ba <+57>: movzx eax,BYTE PTR [ebp-0x4]
- 0x080484be <+61>: add eax,0x3
- 0x080484c1 <+64>: mov BYTE PTR [ebp-0x4],al
- 0x080484c4 <+67>: jmp 0x80484d1 <foo_switch+80>
- 28 default: c += 4; break;
- 0x080484c6 <+69>: movzx eax,BYTE PTR [ebp-0x4]
- 0x080484ca <+73>: add eax,0x4
- 0x080484cd <+76>: mov BYTE PTR [ebp-0x4],al
- 0x080484d0 <+79>: nop
- 29 }
- 30
- 31 return (c);
- 0x080484d1 <+80>: movsx eax,BYTE PTR [ebp-0x4]
- 32 }
- 0x080484d5 <+84>: leave
- 0x080484d6 <+85>: ret
- End of assembler dump.
- (gdb)
分析：
- 在foo_ifelse()中，采用的方法是按順序比較，如滿足條件，則執(zhí)行對應(yīng)的代碼，否則跳轉(zhuǎn)到下一個分支再進行比較；
- 在foo_switch()中，下面的這段匯編代碼比較有意思，
- ..
- 21 switch (c) {
- 0x0804848d <+12>: movsx eax,BYTE PTR [ebp-0x4]
- 0x08048491 <+16>: sub eax,0x30
- 0x08048494 <+19>: cmp eax,0x32
- 0x08048497 <+22>: ja 0x80484c6 <foo_switch+69>
- 0x08048499 <+24>: mov eax,DWORD PTR [eax*4+0x80485f0]
- 0x080484a0 <+31>: jmp eax
- ..
注意：
第17行 jmp eax
也就是說，當c的取值不同，是什么機制保證第17行能跳轉(zhuǎn)到正確的位置開始執(zhí)行呢？
第16行: eax = [eax * 4 + 0x80485f0]
搞清楚了從地址0x80485f0開始，對應(yīng)的內(nèi)存里面的內(nèi)容也就回答了剛才的問題。
執(zhí)行完第16行后，
- 當c為'1'或'0'時， eax的值應(yīng)該是0x080484a2；
- 當c為'b'或'a'時， eax的值應(yīng)該是0x080484ae；
- 當c為'B'或'A'時， eax的值應(yīng)該是0x080484ba；
通過gdb查看對應(yīng)的內(nèi)存，確實如此！
- >>> ord('1') - 0x30
- >>> ord('0') - 0x30
- (gdb) x /2wx 0*4+0x80485f0
- 0x80485f0: 0x080484a2 0x080484a2
- >>> ord('b') - 0x30
- >>> ord('a') - 0x30
- (gdb) x /2wx 49*4+0x80485f0
- 0x80486b4: 0x080484ae 0x080484ae
- >>> ord('B') - 0x30
- >>> ord('A') - 0x30
- (gdb) x /2wx 17*4+0x80485f0
- 0x8048634: 0x080484ba 0x080484ba
那么，我們可以大膽的猜測，雖然c的取值不同但是跳轉(zhuǎn)的IP確實是精準無誤的，一定是編譯階段就被設(shè)定好了，果真如此嗎？接下來分析一下對應(yīng)的二進制文件foo,
第四步，使用objdump查看foo,
- $ objdump -D foo > /tmp/x
- $ vim /tmp/x
- 509 Disassembly of section .rodata:
- ...
- 518 80485f0: a2 84 04 08 a2 mov %al,0xa2080484
- 519 80485f5: 84 04 08 test %al,(%eax,%ecx,1)
- ...
- 534 8048630: c6 84 04 08 ba 84 04 movb $0x8,0x484ba08(%esp,%eax,1)
- 535 8048637: 08
- 536 8048638: ba 84 04 08 c6 mov $0xc6080484,%edx
- ...
- 566 80486b0: c6 84 04 08 ae 84 04 movb $0x8,0x484ae08(%esp,%eax,1)
- 567 80486b7: 08
- 568 80486b8: ae scas %es:(%edi),%al
- 569 80486b9: 84 04 08 test %al,(%eax,%ecx,1)
- ...
在0x80485f0地址，存的8個字節(jié)正好是0x080484a2, 0x080484a2 (注意：按照小端的方式閱讀)
在0x80486b4地址，存的8個字節(jié)正好是0x080484ae, 0x080484ae
在0x8048634地址，存的8個字節(jié)正好是0x080484ba,0x080484ba
果然不出所料，要跳轉(zhuǎn)的IP的值正是在編譯的時候存入了.rodata（只讀數(shù)據(jù)區(qū)）。一旦foo開始運行，對應(yīng)的內(nèi)存地址就填寫上了正確的待跳轉(zhuǎn)地址，接下來只不過是根據(jù)c的取值計算出對應(yīng)的IP存放的內(nèi)存起始地址X，從X中取出待跳轉(zhuǎn)的地址，直接跳轉(zhuǎn)就好。
- 16 0x08048499 <+24>: mov eax,DWORD PTR [eax*4+0x80485f0]
- 17 0x080484a0 <+31>: jmp eax
到此為止，我們已經(jīng)搞清楚了為什么switch...case...語句相對于if...else if...else...來說執(zhí)行效率要高的根本原因。簡言之，編譯的時候創(chuàng)建了一個map存于.rodata區(qū)中，運行的時候直接根據(jù)輸入(c的值）查表，找到對應(yīng)的IP后直接跳轉(zhuǎn)。（省去了cmp, jmp -> cmp, jmp -> cmp, jmp...這一冗長的計算過程。）
總結(jié)：
switch...case...執(zhí)行效率高，屬于典型的以空間換時間。也就是說，（套用算法的行話）以提高空間復(fù)雜度為代價降低了時間復(fù)雜度。
【責任編輯：龐桂玉 TEL：（010）68476606】
責任編輯：龐桂玉
來源：
C語言與C++編程
