自拍偷在线精品自拍偷,亚洲欧美中文日韩v在线观看不卡

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

作者：李肖遙​
開(kāi)發(fā) 后端
在C語(yǔ)言中，條件判斷語(yǔ)句是程序的重要組成部分，也是系統(tǒng)業(yè)務(wù)邏輯的控制手段，教科書(shū)告訴我們switch...case...語(yǔ)句比if...else if...else執(zhí)行效率要高。本文嘗試從匯編的角度予以分析并揭曉其中的奧秘。

 [[333956]]

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

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

具體地說(shuō)，switch...case會(huì)生成一份大?。ū眄?xiàng)數(shù)）為最大case常量＋1的跳表，程序首先判斷switch變量是否大于最大case 常量，若大于，則跳到default分支處理；否則取得索引號(hào)為switch變量大小的跳表項(xiàng)的地址（即跳表的起始地址＋表項(xiàng)大小＊索引號(hào)），程序接著跳到此地址執(zhí)行，到此完成了分支的跳轉(zhuǎn)。

第一步，寫(xiě)一個(gè)demo程序：foo.c 

  1. #include <stdio.h>  
  2. static int  
  3. foo_ifelse(char c)  
  4. {  
  5.         if (c == '0' || c == '1') {  
  6.                 c += 1;  
  7.         } else if (c == 'a' || c == 'b') {  
  8.                 c += 2;  
  9.         } else if (c == 'A' || c == 'B') {  
  10.                 c += 3;  
  11.         } else {  
  12.                 c += 4;  
  13.         }  
  14.         return (c);  
  15. }  
  16. static int  
  17. foo_switch(char c)  
  18. {  
  19.         switch (c) {  
  20.                 case '1':  
  21.                 case '0': c += 1; break;  
  22.                 case 'b':  
  23.                 case 'a': c += 2; break;  
  24.                 case 'B':  
  25.                 case 'A': c += 3; break;  
  26.                 default:  c += 4; break;  
  27.         }    
  28.         return (c); 
  29. }  
  30. int  
  31. main(int argc, char **argv)  
  32. {  
  33.         int m1 = foo_ifelse('0');  
  34.         int m2 = foo_ifelse('1');  
  35.         int n1 = foo_switch('a'); 
  36.         int n2 = foo_switch('b');  
  37.         (void) printf("%c %c %c %c\n", m1, m2, n1, n2);  
  38.         return (0);  
  39. } 

第二步，在Ubuntu上使用gcc編譯

$ gcc -g -o foo foo.c

