VS2008下反汇编观察switch语句-at-2010

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

Author:xichen

Data:2011-03-27

本人原创,2011年于电子科技大学

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

引言:Switch ,if else语句是在程序设计中使用较为频繁的两种语句,它们实现的功能是相似,都是通过对特定值的判断后执行相应的操作。但是switch和if else执行方式肯定是不同的,这点我们直观地在语句的句式上就可以推断得出的,但是究竟在底层它们是以一种怎样的形式执行的呢? 这是值得我们探究的一个话题,因为只有了解其底层过程,我们才能够更好地认识,选择使用switch,else if语句。

接下来我将通过在VS2008中进行反汇编观察,分析switch语句的执行机制。在描述之前,为了节省篇幅,也为了描述的方便,做出一个约定:

switch(i)

{

   case 1:....break;

case 2:....break;

   case 3:....break;

   case 4:....break;

   case 5:....break;

   case 6:....break;

   default:

          ...break;

}

我们约定表示形式为:case序列:1 2 3 4 5 6 x;其中x用来代表default情况;这样描述case语句时较为清爽;

观察: 首先是我们最常见的一种switch语句:case 序列:1 2 3 x;

其汇编代码为:

而相应的if else语句汇编代码为:

当我们对比两段汇编代码的时候,实际上并没有本质的区别,if else语句的做法是我们能够想象的到的,而传说中的switch居然也是这么处理的。。。。。

我们知道使用switch的情况一般是case较多时,那么为什么是case较多时呢?case较多时回事什么样呢?

定义case序列:1 2 3 4 5 6 x;

反汇编代码为:

汇编代码读起来是很晦涩的,但是也是比较有味道的,我比较喜欢的读法是:

画出寄存器,画出堆栈,然后跟随代码自己修改寄存器的值。

比如执行到ja那句的时候,我的草稿纸上显示eax=i; ecx=i-1; [ebp-0c4h]=i-1;

梳理下上面的代码:[ebp-0c4h]就是一个特定的地址,作为eax和ecx之间的中转站,而sub和cmp两条指令保证了i落在1-6区间中,否则直接jmp到x情况。接下来jmp到一个地址:0aa14b8h+(i-1)*4;

我们猜想:这里应该是到一个地方去了,干什么呢?肯定是找怎么跳到合适的位置去了,很容易猜出,实际上地址是4个字节一个格格,0aa14b8h是一个基地址的东西,而i-1决定从第几个格格取地址。

好,接下来我们看看0aa14b8h这个地址后面装的是什么:

9c 14 aa 00 9e 14 aa 00 a0 14 aa 00 a2 14 aa 00 a4 14 aa 00 a6 14 aa 00

(嘿,小端机呢)

读出来的是00 aa 14 9c| 00 aa 14 9e|00 aa 14 a0|00 aa 14 a2|…

对应的地址恰好是:case 1,2,3,4..的地址值,验证了我们的想法;

呵呵,到这里神清气爽,到此结束了!

?是不是我们的话题到这个就结束了呢?不,远远没有。

实际上以上我们给出的是我们最常用的方式,就是case的值连续到吐血的那种,可我们在使用switch的时候不可能总是这种方式,如果地址值不连续呢?比如这个极端:

Case序列:1 2 3 4 5 800 x;

汇编代码:

对比汇编代码,我们可以看出它没有采用之前的方式,而完全就是类比if else的很简单的cmp,je,这。。。我们刚才明明看到了一个表,一个可以查询地址的表啊??

写到这里实际上产生了两个问题:

1.为什么编译器要这么做?

2.什么时候这么做呢?

我们不先回答问题1,现在只是想从现象到现象的去看这个问题;

出现这种情况的原因是我修改了max值为800,也就是说如果是6就有表出现而一个很大的值就没有表出现,那么什么时候也就是这个很大的值是多少的时候会有表出现呢?

如果限定case起始值是1(实际上不是1,也可以化归为1):不断的修改最大值,记录MAX-MIN值,最后在我的不断逼近下,得出MAX-MIN=255是临界值,现象是:当MAX是255的时候,出现了跳转表的做法,但是MAX是256的时候是else if的方式,猜想如果保持MAX=256,修改MIN=2的时候应该是什么样子的呢?那个跳转的表,还是直接判断?

实证下:结果是跳转表如约而至(篇幅原因不截图),哈哈,那么到这里是不是可以说或当表的差值(你懂的的差值)小于255的时候就会出现跳转表呢?不,显然这个太过于武断,因为我一直在忽视一个问题,那就是局部疏密程度显然不能够代表整体,也就是说case值的疏密程度,并不完全取决于MAX-MIN的值,下面给出另外一个例子:

Case序列: 100 110 120 130 140 150 x;

实际上它等同于:case序列:0 10 20 30 40 50 x;

汇编代码:

上面说的表有个类似于基地址的东西,这里居然出现了2个,跳转表好像有,但是好像又不是,这…..

赋予i=120,打个断点跟踪一个值进去观察,首先到地址0aa187ch:

00 06 06 06 06 06 06 06 06 06 01 06 06 06 06 06 06 06 06 06 02 06 06 06 06 06 06 06 06 06 03 06 06 06 06 06 06 06 06 06 04 06……

这是什么?? 我们观察到120进去之后eax的值变成了00000002,查阅指令知道movzx,..byte是取一个字节,也就是02,好的我们知道我们从这些串串中取出了02,然后呢;看下0aa1860h地址:

43 18 aa 00 45 18 aa 00 47 18 aa 00 49 18 aa 00 4b 18 aa 00 4d 18 aa 00 4f 18 aa 00

[eax*4]=8,数8个字节,取4字节,我们得到00aa1847h,查看下:果然case120的地址,这个过程很熟悉,就像我们在第一次见到跳转表时的样子。把这个过程画一个图:

这里可以很清晰的看出,其实这也是一种表的结构,不过是通过先查找序号,再获取地址。为了区别,我们称第一种为单层表,第二种为双层表。

事实上,遇到问题应该多问为什么(我所欠缺的啊)?

那么为什么使用着单层表好好的,又使用双层表了呢?

这是策略的转变,而你知道的:所有的策略,方法我们都可以用一个叫做“算法“的东西称呼之,而算法最基本的两个属性就是时间和空间;

分析: 两个为什么?

从时间角度分析: 从时间角度分析单跳表和双跳表是很easy的事情,从时间考虑很显然双跳表更麻烦,跳了两次才取到地址,如果完全从时间的角度去看,显然会跟我们实际看到的情况不一致,那么就只能从空间的角度分析了

为什么要使用跳转表?

在底层,机器级的执行过程中,CPU的操作有:取值,加(减,乘,除);

本例中需要用的是加法,取值;我们知道取值是1个机器周期,加法是4个机器周期。

比较switch 和else if,当使用跳转表时,switch大致的机器周期是:4个加法;(sub,cmp,jmp寻址的乘和加);也就是说无论有多少项,这个已经是最少的机器周期了,而对于else if而言是O(1),也就是有多少项就有多少次加法。两种情况的交汇点就是4(不够严谨),也就是说只有4以上的case情况switch才有可能更快。这也解释了为什么5个case时switch开始使用跳转表了,但是显然不是绝对的,如果完全是这样,那么case序列:1 2 3 4 5 800时,也应该使用跳转表啊,为什么又使用cmp,je的方式了呢?既然存在了就有它的理由,显然我们需要从空间角度去分析了。

从空间角度分析: 从空间角度分析:

如果case序列: MIN ……MID…..MAX x;共有n+1项;MID表示某一中间值;

其等价形式:case序列:0…..MID-MIN…MAX-MIN x;也是共有n+1项;

通过上面的观察,可以给出观察结果:

对于case语句:

n<4时,使用else if方式;

n>=4的时候,如果MAX-MIN<255,则使用跳转表,

否则MAX-MIN>=255 则直接使用else if方式。

跳转表有两种:在vs2008中,如果MIN—MAX中项值分布较为连续时,往往给出单层表。

          相反如果MIN—MAX项值跨度较大时,往往使用双层表。

使用单层表时,空间为: 4*(MAX-MIN+1) (单位byte)

使用双层表时,空间为:4*(n+1)+ (MAX-MIN+1) (单位byte)

那么对于case序列:1 2 3 4 5 600 x的情况;如果使用单层表,空间为2400byte,显然代价太大了;

对于序列:100 110 120 130 140 150 x;

单层表:451=204; 双层表:47+51=79,空间大大节省,这一定程度上解释了为什么使用双层表;

那么我们是不是可以做出一个判断,完全从空间上的判断:

选择使用单层表的条件:
4*(MAX-MIN+1)< 4*(n+1)+ (MAX-MIN+1)

è3* (MAX-MIN)<4n+1

相应地使用双层表的条件:3* (MAX-MIN)>4n+1

验证我们的想法:

实验结果如下: 最右边是序列,描述:表示在n和min值固定的情况下,MAX取的单层表变为双层表的临界值;

选择n=5,MIN=1; 1 2 3 5 11转

选择n=6,MIN=1; 1 2 3 5 9 13转

选择n=7,MIN=1; 1 2 3 5 9 11 14转

选择n=8,MIN=1; 1 2 3 5 9 11 13 15转

选择n=9,MIN=1; 1 2 3 5 9 11 13 14 17转

很显然如果单纯地从空间的角度考虑,以上的实验结果是不会出现的,而出现了,说明有些东西是我们没有领悟到的。

对于算法,归根结底是时间和空间的博弈,如何在中间选择一个最优的值,冥冥中我觉得会有一个公式,像3次曲线或者跟复杂的曲线一样,指导着编译器做出选择,至于究竟是怎样,站在编译器之外的我,抑或者我们需要更多的实证,当然如果可以,或许当面问MS的天才工程师们……

Chen Xi
Chen Xi
Software Engineer

Related