Chinaunix首页 | 论坛 | 博客
  • 博客访问: 3677898
  • 博文数量: 146
  • 博客积分: 3918
  • 博客等级: 少校
  • 技术积分: 8582
  • 用 户 组: 普通用户
  • 注册时间: 2010-10-17 13:52
个人简介

个人微薄: weibo.com/manuscola

文章分类

全部博文(146)

文章存档

2016年(3)

2015年(2)

2014年(5)

2013年(42)

2012年(31)

2011年(58)

2010年(5)

分类: C/C++

2011-08-27 15:42:12

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

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

  2.         EVENT1 = 1000,
  3.         EVENT2,
  4.         EVENT3,
  5.         EVENT4 /*= 2000*/,
  6.         EVENT5,
  7.         EVENT6,
  8.         EVENT7 /*=20000*/,
  9.         EVENT8,

  10.         EVENT9,
  11.         EVENT10 /*= 30000*/,
  12.         EVENT11,
  13.         EVENT12,
  14.         EVENT13 /*= 40000*/,
  15.         EVENT14,
  16.         EVENT15,
  17.         EVENT16,
  18. }OpCode;
    我的测试程序如下:简单的说就是随机选择16个事件号中的一个,来测试switch语句。通过TIMES =1亿次进入switch 语句,观察性能
  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. #include<time.h>



  4. typedef enum OPCODE{

  5.                 EVENT1 = 1000,
  6.                 EVENT2,
  7.                 EVENT3,
  8.                 EVENT4 /*= 2000*/,
  9.                 EVENT5,
  10.                 EVENT6,
  11.                 EVENT7 /*=20000*/,
  12.                 EVENT8,

  13.                 EVENT9,
  14.                 EVENT10 /*= 30000*/,
  15.                 EVENT11,
  16.                 EVENT12,
  17.                 EVENT13 /*= 40000*/,
  18.                 EVENT14,
  19.                 EVENT15,
  20.                 EVENT16,
  21. }OpCode;

  22. const int event_array[16] = {EVENT1,EVENT2,EVENT3,EVENT4,
  23.                 EVENT5,EVENT6,EVENT7,EVENT8,
  24.                 EVENT9,EVENT10,EVENT11,EVENT12,
  25.                 EVENT13,EVENT14,EVENT15,EVENT16};
  26. int do_event1()
  27. {
  28.                 return 1;
  29. }
  30. int do_event2()
  31. {
  32.                 return 2;
  33. }
  34. int do_event3()
  35. {
  36.                 return 3;
  37. }
  38. int do_event4()
  39. {
  40.                 return 4;
  41. }
  42. int do_event5()
  43. {
  44.                 return 5;
  45. }
  46. int do_event6()
  47. {
  48.                 return 6;
  49. }
  50. int do_event7()
  51. {
  52.                 return 7;
  53. }
  54. int do_event8()
  55. {
  56.                 return 8;
  57. }
  58. int do_event9()
  59. {
  60.                 return 9;
  61. }
  62. int do_event10()
  63. {
  64.                 return 10;
  65. }
  66. int do_event11()
  67. {
  68.                 return 11;
  69. }
  70. int do_event12()
  71. {
  72.                 return 12;
  73. }
  74. int do_event13()
  75. {
  76.                 return 13;
  77. }
  78. int do_event14()
  79. {
  80.                 return 14;
  81. }
  82. int do_event15()
  83. {
  84.                 return 15;
  85. }
  86. int do_event16()
  87. {
  88.                 return 16;
  89. }

  90. int test_switch(int opcode)
  91. {
  92.                 int ret ;
  93.                 switch(opcode)
  94.                 {
  95.                                 case EVENT1:
  96.                                                 do_event1();
  97.                                                 break;
  98.                                 case EVENT2:
  99.                                                 do_event2();
  100.                                                 break;
  101.                                 case EVENT3:
  102.                                                 do_event3();
  103.                                                 break;
  104.                                 case EVENT4:
  105.                                                 do_event4();
  106.                                                 break;
  107.                                 case EVENT5:
  108.                                                 do_event5();
  109.                                                 break;
  110.                                 case EVENT6:
  111.                                                 do_event6();
  112.                                                 break;
  113.                                 case EVENT7:
  114.                                                 do_event7();
  115.                                                 break;
  116.                                 case EVENT8:
  117.                                                 do_event8();
  118.                                                 break;
  119.                                 case EVENT9:
  120.                                                 do_event9();
  121.                                                 break;
  122.                                 case EVENT10:
  123.                                                 do_event10();
  124.                                                 break;
  125.                                 case EVENT11:
  126.                                                 do_event11();
  127.                                                 break;
  128.                                 case EVENT12:
  129.                                                 do_event12();
  130.                                                 break;
  131.                                 case EVENT13:
  132.                                                 do_event13();
  133.                                                 break;
  134.                                 case EVENT14:
  135.                                                 do_event14();
  136.                                                 break;
  137.                                 case EVENT15:
  138.                                                 do_event15();
  139.                                                 break;
  140.                                 case EVENT16:
  141.                                                 do_event16();
  142.                                                 break;
  143.                                 default:
  144.                                                 break;
  145.                 }
  146.                 return 0;
  147. }

  148. #define TIMES 100000000
  149. #define MILLION 1000000
  150. int main()
  151. {
  152.                 int i;
  153.                 int event;
  154.                 struct timeval begin;
  155.                 struct timeval end;
  156.                 unsigned long long timelapse = 0;

  157.                 gettimeofday(&begin,NULL);

  158.                 for(i = 0;i<TIMES;i++)
  159.                 {
  160.                                 event = event_array[rand()%16];
  161.                                 test_switch(event);
  162.                 }

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

  165.                 printf("%d times of switch cost %llu us\n",TIMES,timelapse);
  166.                 return 0;
  167. }
     对于连续的事件号和非连续的事件号,得到的结论是,连续事件号,处理的速度更快。

  1. 对于事件号连续的测试
  2. 100000000 times of switch cost 8713840 us
  3. 100000000 times of switch cost 8461767 us
  4. 100000000 times of switch cost 8446023 us
  5. 100000000 times of switch cost 8460732 us
  6. 100000000 times of switch cost 8450516 us
  7. 100000000 times of switch cost 8440418 us
  8. 对于事件号不连续的测试
  9. 100000000 times of switch cost 9129715 us
  10. 100000000 times of switch cost 9140201 us
  11. 100000000 times of switch cost 9145429 us
  12. 100000000 times of switch cost 9209051 us
  13. 100000000 times of switch cost 9125981 us
  14. 100000000 times of switch cost 9142719 us
 
    1. 连续事件号的gprof统计
    2. Flat profile:

    3. Each sample counts as 0.01 seconds.
    4.   %   cumulative   self              self     total           
    5.  time   seconds   seconds    calls  ns/call  ns/call  name    
    6.  31.52      1.10     1.10 100000000    11.00    11.00  test_switch

    ------------------------------------------------------------------------------------------
    不连续事件号的gprof统计
    1. Flat profile:

    2. Each sample counts as 0.01 seconds.
    3.   %   cumulative   self              self     total           
    4.  time   seconds   seconds    calls  ns/call  ns/call  name    
    5.  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
  1. Contents of section .rodata:
  2. 8048740 03000000 01000200 00000000 00000000 ................
  3. 8048750 00000000 00000000 00000000 00000000 ................
  4. 8048760 e8030000 e9030000 ea030000 eb030000 ................
  5. 8048770 ec030000 ed030000 ee030000 ef030000 ................
  6. 8048780 f0030000 f1030000 f2030000 f3030000 ................
  7. 8048790 f4030000 f5030000 f6030000 f7030000 ................
  8. 80487a0 10850408 17850408 1e850408 25850408 ............%...
  9. 80487b0 2c850408 33850408 3a850408 41850408 ,...3...:...A...
  10. 80487c0 48850408 4f850408 56850408 5d850408 H...O...V...]...
  11. 80487d0 64850408 6b850408 72850408 79850408 d...k...r...y...
  12. 80487e0 25642074 696d6573 206f6620 73776974 %d times of swit
  13. 80487f0 63682063 6f737420 256c6c75 2075730a ch cost %llu us.
  14. 8048800 00
     OK,总算讲清楚了连续事件号的switch 语句的跳转。接下来是 连续事件号的跳转。,算了,为了不变成滚轮杀手,我还是分成两篇文章讲吧。


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

Heartwork2011-12-05 21:30:33

这两天正在看Computer Systems,正好看到switch语句这部分,没想到又和老兄撞车了,哈哈。

根据书中的说法,编译后的switch语句也不是铁定就会使用跳转表的,必须有4个以上的分支(连续情况下)。我用gcc反编译代码发现是6个以上(包括default)。

GFree_Wind2011-10-11 12:11:40

不错。没有想到switch和事件号的连续不连续有关系呢。。。