第三步，使用gdb對(duì)二進(jìn)制文件foo反匯編 (使用intel語(yǔ)法) 

  1. o 反匯編foo_ifelse（） 
  2. (gdb) set disassembly-flavor intel  
  3. (gdb) disas /m foo_ifelse  
  4. Dump of assembler code for function foo_ifelse:  
  5. 4       {  
  6.    0x0804841d <+0>:     push   ebp  
  7.    0x0804841e <+1>:     mov    ebp,esp  
  8.    0x08048420 <+3>:     sub    esp,0x4  
  9.    0x08048423 <+6>:     mov    eax,DWORD PTR [ebp+0x8]  
  10.    0x08048426 <+9>:     mov    BYTE PTR [ebp-0x4],al    
  11. 5               if (c == '0' || c == '1') {  
  12.    0x08048429 <+12>:    cmp    BYTE PTR [ebp-0x4],0x30  
  13.    0x0804842d <+16>:    je     0x8048435 <foo_ifelse+24>  
  14.    0x0804842f <+18>:    cmp    BYTE PTR [ebp-0x4],0x31  
  15.    0x08048433 <+22>:    jne    0x8048441 <foo_ifelse+36>  
  16. 6                       c += 1;  
  17.    0x08048435 <+24>:    movzx  eax,BYTE PTR [ebp-0x4]  
  18.    0x08048439 <+28>:    add    eax,0x1  
  19.    0x0804843c <+31>:    mov    BYTE PTR [ebp-0x4],al  
  20.    0x0804843f <+34>:    jmp    0x804847b <foo_ifelse+94>  
  21. 7               } else if (c == 'a' || c == 'b') {  
  22.    0x08048441 <+36>:    cmp    BYTE PTR [ebp-0x4],0x61  
  23.    0x08048445 <+40>:    je     0x804844d <foo_ifelse+48>  
  24.    0x08048447 <+42>:    cmp    BYTE PTR [ebp-0x4],0x62  
  25.    0x0804844b <+46>:    jne    0x8048459 <foo_ifelse+60>  
  26. 8                       c += 2;  
  27.    0x0804844d <+48>:    movzx  eax,BYTE PTR [ebp-0x4]  
  28.    0x08048451 <+52>:    add    eax,0x2  
  29.    0x08048454 <+55>:    mov    BYTE PTR [ebp-0x4],al  
  30.    0x08048457 <+58>:    jmp    0x804847b <foo_ifelse+94>  
  31. 9               } else if (c == 'A' || c == 'B') {  
  32.    0x08048459 <+60>:    cmp    BYTE PTR [ebp-0x4],0x41  
  33.    0x0804845d <+64>:    je     0x8048465 <foo_ifelse+72>  
  34.    0x0804845f <+66>:    cmp    BYTE PTR [ebp-0x4],0x42  
  35.    0x08048463 <+70>:    jne    0x8048471 <foo_ifelse+84>  
  36. 10                      c += 3;  
  37.    0x08048465 <+72>:    movzx  eax,BYTE PTR [ebp-0x4]  
  38.    0x08048469 <+76>:    add    eax,0x3  
  39.    0x0804846c <+79>:    mov    BYTE PTR [ebp-0x4],al  
  40.    0x0804846f <+82>:    jmp    0x804847b <foo_ifelse+94>  
  41. 11              } else {  
  42. 12                      c += 4;  
  43.    0x08048471 <+84>:    movzx  eax,BYTE PTR [ebp-0x4]  
  44.    0x08048475 <+88>:    add    eax,0x4  
  45.    0x08048478 <+91>:    mov    BYTE PTR [ebp-0x4],al  
  46. 13              }  
  47. 14  
  48. 15              return (c);  
  49.    0x0804847b <+94>:    movsx  eax,BYTE PTR [ebp-0x4]  
  50. 16      }  
  51.    0x0804847f <+98>:    leave  
  52.    0x08048480 <+99>:    ret  
  53. End of assembler dump.  
  54. (gdb)o 反匯編foo_ifelse（）  
  55. (gdb) set disassembly-flavor intel  
  56. (gdb) disas /m foo_ifelse  
  57. Dump of assembler code for function foo_ifelse:  
  58. 4       {  
  59.    0x0804841d <+0>:     push   ebp  
  60.    0x0804841e <+1>:     mov    ebp,esp  
  61.    0x08048420 <+3>:     sub    esp,0x4  
  62.    0x08048423 <+6>:     mov    eax,DWORD PTR [ebp+0x8]  
  63.    0x08048426 <+9>:     mov    BYTE PTR [ebp-0x4],al  
  64. 5               if (c == '0' || c == '1') {  
  65.    0x08048429 <+12>:    cmp    BYTE PTR [ebp-0x4],0x30  
  66.    0x0804842d <+16>:    je     0x8048435 <foo_ifelse+24>  
  67.    0x0804842f <+18>:    cmp    BYTE PTR [ebp-0x4],0x31  
  68.    0x08048433 <+22>:    jne    0x8048441 <foo_ifelse+36>  
  69. 6                       c += 1;  
  70.    0x08048435 <+24>:    movzx  eax,BYTE PTR [ebp-0x4]  
  71.    0x08048439 <+28>:    add    eax,0x1  
  72.    0x0804843c <+31>:    mov    BYTE PTR [ebp-0x4],al  
  73.    0x0804843f <+34>:    jmp    0x804847b <foo_ifelse+94>  
  74. 7               } else if (c == 'a' || c == 'b') {  
  75.    0x08048441 <+36>:    cmp    BYTE PTR [ebp-0x4],0x61  
  76.    0x08048445 <+40>:    je     0x804844d <foo_ifelse+48>  
  77.    0x08048447 <+42>:    cmp    BYTE PTR [ebp-0x4],0x62  
  78.    0x0804844b <+46>:    jne    0x8048459 <foo_ifelse+60>  
  79. 8                       c += 2;  
  80.    0x0804844d <+48>:    movzx  eax,BYTE PTR [ebp-0x4]  
  81.    0x08048451 <+52>:    add    eax,0x2  
  82.    0x08048454 <+55>:    mov    BYTE PTR [ebp-0x4],al  
  83.    0x08048457 <+58>:    jmp    0x804847b <foo_ifelse+94>  
  84. 9               } else if (c == 'A' || c == 'B') {  
  85.    0x08048459 <+60>:    cmp    BYTE PTR [ebp-0x4],0x41  
  86.    0x0804845d <+64>:    je     0x8048465 <foo_ifelse+72>  
  87.    0x0804845f <+66>:    cmp    BYTE PTR [ebp-0x4],0x42  
  88.    0x08048463 <+70>:    jne    0x8048471 <foo_ifelse+84> 
  89. 10                      c += 3;  
  90.    0x08048465 <+72>:    movzx  eax,BYTE PTR [ebp-0x4]  
  91.    0x08048469 <+76>:    add    eax,0x3  
  92.    0x0804846c <+79>:    mov    BYTE PTR [ebp-0x4],al  
  93.    0x0804846f <+82>:    jmp    0x804847b <foo_ifelse+94>  
  94. 11              } else {  
  95. 12                      c += 4;  
  96.    0x08048471 <+84>:    movzx  eax,BYTE PTR [ebp-0x4]  
  97.    0x08048475 <+88>:    add    eax,0x4  
  98.    0x08048478 <+91>:    mov    BYTE PTR [ebp-0x4],al  
  99. 13              }  
  100. 14  
  101. 15              return (c);  
  102.    0x0804847b <+94>:    movsx  eax,BYTE PTR [ebp-0x4]  
  103. 16      }  
  104.    0x0804847f <+98>:    leave  
  105.    0x08048480 <+99>:    ret  
  106. End of assembler dump.  
  107. (gdb) 

