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

嵌入式ARM 2020-06-19 00:00


作者:李肖遥

来源:技术让梦想更伟大


在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语言,去你的策略模式!



免责声明:整理文章为传播相关技术,版权归原作者所有,如有侵权,请联系删除
嵌入式ARM 关注这个时代最火的嵌入式ARM,你想知道的都在这里。
评论
  •       在科技日新月异的今天,智能手机已不再仅仅是通讯工具,它更成为了我们娱乐、学习、工作的核心设备。特别是在游戏体验方面,用户对于手机的性能要求愈发严苛,追求极致流畅与沉浸感。正是基于这样的市场需求,一加品牌于2024年12月26日正式推出了其最新的游戏性能旗舰——一加 Ace 5系列,包括一加 Ace 5与一加 Ace 5 Pro两款力作。这一系列深度聚焦于性能与游戏体验,旨在为用户带来前所未有的游戏盛宴。骁龙8系旗舰平台,性能跃升新高度
    科技财经汇 2024-12-26 22:31 51浏览
  • 起源与基础20 世纪 60 年代:可编程逻辑设备(PLD)的概念出现,一种被称为 “重构能力” 的芯片的可编程性吸引了许多工程师和学者。20 世纪 70 年代:最早的可编程逻辑器件 PLD 诞生,其输出结构是可编程的逻辑宏单元,它的硬件结构设计可由软件完成,设计比纯硬件的数字电路更灵活,但结构简单,只能实现小规模电路。诞生与发展20 世纪 80 年代中期:为弥补 PLD 只能设计小规模电路的缺陷,复杂可编程逻辑器件 CPLD 被推出,它具有更复杂的结构,能够实现较大规模的电路设计。1988 年:
    Jeffreyzhang123 2024-12-27 10:41 45浏览
  • 在科技飞速发展的今天,汽车不再仅仅是一种交通工具,更是一个融合了先进技术的移动智能空间。汽车电子作为汽车产业与电子技术深度融合的产物,正以前所未有的速度推动着汽车行业的变革,为我们带来更加智能、安全、舒适的出行体验。汽车电子的发展历程汽车电子的发展可以追溯到上世纪中叶。早期,汽车电子主要应用于发动机点火系统和简单的电子仪表,功能相对单一。随着半导体技术的不断进步,集成电路被广泛应用于汽车领域,使得汽车电子系统的性能得到了显著提升。从电子燃油喷射系统到防抱死制动系统(ABS),从安全气囊到车载导航
    Jeffreyzhang123 2024-12-27 11:53 43浏览
  • 近日,紫光展锐正式推出基于RTOS系统的旗舰产品W337,它拥有丰富特性和超低功耗,进一步壮大紫光展锐的智能穿戴产品组合,面向中高端和广阔的智能穿戴市场,提供先进的技术解决方案。  性能卓越,成就强悍RTOS穿戴芯 双核CPU架构:紫光展锐W337基于RTOS系统首创双核CPU架构,可根据系统的负载情况动态调整功耗,当系统负载较低时,降低一个或两个核心的频率和电压。由于有两个核心分担负载,每个核心的发热相对较低,进一步降低了系统整体的散热需求。双核架构更好地实现了负
    紫光展锐 2024-12-26 18:13 45浏览
  • 在谐振器(无源晶振)S&A250B测试软件中,DLD1到DLD7主要用于分析晶体在不同驱动功率下的阻抗变化。此外,还有其他DLD参数用于反映晶振的磁滞现象,以及其频率和功率特性。这些参数可以帮助工程师全面了解KOAN晶振在不同功率条件下的动态特性,从而优化其应用和性能。磁滞现象晶振的磁滞现象(Hysteresis)是指在驱动功率变化时,晶体的阻抗或频率无法立即恢复至初始状态,而表现出滞后效应。1. DLDH: Hysteresis Ratio (MaxR/MinR)在不同驱动
    koan-xtal 2024-12-26 12:41 103浏览
  • 施密特触发器光耦施密特触发器光耦(Schmitt Trigger Optocoupler)是一种将光耦和施密特触发器电路相结合的电子元件。它不仅具备光耦的电气隔离功能,还具备施密特触发器的噪声抑制和信号整形能力。施密特触发器光耦的详细结构LED部分:LED是由半导体材料制成的,通常封装在一个透明的塑料或玻璃外壳中。其主要功能是在输入端电流流过时产生光信号。光接收器部分:光接收器通常是一个光敏晶体管或光敏二极管,其基区(或PN结)对光信号敏感。当接收到来自LED的光信号时,光接收器产生一个与光强度
    晶台光耦 2024-12-26 17:19 38浏览
  • 图森未来的“夺权之争”拉扯了这么久,是该画上句号了。大约9年前,侯晓迪、陈默、郝佳男等人共同创立了图森未来,初衷是以L4级别的无人驾驶卡车技术为全球物流运输行业赋能。此后,先后获得了5轮融资,累计融资额超过6.5亿美元,并于2021年成功在美国纳斯达克上市,成为全球自动驾驶第一股。好景不长,2023年市场屡屡传出图森未来裁员、退市的消息。今年1月份,图森未来正式宣布退市,成为了全球首个主动退市的自动驾驶公司。上市匆匆退市也匆匆,其背后深层原因在于高层的频繁变动以及企业的转型调整。最近,图森未来的
    刘旷 2024-12-27 10:23 19浏览
  • 今年AI技术的话题不断,随着相关应用服务的陆续推出,AI的趋势已经是一个明确的趋势及方向,这也连带使得AI服务器的出货量开始加速成长。AI服务器因为有着极高的运算效能,伴随而来的即是大量的热能产生,因此散热效能便成为一个格外重要的议题。其实不只AI服务器有着散热的问题,随着Intel及AMD 的CPU规格也不断地在提升,非AI应用的服务器的散热问题也是不容小觑的潜在问题。即便如此,由于目前的液冷技术仍有许多待克服的地方,例如像是建置成本昂贵,机壳、轨道、水路、数据中心等项目都得重新设计来过,维修
    百佳泰测试实验室 2024-12-26 16:33 100浏览
  • 发明阶段(20世纪80年代至90年代)起源:当时ASIC设计成本高,周期长,流片失败率高,业界需要一种通用的半导体器件进行流片前测试和验证,可编程逻辑器件就此产生。诞生:1980年,Xilinx公司成立。1985年,Ross Freeman制造了第一片PFGA芯片XC2064,采用4输入,1输出的LUT和FF结合的基本逻辑单元。发展阶段(1992年至1999年)容量提升:FPGA容量不断上涨,芯片面积逐渐增大,为架构穿心提供空间,复杂功能可以实现。布线问题凸显:缩着芯片复杂度增加,片上资源的互连
    Jeffreyzhang123 2024-12-27 10:26 54浏览
  • 随着科技的飞速进步,智能家电已成为现代家庭生活中密不可分的一部分。不论是自行出动,清扫地板的扫地机器人、还是可提前准备食材清单的智能冰箱,或者是可自动调节洗衣程序的智能洗衣烘干机,这些智能家电装置正以前所未有的方式改变着我们的日常生活。除了上述提到的智能家电,还有更多你想象得到的便利装置,例如智能除湿机、空气清净机、净水器、智能风扇、语音助理及智能灯具等等。这些装置不仅为现代人的居家生活中带来了许多便利,让我们能够更轻松地管理家务,还可进一步提升生活质量,节省宝贵的时间和能源。正所谓「科技始终来
    百佳泰测试实验室 2024-12-26 16:37 34浏览
  • 新能源汽车市场潮起潮落,只有潮水退去,才能看清谁在裸泳。十年前,一批新能源汽车新势力带着创新的理念和先进的技术,如雨后春笋般涌入中国汽车市场,掀起一场新旧势力的角逐。经历市场的激烈洗礼与投资泡沫的挤压,蔚来、理想、小鹏等新势力车企脱颖而出,刷爆网络。不曾想,今年新势力车企杀出一匹“超级黑马”,爬上新势力车企销量榜前三,将蔚来、小鹏等昔日强者甩在了身后,它就是零跑汽车。公开数据显示,11月份,零跑汽车实现新车交付量约4.02万辆,同比增长117%,单月销量首次突破4万辆;小鹏汽车当月共交付新车约3
    刘旷 2024-12-26 10:53 155浏览
我要评论
0
点击右上角,分享到朋友圈 我知道啦
请使用浏览器分享功能 我知道啦