现在的位置: 首页 > 综合 > 正文

通过汇编码理解switch语句的原理

2013年11月08日 ⁄ 综合 ⁄ 共 7473字 ⁄ 字号 小 中 大 ⁄ 评论关闭

http://blog.chinaunix.net/u3/94078/showart.php?id=1888387 

当需要多次比较时，switch语句的效率比if-else if……
else语句（以后简称muti－if语句）的效率要高，这是我一直以来的理解，但是昨晚讨论到一个问题，这种“高效率”如何实现？今天早上又看到《更深入一点理解switch语句及c/c++对const的处理》和《透过IL看C#
(1)switch语句》这两篇文章，前者（以后为［1］）没有提及case语句中大跨度离散值的原理，后者（以后为［2］）使用的离散数据量又比较小，而且该文侧重于用C＃，由于不是很了解，不发表评论。 

于是就写了一组程序，用gcc编译成汇编码（使用－S开关），
通过解读这些汇编码可以很好的帮助理解switch的原理。文中所涉及的环境为如下,Linux version 2.6.27.5-117.fc10.i686 (mockbuild@x86-7.fedora.phx.redhat.com) (gcc
version 4.3.2 20081105 (Red Hat 4.3.2-7) (GCC) ) #1 SMP Tue Nov 18 12:19:59 EST
2008(取自/proc/version) 

1.三个数据的比较 

程序1.1 

C代码 
  1. int main(void)  
  2. {  
  3.     int i, n;  
  4.     switch(i){  
  5.         case 101:  
  6.             n = 1;  
  7.             break;  
  8.         case 102:  
  9.             n = 2;  
  10.             break;  
  11.         case 103:  
  12.             n = 3;  
  13.             break;  
  14.         default:  
  15.             n = 0;  
  16.             break;  
  17.     }  
  18. }  

得到的汇编码1.1： 

汇编代码 
  1.    .file    "switch.c"  
  2.     .text  
  3. .globl main  
  4.     .type    main, @function  
  5. main:  
  6.     leal    4(%esp), %ecx  
  7.     andl    $-16, %esp  
  8.     pushl    -4(%ecx)  
  9.     pushl    %ebp  
  10.     movl    %esp, %ebp  
  11.     pushl    %ecx  
  12.     subl    $24, %esp  
  13.     movl    -12(%ebp), %eax  
  14.     movl    %eax, -28(%ebp)  
  15.     cmpl    $102, -28(%ebp)  
  16.     je    .L4  
  17.     cmpl    $103, -28(%ebp)  
  18.     je    .L5  
  19.     cmpl    $101, -28(%ebp)  
  20.     jne    .L8  
  21. .L3:  
  22.     movl    $1, -8(%ebp)  
  23.     jmp    .L9  
  24. .L4:  
  25.     movl    $2, -8(%ebp)  
  26.     jmp    .L9  
  27. .L5:  
  28.     movl    $3, -8(%ebp)  
  29.     jmp    .L9  
  30. .L8:  
  31.     movl    $0, -8(%ebp)  
  32. .L9:  
  33.     addl    $24, %esp  
  34.     popl    %ecx  
  35.     popl    %ebp  
  36.     leal    -4(%ecx), %esp  
  37.     ret  
  38.     .size    main, .-main  
  39.     .ident    "GCC: (GNU) 4.3.2 20081105 (Red Hat 4.3.2-7)"  
  40.     .section    .note.GNU-stack,"",@progbits  

这里可以看出switch语句的效率与muti－if语句的效率基本相当，［1］中认为：“gcc确实是把一些case语句转成了李维所说的那种方式进行处理,我们看见了代码中存在有众多的
cmpl 与 jmp
语句这就相当于你使用if..else..一样”，但是如果观察仔细的话，可以看出和if语句还是有区别的（事实上我第一次也没有细看，但是在后面的实验中，我发现了switch语句的优化，回过头来才发现），
switch对比较的顺序自动进行了优化， cmpl的顺序与case的顺序是不同的，
先比较的是102， 然后才是103， 101，这就相当于我们人为的对muti-if语句进行了优先顺序调整，尽管结果可能与我们预期的不同，但是编译器的确这样做了，
这点在后面的实验中尤为明显。 

在［2］中，作者说C＃在3个数据，且数据连续的情况下造表，在数据取值比较不连续的情况下也是造表然后填空数据，在数据取值非常不连续的情况下和muti-if比较相同，而且顺序与case的顺序相同。该文中对switch（int）的探讨也至此完结。 

2.五个数据的比较 

程序2.1 五个连续数据 

