当前位置：首页 > 公众号精选 > 嵌入式微处理器

揭秘:：switch...case为什么比if...else执行效率高？

时间：2020-06-22 12:57:23
关键字： switch    se   
手机看文章

扫描二维码
随时随地手机看文章

[导读]作者:李肖遥 来源:技术让梦想更伟大 在C语言中，条件判断语句是程序的重要组成部分，也是系统业务逻辑的控制手段，教科书告诉我们switch...case...语句比if...else if...else执行效率要高，但这到底是为什么呢？本文尝试从汇编的角度予以分析并揭晓其中的奥秘

<section style="display: none;" data-label="powered by xmt.cn">


作者:李肖遥

来源:技术让梦想更伟大


在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)

分析：

  1. 在foo_ifelse()中，采用的方法是按顺序比较，如满足条件，则执行对应的代码，否则跳转到下一个分支再进行比较；

  2. 在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快！


-END-




推荐阅读



【01】图文并茂，一次搞定C语言结构体内存对齐！（包含完整源码）
【02】C语言/C++基本语句编程风格
【03】基于C99规范，最全C语言预处理知识总结
【04】常用于单片机的接口适配器模式C语言实现
【05】C语言，去你的策略模式!



免责声明：整理文章为传播相关技术，版权归原作者所有，如有侵权，请联系删除
section>

免责声明：本文内容由21ic获得授权后发布，版权归原作者所有，本平台仅提供信息存储服务。文章仅代表作者个人观点，不代表本平台立场，如有问题，请联系我们，谢谢！

嵌入式ARM

扫描二维码，关注更多精彩内容

本站声明： 本文章由作者或相关机构授权发布，目的在于传递更多信息，并不代表本站赞同其观点，本站亦不保证或承诺内容真实性等。需要转载请联系该专栏作者，如若文章内容侵犯您的权益，请及时联系本站删除。
换一批
延伸阅读
[通信先锋]

阿维塔、赛力斯已入股！华为引望可能成“中国博世”

9月2日消息，不造车的华为或将催生出更大的独角兽公司，随着阿维塔和赛力斯的入局，华为引望愈发显得引人瞩目。

关键字： 阿维塔 塞力斯 华为
[美通社全球TMT]

Trianz与AWS达成战略合作协议，彻底改变云采用和管理方式

加利福尼亚州圣克拉拉县2024年8月30日 /美通社/ -- 数字化转型技术解决方案公司Trianz今天宣布，该公司与Amazon Web Services （AWS）签订了...

关键字： AWS AN BSP 数字化
[美通社全球TMT]

人工智能驱动工具SODA V将颠覆汽车市场，使汽车开发时间和成本降低90%

伦敦2024年8月29日 /美通社/ -- 英国汽车技术公司SODA.Auto推出其旗舰产品SODA V，这是全球首款涵盖汽车工程师从创意到认证的所有需求的工具，可用于创建软件定义汽车。 SODA V工具的开发耗时1.5...

关键字： 汽车 人工智能 智能驱动 BSP
[美通社全球TMT]

从容应对未知风险----解密亚马逊云科技的韧性之道

北京2024年8月28日 /美通社/ -- 越来越多用户希望企业业务能7×24不间断运行，同时企业却面临越来越多业务中断的风险，如企业系统复杂性的增加，频繁的功能更新和发布等。如何确保业务连续性，提升韧性，成...

关键字： 亚马逊 解密 控制平面 BSP
[通信先锋]

中国游戏市场开始复苏！腾讯、网易等巨头缩减在日本投资

8月30日消息，据媒体报道，腾讯和网易近期正在缩减他们对日本游戏市场的投资。

关键字： 腾讯 编码器 CPU
[通信先锋]

独立自主！华为董事：致力打造不依赖西方的技术

8月28日消息，今天上午，2024中国国际大数据产业博览会开幕式在贵阳举行，华为董事、质量流程IT总裁陶景文发表了演讲。

关键字： 华为 12nm EDA 半导体
[通信先锋]

华为张平安：数字世界话语权最终由生态繁荣决定！

8月28日消息，在2024中国国际大数据产业博览会上，华为常务董事、华为云CEO张平安发表演讲称，数字世界的话语权最终是由生态的繁荣决定的。

关键字： 华为 12nm 手机 卫星通信
[美通社全球TMT]

中国通信服务公布2024年中期业绩

要点： 有效应对环境变化，经营业绩稳中有升 落实提质增效举措，毛利润率延续升势 战略布局成效显著，战新业务引领增长 以科技创新为引领，提升企业核心竞争力 坚持高质量发展策略，塑强核心竞争优势...

关键字： 通信 BSP 电信运营商 数字经济
[美通社全球TMT]

NVI技术创新联盟成立！自主生态将带动产业链高速发展

北京2024年8月27日 /美通社/ -- 8月21日，由中央广播电视总台与中国电影电视技术学会联合牵头组建的NVI技术创新联盟在BIRTV2024超高清全产业链发展研讨会上宣布正式成立。 活动现场 NVI技术创新联...

关键字： VI 传输协议 音频 BSP
[美通社全球TMT]

软通动力与长三角投资达成战略合作 共谋数字生态新发展

北京2024年8月27日 /美通社/ -- 在8月23日举办的2024年长三角生态绿色一体化发展示范区联合招商会上，软通动力信息技术（集团）股份有限公司（以下简称"软通动力"）与长三角投资（上海）有限...

关键字： BSP 信息技术
关闭
关闭