switch case 原理了解

switch case 原理理解

／＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊／

／＊转载?? 作者都不知道是谁。。。＊／

／＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊／

当需要多次比较时，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

int main(void) { ? ? int i, n; ? ? switch(i){ ? ? ? ? case 101: ? ? ? ? ? ? n = 1; ? ? ? ? ? ? break; ? ? ? ? case 102: ? ? ? ? ? ? n = 2; ? ? ? ? ? ? break; ? ? ? ? case 103: ? ? ? ? ? ? n = 3; ? ? ? ? ? ? break; ? ? ? ? default: ? ? ? ? ? ? n = 0; ? ? ? ? ? ? break; ? ? } }

得到的汇编码1.1：

这里可以看出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 五个连续数据

int main(void) { ? ? int i, n; ? ? switch(i){ ? ? ? ? case 101: ? ? ? ? ? ? n = 1; ? ? ? ? ? ? break; ? ? ? ? case 102: ? ? ? ? ? ? n = 2; ? ? ? ? ? ? break; ? ? ? ? case 103: ? ? ? ? ? ? n = 3; ? ? ? ? ? ? break; ? ? ? ? case 104: ? ? ? ? ? ? n = 4; ? ? ? ? ? ? break; ? ? ? ? case 105: ? ? ? ? ? ? n = 5; ? ? ? ? ? ? break; ? ? ? ? default: ? ? ? ? ? ? n = 0; ? ? ? ? ? ? break; ? ? } }

汇编码2.1：

.file ? ?"switch.c" ? ? .text .globl main ? ? .type ? ?main, @function main: ? ? leal ? ?4(%esp), %ecx ? ? andl ? ?$-16, %esp ? ? pushl ? ?-4(%ecx) ? ? pushl ? ?%ebp ? ? movl ? ?%esp, %ebp ? ? pushl ? ?%ecx ? ? subl ? ?$24, %esp ? ? movl ? ?-12(%ebp), %eax ? ? subl ? ?$101, %eax ? ? movl ? ?%eax, -28(%ebp) ? ? cmpl ? ?$4, -28(%ebp) ? ? ja ? ?.L2 ? ? movl ? ?-28(%ebp), %edx ? ? movl ? ?.L8(,%edx,4), %eax ? ? jmp ? ?*%eax ? ? .section ? ?.rodata ? ? .align 4 ? ? .align 4 .L8: ? ? .long ? ?.L3 ? ? .long ? ?.L4 ? ? .long ? ?.L5 ? ? .long ? ?.L6 ? ? .long ? ?.L7 ? ? .text .L3: ? ? movl ? ?$1, -8(%ebp) ? ? jmp ? ?.L11 .L4: ? ? movl ? ?$2, -8(%ebp) ? ? jmp ? ?.L11 .L5: ? ? movl ? ?$3, -8(%ebp) ? ? jmp ? ?.L11 .L6: ? ? movl ? ?$4, -8(%ebp) ? ? jmp ? ?.L11 .L7: ? ? movl ? ?$5, -8(%ebp) ? ? jmp ? ?.L11 .L2: ? ? movl ? ?$0, -8(%ebp) .L11: ? ? addl ? ?$24, %esp ? ? popl ? ?%ecx ? ? popl ? ?%ebp ? ? leal ? ?-4(%ecx), %esp ? ? ret ? ? .size ? ?main, .-main ? ? .ident ? ?"GCC: (GNU) 4.3.2 20081105 (Red Hat 4.3.2-7)"

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

程序2.2 五个比较连续数据

int main(void) { ? ? int i, n; ? ? switch(i){ ? ? ? ? case 101: ? ? ? ? ? ? n = 1; ? ? ? ? ? ? break; ? ? ? ? case 103: ? ? ? ? ? ? n = 2; ? ? ? ? ? ? break; ? ? ? ? case 106: ? ? ? ? ? ? n = 3; ? ? ? ? ? ? break; ? ? ? ? case 109: ? ? ? ? ? ? n = 4; ? ? ? ? ? ? break; ? ? ? ? case 112: ? ? ? ? ? ? n = 5; ? ? ? ? ? ? break; ? ? ? ? default: ? ? ? ? ? ? n = 0; ? ? ? ? ? ? break; ? ? } }

汇编码2，2：

