`
tianlihu
  • 浏览: 314019 次
  • 性别: Icon_minigender_1
  • 来自: 石家庄
社区版块
存档分类
最新评论

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

GCCC#CC++PHP 
阅读更多
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 
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： 
   .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    $102, -28(%ebp)
    je    .L4
    cmpl    $103, -28(%ebp)
    je    .L5
    cmpl    $101, -28(%ebp)
    jne    .L8
.L3:
    movl    $1, -8(%ebp)
    jmp    .L9
.L4:
    movl    $2, -8(%ebp)
    jmp    .L9
.L5:
    movl    $3, -8(%ebp)
    jmp    .L9
.L8:
    movl    $0, -8(%ebp)
.L9:
    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语句的效率与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语句的比较，程序源代码和生成的汇编码可以通过附件下载，通过比较，结论与我上面的推测基本相同。

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

我们知道，在C中，字符型实际上也是作为整型来存储的，所以这个问题实际上是指switch语句只支持整型数据。由上面的讨论可以知道char的结果与整型应该是相同的
分享到：
| 堆与栈，静态变量和全局变量的区别
评论
1 楼 di1984HIT 2013-05-01  
明天晚上学习一下。
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

    51单片机switch语句的控制P0口8位LED的点亮状态源代码

    在51单片机编程中，`switch`语句是一种常用的条件控制结构，它用于根据不同的情况执行不同的代码块。...通过分析源代码和理解`switch`结构的工作原理，我们可以学习到单片机控制和C语言编程的基础知识。

    编译原理课程设计——算术表达式、for、while语句转换为四元式.pdf

    "编译原理课程设计——算术表达式、for、while语句转换为四元式" 本设计报告的目的是设计一个语法制导翻译器，将算术表达式、for语句、while语句翻译成四元式。下面是设计思路和算法流程： 一、设计目标 设计一个...

    java推荐书籍(条件及循环语句)汇编.pdf

    本文将详细介绍Java中的条件语句和循环语句，包括if语句、switch语句、while循环、do-while循环、for循环等。 一、条件语句 条件语句是Java中的一种控制流语句，用于根据条件来执行不同的代码块。Java中的条件语句...

    一个超轻量级的反汇编引擎

    - 使用了大量的 `switch` 语句来匹配不同的操作码，并执行相应的反汇编操作。 - 当遇到某些特定的操作码时，会调用 `DisassembleMem32` 函数来进行更深层次的解析。 3. **实现细节**： - 该函数覆盖了大量的x86...

    您可能不了解C / C ++中的switch语句

    本文将深入探讨`switch`语句的工作原理，特别是在VC++环境下的实现方式，以及如何通过反汇编（reverse engineering）来理解其内部机制。我们将涉及汇编语言（ASM）、C++和Visual Studio的开发环境（Dev）相关的知识...

    编译原理课程设计--简单编译器

    总结来说，这个项目通过 lex 和 yacc 实现了一个从汇编语言到C语言的编译器，不仅涉及到了编译器的基本原理，还涉及到具体实现的细节和技术挑战。对于学习编译原理的学生而言，这是一个很好的实践项目，能深入理解...

    合肥工业大学编译原理课程设计报告

    【编译原理】\n\n编译原理是一门研究如何将高级编程语言转换为机器可理解的低级语言（如汇编代码或机器代码）的学科。在这个过程中，编译器扮演了关键角色，它包括词法分析、语法分析、语义分析以及代码生成等阶段。...

    C/C++的汇编分析

    6. **控制流**：条件语句（如IF-ELSE）和switch语句在汇编中通过条件跳转实现。switch语句可能涉及跳转表。 7. **异常处理**：C++的异常处理在汇编中涉及到特殊的栈框架和异常处理机制，如SEH（Windows）或EH（Unix...

    00－99计数器汇编程序

    主函数中使用if语句来判断按键的状态，并使用switch语句来选择不同的显示模式。 实验及实践 实验中使用了AT89S51单片机，连接了手动计数的按钮和数码管。实验结果表明，程序可以正确地实现计数和显示。 结论 该...

    汇编语言8255交通灯实验六

    在实验中，我们使用了switch语句来实现交通灯状态的控制。switch语句可以根据不同的情况来执行不同的指令。在我们的实验中，我们使用了五种不同的交通灯状态，每种状态都有其对应的IO端口输出。 下面是我们的算法...

    汇编语言指令集(附带c语言简单指令)

    3. **控制结构**：包括条件语句（if...else）、循环（for、while）、开关语句（switch...case）。 4. **函数定义与调用**：如`void print(int num) { printf("%d", num); }`，定义了一个打印整数的函数，然后通过`...

    C程序设计试题汇编（谭浩强版）

    这包括关键字、数据类型（如int、char、float、double）、变量声明、运算符（算术、关系、逻辑、位操作符）以及基本的控制结构（如if语句、switch语句、for和while循环）。通过填空题，学习者可以巩固这些基础知识，...

    C# .NET试题汇编答案

    3. **异常处理**：理解try-catch-finally语句，如何自定义异常，以及何时使用throw关键字。 4. **集合与泛型**：List、Dictionary, TValue>等常用集合的使用，泛型的原理和优势。 5. **LINQ（Language Integrated ...

    “微机原理与汇编语言”期末试题及答案.pdf

    4. 程序设计的基本结构包括顺序结构、选择结构（如if语句）、循环结构（如for和while）以及分支结构（如switch语句）。 5. 中断处理是CPU对突发事件的响应机制，包括保存当前状态（断点）、执行中断服务程序、恢复...

    C程序设计试题汇编

    4. 流程控制：学习if语句、switch语句、while循环、for循环等控制流程的语句。 二、函数与程序结构 函数是C语言中的重要组成部分，能够实现代码的复用和模块化。书中会介绍： 1. 函数定义与调用：如何定义函数，...

    C程序设计试题汇编.zip

    4. **流程控制语句**：包括条件语句（if...else、switch...case）、循环语句（for、while、do...while）以及跳转语句（break、continue）。理解并熟练使用这些语句能实现程序的逻辑控制。 5. **函数**：函数是C语言...

    北航编译课程设计中难度，有switch_case无for

    这表明编译器需要理解和处理不包含`for`循环但包含`switch`语句的语法结构。 编译器是将高级编程语言（如C、C++等）翻译成机器可执行的汇编或机器码的程序。在这个课程设计中，学生可能被要求完成以下任务： 1. **...

Magicbox
Global site tag (gtag.js) - Google Analytics