揭秘:：switch...case為什么比if...else執(zhí)行效率高？

時間：2020-06-22 12:57:23

關(guān)鍵字： switch se

手機(jī)看文章

掃描二維碼
隨時隨地手機(jī)看文章

[導(dǎo)讀]作者:李肖遙來源:技術(shù)讓夢想更偉大在C語言中，條件判斷語句是程序的重要組成部分，也是系統(tǒng)業(yè)務(wù)邏輯的控制手段，教科書告訴我們switch...case...語句比if...else if...else執(zhí)行效率要高，但這到底是為什么呢？本文嘗試從匯編的角度予以分析并揭曉其中的奧秘

作者:李肖遙

來源:技術(shù)讓夢想更偉大

在C語言中，條件判斷語句是程序的重要組成部分，也是系統(tǒng)業(yè)務(wù)邏輯的控制手段，教科書告訴我們switch...case...語句比if...else if...else執(zhí)行效率要高，但這到底是為什么呢？本文嘗試從匯編的角度予以分析并揭曉其中的奧秘。

switch...case與if...else的根本區(qū)別

switch...case會生成一個跳轉(zhuǎn)表來指示實(shí)際的case分支的地址，而這個跳轉(zhuǎn)表的索引號與switch變量的值是相等的。從而，switch...case不用像if...else那樣遍歷條件分支直到命中條件，而只需訪問對應(yīng)索引號的表項(xiàng)從而到達(dá)定位分支的目的。

具體地說，switch...case會生成一份大?。ū眄?xiàng)數(shù)）為最大case常量＋1的跳表，程序首先判斷switch變量是否大于最大case 常量，若大于，則跳到default分支處理；否則取得索引號為switch變量大小的跳表項(xiàng)的地址（即跳表的起始地址＋表項(xiàng)大?。饕枺绦蚪又酱说刂穲?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對二進(jìn)制文件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)到下一個分支再進(jì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

也就是說，當(dāng)c的取值不同，是什么機(jī)制保證第17行能跳轉(zhuǎn)到正確的位置開始執(zhí)行呢？

第16行: eax = [eax * 4 + 0x80485f0]

搞清楚了從地址0x80485f0開始，對應(yīng)的內(nèi)存里面的內(nèi)容也就回答了剛才的問題。

執(zhí)行完第16行后，

當(dāng)c為'1'或'0'時， eax的值應(yīng)該是0x080484a2；
當(dāng)c為'b'或'a'時， eax的值應(yīng)該是0x080484ae；
當(dāng)c為'B'或'A'時， eax的值應(yīng)該是0x080484ba；

通過gdb查看對應(yīng)的內(nèi)存，確實(shí)如此！

>>> 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í)是精準(zhǔn)無誤的，一定是編譯階段就被設(shè)定好了，果真如此嗎？接下來分析一下對應(yīng)的二進(jìn)制文件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ùn)行，對應(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ū)中，運(yùn)行的時候直接根據(jù)輸入(c的值）查表，找到對應(yīng)的IP后直接跳轉(zhuǎn)。（省去了cmp, jmp -> cmp, jmp -> cmp, jmp...這一冗長的計算過程。）

總結(jié)：

switch...case...執(zhí)行效率高，屬于典型的以空間換時間。也就是說，（套用算法的行話）以提高空間復(fù)雜度為代價降低了時間復(fù)雜度。

題外話

大家去看看一本書《C++ Footprint and Performance Optimization》，里面的7章，第一節(jié)。然后根據(jù)大量的實(shí)際程序測試（不考慮不同的編譯器優(yōu)化程度差異，假設(shè)都是最好的優(yōu)化），那么Switch語句擊中第三個選項(xiàng)的時間跟if/else if語句擊中第三個選項(xiàng)的時間相同。擊中第一，第二選項(xiàng)的速度if語句快，擊中第四以及第四之后的選項(xiàng)的速度switch語句快。所以，如果所有選項(xiàng)出現(xiàn)概率相同的話，結(jié)論就是：5個選項(xiàng)（包括default）的情況下，switch和if/else if相同。低于5個選項(xiàng)if快，高于5給選項(xiàng)switch快！

-END-