关于switch语句

     最近比较关注性能优化这方面的东西，性能优化首先考虑的应该是架构和算法，如果选错了算法，比如排序非要用冒泡排序，对于大量的随机数据，无论怎么优化也不能提升速度。所以应该首先找到瓶颈，针对瓶颈进行优化。这个方面按下不提，今天主要描述我对switch语句的理解。

     switch语句有两种情况，一种情况是switch中的事件号是连续的，另外一种是事件号不连续。如下面的代码。如果去掉注释，事件号是不连续的，保留注释，时间号是连续的。下面我们会讲两种情况，编译出来的代码分别是什么样子的。

typedef  enum OPCODE{

        EVENT1 = 1000,
        EVENT2,
        EVENT3,
        EVENT4 /*= 2000*/,
        EVENT5,
        EVENT6,
        EVENT7 /*=20000*/,
        EVENT8,

        EVENT9,
        EVENT10 /*= 30000*/,
        EVENT11,
        EVENT12,
        EVENT13 /*= 40000*/,
        EVENT14,
        EVENT15,
        EVENT16,
}OpCode;

    我的测试程序如下：简单的说就是随机选择16个事件号中的一个，来测试switch语句。通过TIMES =1亿次进入switch 语句，观察性能。

#include<stdio.h>
#include<stdlib.h>
#include<time.h>



typedef  enum OPCODE{

                EVENT1 = 1000,
                EVENT2,
                EVENT3,
                EVENT4 /*= 2000*/,
                EVENT5,
                EVENT6,
                EVENT7 /*=20000*/,
                EVENT8,

                EVENT9,
                EVENT10 /*= 30000*/,
                EVENT11,
                EVENT12,
                EVENT13 /*= 40000*/,
                EVENT14,
                EVENT15,
                EVENT16,
}OpCode;

const int event_array[16] = {EVENT1,EVENT2,EVENT3,EVENT4,
                EVENT5,EVENT6,EVENT7,EVENT8,
                EVENT9,EVENT10,EVENT11,EVENT12,
                EVENT13,EVENT14,EVENT15,EVENT16};
int do_event1()
{
                return 1;
}
int do_event2()
{
                return 2;
}
int do_event3()
{
                return 3;
}
int do_event4()
{
                return 4;
}
int do_event5()
{
                return 5;
}
int do_event6()
{
                return 6;
}
int do_event7()
{
                return 7;
}
int do_event8()
{
                return 8;
}
int do_event9()
{
                return 9;
}
int do_event10()
{
                return 10;
}
int do_event11()
{
                return 11;
}
int do_event12()
{
                return 12;
}
int do_event13()
{
                return 13;
}
int do_event14()
{
                return 14;
}
int do_event15()
{
                return 15;
}
int do_event16()
{
                return 16;
}

int test_switch(int opcode)
{
                int  ret ;
                switch(opcode)
                {
                                case EVENT1:
                                                do_event1();
                                                break;
                                case EVENT2:
                                                do_event2();
                                                break;
                                case EVENT3:
                                                do_event3();
                                                break;
                                case EVENT4:
                                                do_event4();
                                                break;
                                case EVENT5:
                                                do_event5();
                                                break;
                                case EVENT6:
                                                do_event6();
                                                break;
                                case EVENT7:
                                                do_event7();
                                                break;
                                case EVENT8:
                                                do_event8();
                                                break;
                                case EVENT9:
                                                do_event9();
                                                break;
                                case EVENT10:
                                                do_event10();
                                                break;
                                case EVENT11:
                                                do_event11();
                                                break;
                                case EVENT12:
                                                do_event12();
                                                break;
                                case EVENT13:
                                                do_event13();
                                                break;
                                case EVENT14:
                                                do_event14();
                                                break;
                                case EVENT15:
                                                do_event15();
                                                break;
                                case EVENT16:
                                                do_event16();
                                                break;
                                default:
                                                break;
                }
                return 0;
}

#define TIMES 100000000
#define MILLION  1000000
int main()
{
                int i;
                int event;
                struct timeval begin;
                struct timeval end;
                unsigned long long timelapse = 0;

                gettimeofday(&begin,NULL);

                for(i = 0;i<TIMES;i++)
                {
                                event = event_array[rand()%16];
                                test_switch(event);
                }

                gettimeofday(&end,NULL);
                timelapse = MILLION*(end.tv_sec - begin.tv_sec) + (end.tv_usec - begin.tv_usec);

                printf("%d times of switch cost %llu us\n",TIMES,timelapse);
                return 0;
}

     对于连续的事件号和非连续的事件号，得到的结论是，连续事件号，处理的速度更快。

对于事件号连续的测试
100000000 times of switch cost 8713840 us
100000000 times of switch cost 8461767 us
100000000 times of switch cost 8446023 us
100000000 times of switch cost 8460732 us
100000000 times of switch cost 8450516 us
100000000 times of switch cost 8440418 us

对于事件号不连续的测试
100000000 times of switch cost 9129715 us
100000000 times of switch cost 9140201 us
100000000 times of switch cost 9145429 us
100000000 times of switch cost 9209051 us
100000000 times of switch cost 9125981 us
100000000 times of switch cost 9142719 us

 