? ?.file ? ?"switch.c" ? ? .text .globl main ? ? .type ? ?main, @function main: ? ? leal ? ?4(%esp), %ecx ? ? andl ? ?$-16, %esp ? ? pushl ? ?-4(%ecx) ? ? pushl ? ?%ebp ? ? movl ? ?%esp, %ebp ? ? pushl ? ?%ecx ? ? subl ? ?$24, %esp ? ? movl ? ?-12(%ebp), %eax ? ? subl ? ?$101, %eax ? ? movl ? ?%eax, -28(%ebp) ? ? cmpl ? ?$11, -28(%ebp) ? ? ja ? ?.L2 ? ? movl ? ?-28(%ebp), %edx ? ? movl ? ?.L8(,%edx,4), %eax ? ? jmp ? ?*%eax ? ? .section ? ?.rodata ? ? .align 4 ? ? .align 4 .L8: ? ? .long ? ?.L3 ? ? .long ? ?.L2 ? ? .long ? ?.L4 ? ? .long ? ?.L2 ? ? .long ? ?.L2 ? ? .long ? ?.L5 ? ? .long ? ?.L2 ? ? .long ? ?.L2 ? ? .long ? ?.L6 ? ? .long ? ?.L2 ? ? .long ? ?.L2 ? ? .long ? ?.L7 ? ? .text .L3: ? ? movl ? ?$1, -8(%ebp) ? ? jmp ? ?.L11 .L4: ? ? movl ? ?$2, -8(%ebp) ? ? jmp ? ?.L11 .L5: ? ? movl ? ?$3, -8(%ebp) ? ? jmp ? ?.L11 .L6: ? ? movl ? ?$4, -8(%ebp) ? ? jmp ? ?.L11 .L7: ? ? movl ? ?$5, -8(%ebp) ? ? jmp ? ?.L11 .L2: ? ? movl ? ?$0, -8(%ebp) .L11: ? ? addl ? ?$24, %esp ? ? popl ? ?%ecx ? ? popl ? ?%ebp ? ? leal ? ?-4(%ecx), %esp ? ? ret ? ? .size ? ?main, .-main ? ? .ident ? ?"GCC: (GNU) 4.3.2 20081105 (Red Hat 4.3.2-7)" ? ? .section ? ?.note.GNU-stack,"",@progbits

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

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

int main(void) { ? ? int i, n; ? ? switch(i){ ? ? ? ? case 100: ? ? ? ? ? ? n = 1; ? ? ? ? ? ? break; ? ? ? ? case 120: ? ? ? ? ? ? n = 2; ? ? ? ? ? ? break; ? ? ? ? case 140: ? ? ? ? ? ? n = 3; ? ? ? ? ? ? break; ? ? ? ? case 160: ? ? ? ? ? ? n = 4; ? ? ? ? ? ? break; ? ? ? ? case 180: ? ? ? ? ? ? n = 5; ? ? ? ? ? ? break; ? ? ? ? default: ? ? ? ? ? ? n = 0; ? ? ? ? ? ? break; ? ? } }

汇编码2.3：

????.file????"switch.c" ????.text .globl main ????.type????main, @function main: ????leal????4(%esp), %ecx ????andl????$-16, %esp ????pushl????-4(%ecx) ????pushl????%ebp ????movl????%esp, %ebp ????pushl????%ecx ????subl????$24, %esp ????movl????-12(%ebp), %eax ????movl????%eax, -28(%ebp) ????cmpl????$140, -28(%ebp) ????je????.L5 ????cmpl????$140, -28(%ebp) ????jg????.L8 ????cmpl????$100, -28(%ebp) ????je????.L3 ????cmpl????$120, -28(%ebp) ????je????.L4 ????jmp????.L2 .L8: ????cmpl????$160, -28(%ebp) ????je????.L6 ????cmpl????$180, -28(%ebp) ????je????.L7 ????jmp????.L2 .L3: ????movl????$1, -8(%ebp) ????jmp????.L11 .L4: ????movl????$2, -8(%ebp) ????jmp????.L11 .L5: ????movl????$3, -8(%ebp) ????jmp????.L11 .L6: ????movl????$4, -8(%ebp) ????jmp????.L11 .L7: ????movl????$5, -8(%ebp) ????jmp????.L11 .L2: ????movl????$0, -8(%ebp) .L11: ????addl????$24, %esp ????popl????%ecx ????popl????%ebp ????leal????-4(%ecx), %esp ????ret ????.size????main, .-main ????.ident????"GCC: (GNU) 4.3.2 20081105 (Red Hat 4.3.2-7)" ????.section????.note.GNU-stack,"",@progbits

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

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

3 更多数据的比较

这里我又进行了更多条case语句的比较，程序源代码和生成的汇编码可以通过附件下载，通过比较，结论与我上面的推测基本相同。具体的原理相信在讲解C／C++编译器原理的书中有提及，希望有人找到后能够发送给我以共同探讨（email：yangyuan.whuyy@yahoo.com.cn）

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

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

switch case 原理了解

热点推荐