作者:李肖遙
來源:技術讓夢想更偉大
在C語言中，條件判斷語句是程式的重要組成部分，也是系統業務邏輯的控制手段，教科書告訴我們switch...case...語句比if...else if...else執行效率要高，但這到底是為什麼呢？本文嘗試從彙編的角度予以分析并揭曉其中的奧秘。
switch...case與if...else的根本差別
switch...case會生成一個跳轉表來訓示實際的case分支的位址，而這個跳轉表的索引号與switch變量的值是相等的。進而，switch...case不用像if...else那樣周遊條件分支直到命中條件，而隻需通路對應索引号的表項進而到達定位分支的目的。
具體地說，switch...case會生成一份大小（表項數）為最大case常量＋1的跳表，程式首先判斷switch變量是否大于最大case 常量，若大于，則跳到default分支處理；否則取得索引号為switch變量大小的跳表項的位址（即跳表的起始位址＋表項大小＊索引号），程式接着跳到此位址執行，到此完成了分支的跳轉。
第一步，寫一個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()中，采用的方法是按順序比較，如滿足條件，則執行對應的代碼，否則跳轉到下一個分支再進行比較；
- 在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行能跳轉到正确的位置開始執行呢？
第16行: eax = [eax * 4 + 0x80485f0]
搞清楚了從位址0x80485f0開始，對應的記憶體裡面的内容也就回答了剛才的問題。
執行完第16行後，
- 當c為'1'或'0'時， eax的值應該是0x080484a2；
- 當c為'b'或'a'時， eax的值應該是0x080484ae；
- 當c為'B'或'A'時， eax的值應該是0x080484ba；
通過gdb檢視對應的記憶體，确實如此！
>>> 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的取值不同但是跳轉的IP确實是精準無誤的，一定是編譯階段就被設定好了，果真如此嗎？接下來分析一下對應的二進制檔案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個位元組正好是0x080484a2, 0x080484a2 (注意：按照小端的方式閱讀)
在0x80486b4位址，存的8個位元組正好是0x080484ae, 0x080484ae
在0x8048634位址，存的8個位元組正好是0x080484ba,0x080484ba
果然不出所料，要跳轉的IP的值正是在編譯的時候存入了.rodata（隻讀資料區）。一旦foo開始運作，對應的記憶體位址就填寫上了正确的待跳轉位址，接下來隻不過是根據c的取值計算出對應的IP存放的記憶體起始位址X，從X中取出待跳轉的位址，直接跳轉就好。
16 0x08048499 <+24>: mov eax,DWORD PTR [eax*4+0x80485f0]
17 0x080484a0 <+31>: jmp eax
複制
到此為止，我們已經搞清楚了為什麼switch...case...語句相對于if...else if...else...來說執行效率要高的根本原因。簡言之，編譯的時候建立了一個map存于.rodata區中，運作的時候直接根據輸入(c的值）查表，找到對應的IP後直接跳轉。（省去了cmp, jmp -> cmp, jmp -> cmp, jmp...這一冗長的計算過程。）
總結：
switch...case...執行效率高，屬于典型的以空間換時間。也就是說，（套用算法的行話）以提高空間複雜度為代價降低了時間複雜度。
題外話
大家去看看一本書《C++ Footprint and Performance Optimization》，裡面的7章，第一節。然後根據大量的實際程式測試（不考慮不同的編譯器優化程度差異，假設都是最好的優化），那麼Switch語句擊中第三個選項的時間跟if/else if語句擊中第三個選項的時間相同。擊中第一，第二選項的速度if語句快，擊中第四以及第四之後的選項的速度switch語句快。是以，如果所有選項出現機率相同的話，結論就是：5個選項（包括default）的情況下，switch和if/else if相同。低于5個選項if快，高于5給選項switch快！