Chinaunix首页 | 论坛 | 博客
  • 博客访问: 8435
  • 博文数量: 6
  • 博客积分: 285
  • 博客等级: 二等列兵
  • 技术积分: 70
  • 用 户 组: 普通用户
  • 注册时间: 2009-03-28 15:22
文章分类
文章存档

2009年(6)

我的朋友
最近访客

分类: C/C++

2009-04-02 11:10:46

 

/**************************/

/*转载请注明原作者及出处*/

/**************************/

当需要多次比较时,switch语句的效率比if-else if…… else语句(以后简称muti-if语句)的效率要高,这是我一直以来的理解,但是昨晚讨论到一个问题,这种“高效率”如何实现?今天早上又看到《更深入一点理解switch语句及c/c++对const的处理》和《》这两篇文章,前者(以后为[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语句的比较,程序源代码和生成的汇编码可以通过附件下载,通过比较,结论与我上面的推测基本相同。具体的原理相信在讲解C/C++编译器原理的书中有提及,希望有人找到后能够发送给我以共同探讨(email:yangyuan.whuyy@yahoo.com.cn)

文件:switch.zip
大小:1KB
下载:下载

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

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

阅读(1150) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~