VC驿站

 找回密码
 加入驿站

QQ登录

只需一步,快速开始

搜索
查看: 2279|回复: 4

[原创] Switch 对 if 的优化

[复制链接]
001
61_avatar_middle
最佳答案
0 
在线会员 发表于 2016-4-10 15:14:01 | 显示全部楼层 |阅读模式
    注册这个账号也有1年多了,平时逛论坛的时间不多,也发了几篇帖子,本来想将学到的C++的内容整理出来,然而后面学习比较紧张,自己也懒惰了,如今再发已经差不多隔了一年多了,而自己也刚进入职场成为了一个菜鸟程序员,而且自己对C/C++这块的理解也更深了一层,希望以后自己能够坚持发一系列的帖子将C/C++这块基础东西,通过汇编的方式来再次复习一遍。最后希望自己能坚持Switch 对 if 的优化
    言归正传,下面来说明switch语句的汇编实现。
    首先对于简单的switch来说,编译器将它翻译为if...else if...else的方式,简单的是指case语句不超过三个。
    对于相对复杂的主要有地址表、索引表、以及判断数的方式,来减少判断次数,下面对它们进行一一说明:
    1)地址表:
        首先请看下面的代码和它对应的汇编代码:
  1. switch(argc)
  2.         {
  3.           case 1:
  4.                     printf("argc = 1\n");
  5.                     break;
  6.   case 2:
  7.                     printf("argc = 2\n");
  8.                     break;
  9.            case 3:
  10.                     printf("argc = 3\n");
  11.                     break;
  12.            case 4:
  13.                     printf("argc = 4\n");
  14.                     break;
  15.            case 5:
  16.                     printf("argc = 5\n");
  17.                     break;
  18.            case 6:
  19.                     printf("argc = 6\n");
  20.                     break;
  21.            default:
  22.                     printf("else\n");
  23.                     break;
  24.         }
复制代码


  1. 0040B798   mov         eax,dword ptr [ebp+8] ;eax = argc
  2. 0040B79B   mov         dword ptr [ebp-4],eax
  3. 0040B79E   mov         ecx,dword ptr [ebp-4]  ;ecx = eax
  4. 0040B7A1   sub         ecx,1
  5. 0040B7A4   mov         dword ptr [ebp-4],ecx
  6. 0040B7A7   cmp         dword ptr [ebp-4],5
  7. 0040B7AB   ja          $L544+0Fh (0040b811) ;argc 》 5则跳转到default处,至于为什么是5而不是6,看后面的说明
  8. 0040B7AD   mov         edx,dword ptr [ebp-4] ;edx = argc
  9. 0040B7B0   jmp         dword ptr [edx*4+40B831h]
  10. 11:       case 1:
  11. 12:           printf("argc = 1\n");
  12. 0040B7B7   push        offset string "argc = 1\n" (00420fc0)
  13. 0040B7BC   call        printf (00401090)
  14. 0040B7C1   add         esp,4
  15. 13:           break;
  16. 0040B7C4   jmp         $L544+1Ch (0040b81e)
  17. 14:       case 2:
  18. 15:           printf("argc = 2\n");
  19. 0040B7C6   push        offset string "argc = 2\n" (00420fb4)
  20. 0040B7CB   call        printf (00401090)
  21. 0040B7D0   add         esp,4
  22. 16:           break;
  23. 0040B7D3   jmp         $L544+1Ch (0040b81e)
  24. 17:       case 3:
  25. 18:           printf("argc = 3\n");
  26. 0040B7D5   push        offset string "argc = 3\n" (00420fa8)
  27. 0040B7DA   call        printf (00401090)
  28. 0040B7DF   add         esp,4
  29. 19:           break;
  30. 0040B7E2   jmp         $L544+1Ch (0040b81e)
  31. 20:       case 4:
  32. 21:           printf("argc = 4\n");
  33. 0040B7E4   push        offset string "argc = 4\n" (00420f9c)
  34. 0040B7E9   call        printf (00401090)
  35. 0040B7EE   add         esp,4
  36. 22:           break;
  37. 0040B7F1   jmp         $L544+1Ch (0040b81e)
  38. 23:       case 5:
  39. 24:           printf("argc = 5\n");
  40. 0040B7F3   push        offset string "argc < 0\n" (0042003c)
  41. 0040B7F8   call        printf (00401090)
  42. 0040B7FD   add         esp,4
  43. 25:           break;
  44. 0040B800   jmp         $L544+1Ch (0040b81e)
  45. 26:       case 6:
  46. 27:           printf("argc = 6\n");
  47. 0040B802   push        offset string "argc <= 0\n" (0042002c)
  48. 0040B807   call        printf (00401090)
  49. 0040B80C   add         esp,4
  50. 28:           break;
  51. 0040B80F   jmp         $L544+1Ch (0040b81e)
  52. 29:       default:
  53. 30:           printf("else\n");
  54. 0040B811   push        offset string "argc = %d\n" (0042001c)
  55. 0040B816   call        printf (00401090)
  56. 0040B81B   add         esp,4
  57. 31:           break;
  58. 32:       }
  59. 33:
  60. 34:       return 0;
  61. 0040B81E   xor         eax,eax
