switch与跳转表深入分析

更深入一点理解 switch 语句 及 c/c++ 对 const 的处理
                                    谢煜波
------------------------------------------------

转载请注明原作者，以出处~~

------------------------------------------------

前段时间在论坛上看见台湾李维在<>一书中对windows编程模式中,消息处理部分有如下的一些分析:
他说,在消息处理循环中,一般的形式是这样的
MSG msg ;
switch( msg ){
        case WM_XXXXXXX :
                ....
        case WM_XXXXXXX :
                ....
        case WM_XXXXXXX :
                ....
} ;
李维说,这种模式是很低效的,因应经过汇编后,这种C代码会产生如下的汇编代码
        cmp .... .....
        jnz .... .....
        cmp .... .....
        jnz .... .....
        cmp .... .....
        jnz .... .....
如果你的 case 足够多,比如,你有一万条消息需要处理,而不幸的是你把一条最常用的消息
放在了最后一位,那么当这条消息要得到处理,会首先经过一万次的cmp与jnz, 李维认为,这
是非常非常低效的,实在是低效的忍无可忍,无需再忍~~:P

在起初,我也是这样认为的,但近来的阅读及实验却发现,这种看法非常片面,今天就来谈谈这个问题( 所有实验在 linux 平台下完成 )

首先看一到用 c 编写的程序
/* -------------------- filename : ta.c --------------- */
int switch_test_first( int x )
{
        int res ;
        switch( x ){
                case 100 :
                        res = 1 ;
                        break ;
                case 102 :
                        res = 2 ;
                        break ;
                case 103 :
                        res = 3 ;
                        break ;
        }
        return res ;
}
然后,我们用 gcc 将它编译成汇编文件( 使用 -S 开关 )
gcc -S ta.c
将得到如下的汇编文件( ta.s )
        .file   "ta.c"
        .text
.globl switch_test_first
        .type   switch_test_first,@function
switch_test_first:
        pushl   %ebp
        movl    %esp, %ebp
        subl    $8, %esp
        movl    8(%ebp), %eax
        .file   "ta.c"
        .text
.globl switch_test_first
        .type   switch_test_first,@function
switch_test_first:
        pushl   %ebp
        movl    %esp, %ebp
        subl    $8, %esp
        movl    8(%ebp), %eax
        movl    %eax, -8(%ebp)
        cmpl    $102, -8(%ebp)          // 1
        je      .L4                     // 2
        cmpl    $102, -8(%ebp)          // 3   
        jg      .L8                     // 4
        cmpl    $100, -8(%ebp)          // 5
        je      .L3                     // 6
        jmp     .L2                     // 7
.L8:
        cmpl    $103, -8(%ebp)
        je      .L5
        jmp     .L2
.L3:
        movl    $1, -4(%ebp)
        jmp     .L2
.L4:
        movl    $2, -4(%ebp)
        jmp     .L2
.L5:
        movl    $3, -4(%ebp)
.L2:
        movl    -4(%ebp), %eax
        leave
        ret
.Lfe1:
        .size   switch_test_first,.Lfe1-switch_test_first
        .ident  "GCC: (GNU) 3.2.2 20030222 (Red Hat Linux 3.2.2-5)"

注意看文件中 // 1 ~ // 7 的部份,从这个部份,我们可以看出,gcc确实是把一些case语句转成了李维所说的那种方式进行处理,我们看见了代码中存在有众多的 cmpl 与 jmp 语句
这就相当于你使用if..else..一样,但是否总是这样呢?

我们下面改动一下 ta.c 这个文件,在里面再多加一些 case 语句
/* -------------- filename : new_ta.c ------------------- */
int switch_test_first( int x )
{
        int res ;
        switch( x ){
                case 100 :
                        res = 1 ;
                        break ;
                case 102 :
                        res = 2 ;
                        break ;
                case 103 :
                        res = 3 ;
                        break ;
                case 104 :
                        res = 4 ;
                        break ;
                case 105 :
                        res = 5 ;
                        break ;
                case 106 :
                        res = 6 ;
                        break ;
        }
        return res ;
}
这个 new_ta.c 与原来的 ta.c 在结构上完全相同,唯一不同的就是 case 语句的数量变多了,下面我们来编译一下这个文件
gcc -S new_ta.c
下面是我们产生的更新的汇编文件
        .file   "new_ta.c"
        .text
.globl switch_test_first
        .type   switch_test_first,@function
switch_test_first:
        pushl   %ebp
        movl    %esp, %ebp
        subl    $8, %esp
        movl    8(%ebp), %eax
        subl    $100, %eax
        movl    %eax, -8(%ebp)
        cmpl    $6, -8(%ebp)
        ja      .L2
        movl    -8(%ebp), %edx
        movl    .L9(,%edx,4), %eax
        jmp     *%eax
        .section        .rodata
        .align 4
        .align 4
.L9:                             // A
        .long   .L3
        .long   .L2
        .long   .L4
        .long   .L5
        .long   .L6
        .long   .L7
        .long   .L8
        .text
.L3:                            // 1
        movl    $1, -4(%ebp)
        jmp     .L2
.L4:                            // 2
        movl    $2, -4(%ebp)
        jmp     .L2
.L5:                            // 3
        movl    $3, -4(%ebp)
        jmp     .L2             // 4  
.L6:
        movl    $4, -4(%ebp)
        jmp     .L2             // 5
.L7:
        movl    $5, -4(%ebp)    // 6
        jmp     .L2
.L8:                            // 7
        movl    $6, -4(%ebp)
.L2:                           
        movl    -4(%ebp), %eax
        leave
        ret
.Lfe1:
        .size   switch_test_first,.Lfe1-switch_test_first
        .ident  "GCC: (GNU) 3.2.2 20030222 (Red Hat Linux 3.2.2-5)"

仔细比较一下这个最新的 new_ta.s 与前面的 ta.s,精华全在里面了!

[1] [2]

编辑 webmaster