C代码 
  1. int main(void)  
  2. {  
  3.     int i, n;  
  4.     switch(i){  
  5.         case 101:  
  6.             n = 1;  
  7.             break;  
  8.         case 102:  
  9.             n = 2;  
  10.             break;  
  11.         case 103:  
  12.             n = 3;  
  13.             break;  
  14.         case 104:  
  15.             n = 4;  
  16.             break;  
  17.         case 105:  
  18.             n = 5;  
  19.             break;  
  20.         default:  
  21.             n = 0;  
  22.             break;  
  23.     }  
  24. }  

汇编码2.1： 

汇编代码 
  1. .file    "switch.c"  
  2.     .text  
  3. .globl main  
  4.     .type    main, @function  
  5. main:  
  6.     leal    4(%esp), %ecx  
  7.     andl    $-16, %esp  
  8.     pushl    -4(%ecx)  
  9.     pushl    %ebp  
  10.     movl    %esp, %ebp  
  11.     pushl    %ecx  
  12.     subl    $24, %esp  
  13.     movl    -12(%ebp), %eax  
  14.     subl    $101, %eax  
  15.     movl    %eax, -28(%ebp)  
  16.     cmpl    $4, -28(%ebp)  
  17.     ja    .L2  
  18.     movl    -28(%ebp), %edx  
  19.     movl    .L8(,%edx,4), %eax  
  20.     jmp    *%eax  
  21.     .section    .rodata  
  22.     .align 4  
  23.     .align 4  
  24. .L8:  
  25.     .long    .L3  
  26.     .long    .L4  
  27.     .long    .L5  
  28.     .long    .L6  
  29.     .long    .L7  
  30.     .text  
  31. .L3:  
  32.     movl    $1, -8(%ebp)  
  33.     jmp    .L11  
  34. .L4:  
  35.     movl    $2, -8(%ebp)  
  36.     jmp    .L11  
  37. .L5:  
  38.     movl    $3, -8(%ebp)  
  39.     jmp    .L11  
  40. .L6:  
  41.     movl    $4, -8(%ebp)  
  42.     jmp    .L11  
  43. .L7:  
  44.     movl    $5, -8(%ebp)  
  45.     jmp    .L11  
  46. .L2:  
  47.     movl    $0, -8(%ebp)  
  48. .L11:  
  49.     addl    $24, %esp  
  50.     popl    %ecx  
  51.     popl    %ebp  
  52.     leal    -4(%ecx), %esp  
  53.     ret  
  54.     .size    main, .-main  
  55.     .ident    "GCC: (GNU) 4.3.2 20081105 (Red Hat 4.3.2-7)"  

可以看出，这里switch确实如同［1］［2］中所述，编译器自造了.L8指向的表，表中标明了case跳转的入口，由此可见，这种情况下swithc效率确实比muti-if高，通过减去最小值所的的偏移来在表中寻找跳转入口。 

程序2.2 五个比较连续数据 

C代码 
  1. int main(void)  
  2. {  
  3.     int i, n;  
  4.     switch(i){  
  5.         case 101:  
  6.             n = 1;  
  7.             break;  
  8.         case 103:  
  9.             n = 2;  
  10.             break;  
  11.         case 106:  
  12.             n = 3;  
  13.             break;  
  14.         case 109:  
  15.             n = 4;  
  16.             break;  
  17.         case 112:  
  18.             n = 5;  
  19.             break;  
  20.         default:  
  21.             n = 0;  
  22.             break;  
  23.     }  
  24. }  

汇编码2.2： 

汇编代码 
  1.    .file    "switch.c"  
  2.     .text  
  3. .globl main  
  4.     .type    main, @function  
  5. main:  
  6.     leal    4(%esp), %ecx  
  7.     andl    $-16, %esp  
  8.     pushl    -4(%ecx)  
  9.     pushl    %ebp  
  10.     movl    %esp, %ebp  
  11.     pushl    %ecx  
  12.     subl    $24, %esp  
  13.     movl    -12(%ebp), %eax  
  14.     subl    $101, %eax  
  15.     movl    %eax, -28(%ebp)  
  16.     cmpl    $11, -28(%ebp)  
  17.     ja    .L2  
  18.     movl    -28(%ebp), %edx  
  19.     movl    .L8(,%edx,4), %eax  
  20.     jmp    *%eax  
  21.     .section    .rodata  
  22.     .align 4  
  23.     .align 4  
  24. .L8:  
  25.     .long    .L3  
  26.     .long    .L2  
  27.     .long    .L4  
  28.     .long    .L2  
  29.     .long    .L2  
  30.     .long    .L5  
  31.     .long    .L2  
  32.     .long    .L2  
  33.     .long    .L6  
  34.     .long    .L2  
  35.     .long    .L2  
  36.     .long    .L7  
  37.     .text  
  38. .L3:  
  39.     movl    $1, -8(%ebp)  
  40.     jmp    .L11  
  41. .L4:  
  42.     movl    $2, -8(%ebp)  
  43.     jmp    .L11  
  44. .L5:  
  45.     movl    $3, -8(%ebp)  
  46.     jmp    .L11  
  47. .L6:  
  48.     movl    $4, -8(%ebp)  
  49.     jmp    .L11  
  50. .L7:  
  51.     movl    $5, -8(%ebp)  
  52.     jmp    .L11  
  53. .L2:  
  54.     movl    $0, -8(%ebp)  
  55. .L11:  
  56.     addl    $24, %esp  
  57.     popl    %ecx  
  58.     popl    %ebp  
  59.     leal    -4(%ecx), %esp  
  60.     ret  
  61.     .size    main, .-main  
  62.     .ident    "GCC: (GNU) 4.3.2 20081105 (Red Hat 4.3.2-7)"  
  63.     .section    .note.GNU-stack,"",@progbits  

