« プレイステーション3は、発売されるか? | トップページ | 脆弱性…て? »

2006年2月23日 (木)

「switch&case」の最適化は?

この前のバグは、
「switch&case」の最適化の結果だが…

実際は、どうチェックしているか
気になったので調べてみた…。

サンプルは、以下の通り。

----------------------------------------
int count;
void test1(int index)
{
    switch(index)
    {
    case 0:count=0;break;
    case 1:count=1;break;
    case 2:count=2;break;
    case 3:count=3;break;
    }
}
void test2(int index)
{
    switch(index)
    {
    case -1:count=-1;break;
    case 0:count=0;break;
    case 1:count=1;break;
    case 2:count=2;break;
    }
}
void test3(int index)
{
    switch(index)
    {
    case 1:count=1;break;
    case 2:count=2;break;
    case 3:count=3;break;
    case 4:count=4;break;
    }
}
void test4(int index)
{
    switch(index)
    {
    case 0:count=0;break;
    case 10:count=10;break;
    case 100:count=100;break;
    case 1000:count=1000;break;
    }
}
void main(void)
{
    test1(-1);
    test2(1);
    test3(2);
    test4(10);
}
----------------------------------------

実際に実行される状態。

----------------------------------------
1:    int count;
2:    void test1(int index)
3:    {
00401000   mov         eax,dword ptr [esp+4]
00401004   cmp         eax,3
00401007   ja          $L98+0Ah (0040103b)
00401009   jmp         dword ptr [eax*4+40103Ch]
4:        switch(index)
5:        {
6:        case 0:count=0;break;
00401010   mov         dword ptr [_count (00406428)],0
0040101A   ret
7:        case 1:count=1;break;
0040101B   mov         dword ptr [_count (00406428)],1
00401025   ret
8:        case 2:count=2;break;
00401026   mov         dword ptr [_count (00406428)],2
00401030   ret
9:        case 3:count=3;break;
00401031   mov         dword ptr [_count (00406428)],3
10:       }
11:   }
0040103B   ret
--------------------
12:   void test2(int index)
13:   {
00401050   mov         eax,dword ptr [esp+4]
00401054   inc         eax
00401055   cmp         eax,3
00401058   ja          $L110+0Ah (0040108c)
0040105A   jmp         dword ptr [eax*4+401090h]
14:       switch(index)
15:       {
16:       case -1:count=-1;break;
00401061   mov         dword ptr [_count (00406428)],0FFFFFFFFh
0040106B   ret
17:       case 0:count=0;break;
0040106C   mov         dword ptr [_count (00406428)],0
00401076   ret
18:       case 1:count=1;break;
00401077   mov         dword ptr [_count (00406428)],1
00401081   ret
19:       case 2:count=2;break;
00401082   mov         dword ptr [_count (00406428)],2
20:       }
21:   }
0040108C   ret
--------------------
22:   void test3(int index)
23:   {
004010A0   mov         eax,dword ptr [esp+4]
004010A4   dec         eax
004010A5   cmp         eax,3
004010A8   ja          $L122+0Ah (004010dc)
004010AA   jmp         dword ptr [eax*4+4010E0h]
24:       switch(index)
25:       {
26:       case 1:count=1;break;
004010B1   mov         dword ptr [_count (00406428)],1
004010BB   ret
27:       case 2:count=2;break;
004010BC   mov         dword ptr [_count (00406428)],2
004010C6   ret
28:       case 3:count=3;break;
004010C7   mov         dword ptr [_count (00406428)],3
004010D1   ret
29:       case 4:count=4;break;
004010D2   mov         dword ptr [_count (00406428)],4
30:       }
31:   }
004010DC   ret
--------------------
32:   void test4(int index)
33:   {
004010F0   mov         eax,dword ptr [esp+4]
004010F4   cmp         eax,64h
004010F7   jg          test4+30h (00401120)
004010F9   je          test4+25h (00401115)
004010FB   test        eax,eax
004010FD   je          test4+1Ah (0040110a)
004010FF   cmp         eax,0Ah
00401102   jne         test4+3Ch (0040112c)
37:       case 10:count=10;break;
00401104   mov         [_count (00406428)],eax
00401109   ret
36:       case 0:count=0;break;
0040110A   mov         dword ptr [_count (00406428)],0
00401114   ret
38:       case 100:count=100;break;
00401115   mov         dword ptr [_count (00406428)],64h
0040111F   ret
00401120   cmp         eax,3E8h
00401125   jne         test4+3Ch (0040112c)
39:       case 1000:count=1000;break;
00401127   mov         [_count (00406428)],eax
40:       }
41:   }
0040112C   ret
--------------------
42:   void main(void)
43:   {
00401130   push        0FFh
00401132   call        test1 (00401000)
44:       test1(-1);
45:       test2(1);
00401137   push        1
00401139   call        test2 (00401050)
46:       test3(2);
0040113E   push        2
00401140   call        test3 (004010a0)
47:       test4(10);
00401145   push        0Ah
00401147   call        test4 (004010f0)
0040114C   add         esp,10h
48:   }
0040114F   ret
----------------------------------------

「test1」では、0~3なので
最初に0~3以外は、排除して
テーブルジャンプしている…。

「test2」では、-1~2なので
最初に+1して0~3以外は、排除して
テーブルジャンプしている…。

「test3」では、1~4なので
最初に-1して0~3以外は、排除して
テーブルジャンプしている…。

「test4」では、テーブルジャンプできないので
個別にチェックしているのだが…
最初に100分で岐分岐して…
どの項目にも最も高速に
到達で切るように細工してある…。

実感…
良く出来ている…。

最適化…
恐るべし…。

|

« プレイステーション3は、発売されるか? | トップページ | 脆弱性…て? »

コメント

コメントを書く



(ウェブ上には掲載しません)




トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/108365/8795835

この記事へのトラックバック一覧です: 「switch&case」の最適化は?:

« プレイステーション3は、発売されるか? | トップページ | 脆弱性…て? »