o 反匯編foo_switch（） 

  1. (gdb) set disassembly-flavor intel  
  2. (gdb) disas /m foo_switch  
  3. Dump of assembler code for function foo_switch:  
  4. 20      {  
  5.    0x08048481 <+0>:     push   ebp  
  6.    0x08048482 <+1>:     mov    ebp,esp  
  7.    0x08048484 <+3>:     sub    esp,0x4  
  8.    0x08048487 <+6>:     mov    eax,DWORD PTR [ebp+0x8]  
  9.    0x0804848a <+9>:     mov    BYTE PTR [ebp-0x4],al  
  10. 21              switch (c) {  
  11.    0x0804848d <+12>:    movsx  eax,BYTE PTR [ebp-0x4]  
  12.    0x08048491 <+16>:    sub    eax,0x30  
  13.    0x08048494 <+19>:    cmp    eax,0x32  
  14.    0x08048497 <+22>:    ja     0x80484c6 <foo_switch+69>  
  15.    0x08048499 <+24>:    mov    eax,DWORD PTR [eax*4+0x80485f0]  
  16.    0x080484a0 <+31>:    jmp    eax  
  17. 22                      case '1':  
  18. 23                      case '0': c += 1; break;  
  19.    0x080484a2 <+33>:    movzx  eax,BYTE PTR [ebp-0x4]  
  20.    0x080484a6 <+37>:    add    eax,0x1  
  21.    0x080484a9 <+40>:    mov    BYTE PTR [ebp-0x4],al  
  22.    0x080484ac <+43>:    jmp    0x80484d1 <foo_switch+80>  
  23. 24                      case 'b':  
  24. 25                      case 'a': c += 2; break;  
  25.    0x080484ae <+45>:    movzx  eax,BYTE PTR [ebp-0x4]  
  26.    0x080484b2 <+49>:    add    eax,0x2  
  27.    0x080484b5 <+52>:    mov    BYTE PTR [ebp-0x4],al  
  28.    0x080484b8 <+55>:    jmp    0x80484d1 <foo_switch+80>  
  29. 26                      case 'B':  
  30. 27                      case 'A': c += 3; break;  
  31.    0x080484ba <+57>:    movzx  eax,BYTE PTR [ebp-0x4]  
  32.    0x080484be <+61>:    add    eax,0x3  
  33.    0x080484c1 <+64>:    mov    BYTE PTR [ebp-0x4],al  
  34.    0x080484c4 <+67>:    jmp    0x80484d1 <foo_switch+80>  
  35. 28                      default:  c += 4; break;  
  36.    0x080484c6 <+69>:    movzx  eax,BYTE PTR [ebp-0x4]  
  37.    0x080484ca <+73>:    add    eax,0x4  
  38.    0x080484cd <+76>:    mov    BYTE PTR [ebp-0x4],al  
  39.    0x080484d0 <+79>:    nop  
  40. 29              } 
  41. 30  
  42. 31              return (c);  
  43.    0x080484d1 <+80>:    movsx  eax,BYTE PTR [ebp-0x4]  
  44. 32      }  
  45.    0x080484d5 <+84>:    leave  
  46.    0x080484d6 <+85>:    ret  
  47. End of assembler dump.  
  48. (gdb) 