连续事件号的gprof统计
Flat profile:

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total
 time   seconds   seconds    calls  ns/call  ns/call  name
 31.52      1.10     1.10 100000000    11.00    11.00  test_switch
------------------------------------------------------------------------------------------不连续事件号的gprof统计
Flat profile:

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total
 time   seconds   seconds    calls  ns/call  ns/call  name
 52.44      1.83     1.83 100000000    18.30    24.40  test_switch

   

     我纠结与事情的原因，后来查看了反编译出来的汇编代码，就清楚了。

     对于连续事件号，switch语句的跳转，是通过跳转表实现的。一个数组存放着所有事件对应的跳转地址。举例子来说，如果第一个事件号是1000，当前事件号是1005，偏移量为5，去查找跳转表的偏移量为5的元素（即跳转表数组的第六个元素），作为跳转地址。看下面汇编代码就更清晰了。

    下面的0x3e8 = 1000，就是第一个事件号。sub $0x3e8,%eax ，将当前事件号减去第一个事件号，就是偏移量。因为偏移量最大为15即0xf，所以首先和0xf进行比较，如果大于oxf，表示为default事件，直接去执行default的代码。

     对于连续事件号来讲，default这个选项执行的速度最快，因为首先就要判断是否是default事件，不是default，才去跳转执行其他事件。《C++ Footprint and Performance Optimization》这本书提到了所有的switch分支中，default最快。

     

080484f4 :

80484f4: 55                   push %ebp

80484f5: 89 e5                mov %esp,%ebp

80484f7: 83 ec 10             sub $0x10,%esp

80484fa: 8b 45 08             mov 0x8(%ebp),%eax

80484fd: 2d e8 03 00 00       sub $0x3e8,%eax    

8048502: 83 f8 0f             cmp $0xf,%eax

8048505: 77 77                ja 804857e

8048507: 8b 04 85 a0 87 04 08 mov 0x80487a0(,%eax,4),%eax

804850e: ff e0                jmp *%eax

8048510: e8 3f ff ff ff       call 8048454

8048515: eb 67                jmp 804857e

8048517: e8 42 ff ff ff       call 804845e

804851c: eb 60                jmp 804857e

804851e: e8 45 ff ff ff       call 8048468

8048523: eb 59                jmp 804857e

8048525: e8 48 ff ff ff       call 8048472

804852a: eb 52                jmp 804857e

804852c: e8 4b ff ff ff       call 804847c

8048531: eb 4b                jmp 804857e

8048533: e8 4e ff ff ff       call 8048486

... ...........

...............

8048579: e8 6c ff ff ff       call 80484ea

804857e: b8 00 00 00 00       mov $0x0,%eax

8048583: c9                   leave

8048584: c3                   ret

     接下来汇编是mov 0x80487a0(,%eax,4),%eax  ，由于我的电脑是32位的，指针这种类型的长度为4字节，所以，括号里面是4，%eax是偏移量。比如我们的事件号就是1005，那么偏移量为5。 OK，我们将

0x80487a0 +5*4 = 0x80487b4 存入eax。

    这里有个magic number，0x80487a0，这个地址是干啥的东东呢。这个地址就是我们前面提到的跳转表的地址。就是跳转地址数组的基地址。请看下面.rodata段的数据。加粗的部分是那个我们寻找的magic number。 这个数组是指针数组，所以每个元素为long 类型，4个字节。  我们可以看到数组第一个元素是10850408，由于我的电脑是little-endian，所以这个地址实际是，0x08048510。 这就是EVENT1，或者说第一个事件应该跳转去的的地方。 这条汇编语句可以验证：

    8048510: e8 3f ff ff ff       call 8048454

    

    OK 如果是1005事件号，偏移量为5，计算出来的地址为0x80487b4，我们看下这个地址存放的是0x33850408，翻译过来就是0x08048533,这个地址就是事件1005 (EVENT6)应该跳转到的地址，我们看下汇编代码，果然

    8048533: e8 4e ff ff ff       call 8048486

Contents of section .rodata:
8048740 03000000 01000200 00000000 00000000  ................
8048750 00000000 00000000 00000000 00000000  ................
8048760 e8030000 e9030000 ea030000 eb030000  ................
8048770 ec030000 ed030000 ee030000 ef030000  ................
8048780 f0030000 f1030000 f2030000 f3030000  ................
8048790 f4030000 f5030000 f6030000 f7030000  ................
80487a0 10850408 17850408 1e850408 25850408  ............%...
80487b0 2c850408 33850408 3a850408 41850408  ,...3...:...A...
80487c0 48850408 4f850408 56850408 5d850408  H...O...V...]...
80487d0 64850408 6b850408 72850408 79850408  d...k...r...y...
80487e0 25642074 696d6573 206f6620 73776974  %d times of swit
80487f0 63682063 6f737420 256c6c75 2075730a  ch cost %llu us.
8048800 00

     OK，总算讲清楚了连续事件号的switch 语句的跳转。接下来是 连续事件号的跳转。，算了，为了不变成滚轮杀手，我还是分成两篇文章讲吧。