复制代码


上面的代码中并没有看到像if那样,对每一个条件都进行比较,其中有一句话 “jmp dword ptr [edx*4+40B831h]” 这句话从表面上看应该是取数组中的元素,再根据元素的值来进行跳转,而这个元素在数组中的位置与eax也就是与argc的值有关,下面我们跟踪到数组中查看数组的元素值:

0040B831   B7 B7 40 00         
0040B835   C6 B7 40 00
0040B839   D5 B7 40 00
0040B83D   E4 B7 40 00
0040B841   F3 B7 40 00
0040B845   02 B8 40 00

通过对比可以发现0x0040b7b7是case 1处的地址,后面的分别是case 2、case 3、case 4、case 5、case 6处的地址,每个case中的break语句都翻译为了同一句话“jmp $L544+1Ch (0040b81e)”,所以从这可以看出,在switch中,编译器多增加了一个数组用于存储每个case对应的地址,根据switch中传入的整数在数组中查到到对应的地址,直接通过这个地址跳转到对应的位置,减少了比较操作,提升了效率。编译器在处理switch时会首先校验不满足所有case的情况,当这种情况发生时代码调转到default或者switch语句块之外。然后将传入的整数值减一(数组元素是从0开始计数)。最后根据参数值找到应该跳转的位置。
        这种方式可以用下面的图表示:
Switch 对 if 的优化

如果每两个case之间的差距大于6,或者case语句数小于4则不会采取这种做法,如果再采用这种方式,那么会造成较大的资源消耗。这个时候编译器会采用索引表的方式来进行地址的跳转。
下面有这样一个例子:
  1. switch(argc)
  2.     {
  3.     case 1:
  4.         printf("argc = 1\n");
  5.         break;
  6.     case 2:
  7.         printf("argc = 2\n");
  8.         break;
  9.     case 5:
  10.         printf("argc = 5\n");
  11.         break;
  12.     case 6:
  13.         printf("argc = 6\n");
  14.         break;
  15.     case 255:
  16.         printf("argc = 255\n");
  17.     default:
  18.         printf("else\n");
  19.         break;
  20.     }
复制代码

  1. 0040B798   mov         eax,dword ptr [ebp+8]
  2. 0040B79B   mov         dword ptr [ebp-4],eax
  3. 0040B79E   mov         ecx,dword ptr [ebp-4] ;到此eax = ecx = argc
  4. 0040B7A1   sub         ecx,1
  5. 0040B7A4   mov         dword ptr [ebp-4],ecx
  6. 0040B7A7   cmp         dword ptr [ebp-4],0FEh
  7. 0040B7AE   ja          $L542+0Dh (0040b80b) ;当argc  > 255则跳转到default处
  8. 0040B7B0   mov         eax,dword ptr [ebp-4]
  9. 0040B7B3   xor         edx,edx
  10. 0040B7B5   mov         dl,byte ptr  (0040b843)[eax]
  11. 0040B7BB   jmp         dword ptr [edx*4+40B82Bh]
  12. 11:       case 1:
  13. 12:           printf("argc = 1\n");
  14. 0040B7C2   push        offset string "argc = 1\n" (00420fb4)
  15. 0040B7C7   call        printf (00401090)
  16. 0040B7CC   add         esp,4
  17. 13:           break;
  18. 0040B7CF   jmp         $L542+1Ah (0040b818)
  19. 14:       case 2:
  20. 15:           printf("argc = 2\n");
  21. 0040B7D1   push        offset string "argc = 3\n" (00420fa8)
  22. 0040B7D6   call        printf (00401090)
  23. 0040B7DB   add         esp,4
  24. 16:           break;
  25. 0040B7DE   jmp         $L542+1Ah (0040b818)
  26. 17:       case 5:
  27. 18:           printf("argc = 5\n");
  28. 0040B7E0   push        offset string "argc = 5\n" (00420f9c)
  29. 0040B7E5   call        printf (00401090)
  30. 0040B7EA   add         esp,4
  31. 19:           break;
  32. 0040B7ED   jmp         $L542+1Ah (0040b818)
  33. 20:       case 6:
  34. 21:           printf("argc = 6\n");
  35. 0040B7EF   push        offset string "argc < 0\n" (0042003c)
  36. 0040B7F4   call        printf (00401090)
  37. 0040B7F9   add         esp,4
  38. 22:           break;
  39. 0040B7FC   jmp         $L542+1Ah (0040b818)
  40. 23:       case 255:
  41. 24:           printf("argc = 255\n");
  42. 0040B7FE   push        offset string "argc <= 0\n" (0042002c)
  43. 0040B803   call        printf (00401090)
  44. 0040B808   add         esp,4
  45. 25:       default:
  46. 26:           printf("else\n");
  47. 0040B80B   push        offset string "argc = %d\n" (0042001c)
  48. 0040B810   call        printf (00401090)
  49. 0040B815   add         esp,4
  50. 27:           break;
  51. 28:       }
  52. 29:
  53. 30:       return 0;
  54. 0040B818   xor         eax,eax