这里也如［2］所述，
建立了一个长度为case中最大值与最小值之差的表， case中未定义的则转到defalut来执行。 

程序2.3 五个非常不连续的数据 

C代码 
  1. int main(void)  
  2. {  
  3.     int i, n;  
  4.     switch(i){  
  5.         case 100:  
  6.             n = 1;  
  7.             break;  
  8.         case 120:  
  9.             n = 2;  
  10.             break;  
  11.         case 140:  
  12.             n = 3;  
  13.             break;  
  14.         case 160:  
  15.             n = 4;  
  16.             break;  
  17.         case 180:  
  18.             n = 5;  
  19.             break;  
  20.         default:  
  21.             n = 0;  
  22.             break;  
  23.     }  
  24. }  

汇编码2.3： 

汇编代码 
  1.     .file    "switch.c"  
  2.     .text  
  3. .globl main  
  4.     .type    main, @function  
  5. main:  
  6.     leal    4(%esp), %ecx  
  7.     andl    $-16, %esp  
  8.     pushl    -4(%ecx)  
  9.     pushl    %ebp  
  10.     movl    %esp, %ebp  
  11.     pushl    %ecx  
  12.     subl    $24, %esp  
  13.     movl    -12(%ebp), %eax  
  14.     movl    %eax, -28(%ebp)  
  15.     cmpl    $140, -28(%ebp)  
  16.     je    .L5  
  17.     cmpl    $140, -28(%ebp)  
  18.     jg    .L8  
  19.     cmpl    $100, -28(%ebp)  
  20.     je    .L3  
  21.     cmpl    $120, -28(%ebp)  
  22.     je    .L4  
  23.     jmp    .L2  
  24. .L8:  
  25.     cmpl    $160, -28(%ebp)  
  26.     je    .L6  
  27.     cmpl    $180, -28(%ebp)  
  28.     je    .L7  
  29.     jmp    .L2  
  30. .L3:  
  31.     movl    $1, -8(%ebp)  
  32.     jmp    .L11  
  33. .L4:  
  34.     movl    $2, -8(%ebp)  
  35.     jmp    .L11  
  36. .L5:  
  37.     movl    $3, -8(%ebp)  
  38.     jmp    .L11  
  39. .L6:  
  40.     movl    $4, -8(%ebp)  
  41.     jmp    .L11  
  42. .L7:  
  43.     movl    $5, -8(%ebp)  
  44.     jmp    .L11  
  45. .L2:  
  46.     movl    $0, -8(%ebp)  
  47. .L11:  
  48.     addl    $24, %esp  
  49.     popl    %ecx  
  50.     popl    %ebp  
  51.     leal    -4(%ecx), %esp  
  52.     ret  
  53.     .size    main, .-main  
  54.     .ident    "GCC: (GNU) 4.3.2 20081105 (Red Hat 4.3.2-7)"  
  55.     .section    .note.GNU-stack,"",@progbits  

可以看到，这里switch又进行了二分法查找的优化，
而且当我把程序中“100， 120， 140， 160，
180”的顺序任意打乱后，得到的汇编码都是相同的，由此可以推测，switch在编译时会先获得case中的各值，然后进行排序，最后生成使用二分法优化的查找比较模式。 

另外，我推测使用造表法和二分查表法的应该是依据case中最大值与最小值之差与case语句个数来取舍的。 

3 更多数据的比较 

这里我又进行了更多条case语句的比较，程序源代码和生成的汇编码可以通过附件下载，通过比较，结论与我上面的推测基本相同。 

4 为什么C/C++中switch语句需要的是整型或字符型 

我们知道，在C中，字符型实际上也是作为整型来存储的，所以这个问题实际上是指switch语句只支持整型数据。由上面的讨论可以知道char的结果与整型应该是相同的 

返回
【上篇】
【下篇】

作者:

抱歉!评论已关闭.

返回首页

Copyright © 2013-2018 学步园  保留所有权利.
软文销售 QQ客服：2265327166 点击这里给我发消息（其他合作也可洽谈）
必威体育
必威电竞