分析：

  •  在foo_ifelse()中，采用的方法是按順序比較，如滿足條件，則執(zhí)行對(duì)應(yīng)的代碼，否則跳轉(zhuǎn)到下一個(gè)分支再進(jìn)行比較；
  •  在foo_switch()中，下面的這段匯編代碼比較有意思， 
  1. ..  
  2. 21 switch (c) {  
  3.    0x0804848d <+12>:    movsx  eax,BYTE PTR [ebp-0x4]  
  4.    0x08048491 <+16>:    sub    eax,0x30  
  5.    0x08048494 <+19>:    cmp    eax,0x32  
  6.    0x08048497 <+22>:    ja     0x80484c6 <foo_switch+69>  
  7.    0x08048499 <+24>:    mov    eax,DWORD PTR [eax*4+0x80485f0]  
  8.    0x080484a0 <+31>:    jmp    eax  
  9. .. 

注意： 

第17行 jmp eax

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

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

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

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

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

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

  1. >>> ord('1') - 0x30  
  2. >>> ord('0') - 0x30  
  3. (gdb) x /2wx  0*4+0x80485f0  
  4. 0x80485f0:    0x080484a2    0x080484a2  
  5. >>> ord('b') - 0x30  
  6. >>> ord('a') - 0x30  
  7. (gdb) x /2wx 49*4+0x80485f0  
  8. 0x80486b4:    0x080484ae    0x080484ae             
  9. >>> ord('B') - 0x30  
  10. >>> ord('A') - 0x30  
  11. (gdb) x /2wx 17*4+0x80485f0  
  12. 0x8048634:    0x080484ba    0x080484ba 

那么，我們可以大膽的猜測(cè)，雖然c的取值不同但是跳轉(zhuǎn)的IP確實(shí)是精準(zhǔn)無(wú)誤的，一定是編譯階段就被設(shè)定好了，果真如此嗎？接下來(lái)分析一下對(duì)應(yīng)的二進(jìn)制文件foo,

第四步，使用objdump查看foo, 

  1. $ objdump -D foo > /tmp/x  
  2. $ vim /tmp/x  
  3.  509 Disassembly of section .rodata:  
  4.  ...  
  5.  518  80485f0:       a2 84 04 08 a2          mov    %al,0xa2080484  
  6.  519  80485f5:       84 04 08                test   %al,(%eax,%ecx,1)  
  7.  ...  
  8.  534  8048630:       c6 84 04 08 ba 84 04    movb   $0x8,0x484ba08(%esp,%eax,1)  
  9.  535  8048637:       08  
  10.  536  8048638:       ba 84 04 08 c6          mov    $0xc6080484,%edx  
  11.  ...  
  12.  566  80486b0:       c6 84 04 08 ae 84 04    movb   $0x8,0x484ae08(%esp,%eax,1)  
  13.  567  80486b7:       08  
  14.  568  80486b8:       ae                      scas   %es:(%edi),%al  
  15.  569  80486b9:       84 04 08                test   %al,(%eax,%ecx,1)  
  16.  ... 

在0x80485f0地址，存的8個(gè)字節(jié)正好是0x080484a2, 0x080484a2 (注意：按照小端的方式閱讀)

在0x80486b4地址，存的8個(gè)字節(jié)正好是0x080484ae, 0x080484ae

在0x8048634地址，存的8個(gè)字節(jié)正好是0x080484ba,0x080484ba

果然不出所料，要跳轉(zhuǎn)的IP的值正是在編譯的時(shí)候存入了.rodata（只讀數(shù)據(jù)區(qū)）。一旦foo開(kāi)始運(yùn)行，對(duì)應(yīng)的內(nèi)存地址就填寫(xiě)上了正確的待跳轉(zhuǎn)地址，接下來(lái)只不過(guò)是根據(jù)c的取值計(jì)算出對(duì)應(yīng)的IP存放的內(nèi)存起始地址X，從X中取出待跳轉(zhuǎn)的地址，直接跳轉(zhuǎn)就好。 

  1. 16    0x08048499 <+24>:    mov    eax,DWORD PTR [eax*4+0x80485f0]  
  2. 17    0x080484a0 <+31>:    jmp    eax 

到此為止，我們已經(jīng)搞清楚了為什么switch...case...語(yǔ)句相對(duì)于if...else if...else...來(lái)說(shuō)執(zhí)行效率要高的根本原因。簡(jiǎn)言之，編譯的時(shí)候創(chuàng)建了一個(gè)map存于.rodata區(qū)中，運(yùn)行的時(shí)候直接根據(jù)輸入(c的值）查表，找到對(duì)應(yīng)的IP后直接跳轉(zhuǎn)。（省去了cmp, jmp -> cmp, jmp -> cmp, jmp...這一冗長(zhǎng)的計(jì)算過(guò)程。）

總結(jié)：

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

 

【責(zé)任編輯：龐桂玉 TEL：（010）68476606】

 

責(zé)任編輯：龐桂玉 來(lái)源： C語(yǔ)言與C++編程
switch...caseif...else語(yǔ)言
相關(guān)推薦

2011-05-25 14:59:35

if elseswitch case

2023-06-07 08:35:36

2019-09-11 09:09:56

++ii++編程語(yǔ)言

2021-07-21 09:35:36

switchbreakJava

2019-07-05 16:26:06

MySQLcount(1)count(*)

2011-09-13 09:57:25

谷歌云計(jì)算

2025-04-21 00:00:05

2011-04-06 14:20:50

Java編程

2022-10-17 08:03:54

CPUDMAKafka

2011-04-13 09:13:02

Java內(nèi)存

2009-08-19 10:41:14

C# switch和c

2012-03-12 11:48:44

惠普激光打印機(jī)

2023-07-26 07:02:04

2013-01-18 11:16:15

效率

2020-01-15 14:20:07

Node.js應(yīng)用程序javascript

2011-04-25 17:04:28

傳真機(jī)

2022-05-31 14:43:47

微軟AI研究

2022-09-16 15:02:19

戴爾

2022-03-31 16:47:30

mysqlcount面試官

2009-06-08 21:45:46

Javaswitch-case
點(diǎn)贊
收藏

51CTO技術(shù)棧公眾號(hào)