复制代码


这段代码与上述的线性表相比较区别并不大,只是多了一句 “mov dl,byte ptr (0040b843)[eax]”  这似乎又是一个数组,通过查看内存可以知道这个数组的值分别为:00 01 05 05 02 03 05 05 ... 04,下一句根据这些值在另外一个数组中查找数据,我们列出另外一个数组的值:

C2 B7 40 00   D1 B7 40 00  E0 B7 40 00  EF B7 40 00  FE B7 40 00  0B B8 40 00

通过对比我们发现,这些值分别是每个case与default入口处的地址,编译器先查找到每个值在数组中对应的元素位置,然后根据这个位置值再在地址表中从、找到地址进行跳转,这个过程可以用下面的图来表示:
Switch 对 if 的优化
这样通过一个每个元素占一个字节的表,来表示对应的case在地址表中所对应的位置,从而跳转到对应的地址,这样通过对每个case增加一个字节的内存消耗来达到,减少地址表对应的内存消耗。

  在上述的汇编代码中,是利用dl寄存器来存储对应case在地址表中项,这样就会产生一个问题,当case 值大于 255,也就是超出了一个字节的,超出了dl寄存器的表示范围时,又该如何来进行跳转这个时候编译器会采用判定树的方式来进行判定,在根节点保存的是所有case值的中位数, 左子树都是大于这个大于这个值的数,右字数是小于这个值的数,通过每次的比较来得到正确的地址。比如下面的这个判定树:
Switch 对 if 的优化

首先与10进行比较,根据与10 的大小关系进入左子树或者右子树,再看看左右子树的分支是否不大于3,若不大于3则直接转化为对应的if...else if... else结构,大于3则检测分支是否满足上述的优化条件,满足则进行对应的地址表或者索引表的优化,否则会再次对子树进行优化,以便减少比较次数。
        至此基本上把编译器采用的方式,基本上列了出来,判定书那块,我没有详细的说明,当初自己在看这块内容时,并没有弄太懂,只是知道一个大概的思路,所以在这就不误导大家了。

评分

参与人数 2威望 +2 驿站币 +5 热心值 +5 收起 理由
77_avatar_small Health + 2 + 2 感谢分享!
51_avatar_small Syc + 2 + 3 + 3 赞一个!

查看全部评分





上一篇:一个C/C++书籍的网盘
下一篇:C语言循环的实现
51_avatar_middle
最佳答案
83 
online_admins 发表于 2016-4-10 23:46:05 | 显示全部楼层
分析过程相当不错,结合汇编,大家一起学习学习!
77_avatar_middle
最佳答案
31 
online_vip 发表于 2016-4-10 23:55:29 | 显示全部楼层
NB的东东,路过学习,支持楼主
80_avatar_middle
最佳答案
0 
在线会员 发表于 2016-6-3 10:18:52 | 显示全部楼层
好~~~~不错
73_avatar_middle
最佳答案
0 
在线会员 发表于 2016-6-24 17:33:13 | 显示全部楼层
case的三种方式,直跳,对表,树形
您需要登录后才可以回帖 登录 | 加入驿站 qq_login

本版积分规则

×【发帖 友情提示】
1、请回复有意义的内容,请勿恶意灌水;
2、纯数字、字母、表情等无意义的内容系统将自动删除;
3、若正常回复后帖子被自动删除,为系统误删的情况,请重新回复其他正常内容或等待管理员审核通过后会自动发布;
4、感谢您对VC驿站一如既往的支持,谢谢合作!

关闭

站长提醒上一条 /2 下一条

QQ|小黑屋|手机版|VC驿站 ( 辽ICP备09019393号 )|网站地图wx_jqr

GMT+8, 2021-1-28 19:45

Powered by CcTry.CoM

© 2009-2020 cctry.com

快速回复 返回顶部 返回列表