勝負「if vs switch」

前回switchをしたことですし、ここらで１つ速度テストをしてみましょう。テストするのは次のコード。

ソースコード

using System;

namespace Project1
{
    class Program
    {
        public static void Main()
        {
            Console.WriteLine( DateTime.Now.Ticks);
            int n;

            long timeA = DateTime.Now.Ticks;
            n=0;
            for(int i=0;i<1000000000;i++)
            {
                if(n==0)n=1;
                else if(n==1)n=2;
                else if(n==2)n=3;
                else if(n==3)n=4;
                else if(n==4)n=5;
                else if(n==5)n=6;
                else if(n==6)n=7;
                else if(n==7)n=8;
                else if(n==8)n=9;
                else if(n==9)n=0;
            }

            long timeB = DateTime.Now.Ticks;
            n=0;
            for(int i=0;i<1000000000;i++)
            {
                switch(n)
                {
                case 0: n=1;
                    break;
                case 1: n=2;
                    break;
                case 2: n=3;
                    break;
                case 3: n=4;
                    break;
                case 4: n=5;
                    break;
                case 5: n=6;
                    break;
                case 6: n=7;
                    break;
                case 7: n=8;
                    break;
                case 8: n=9;
                    break;
                case 9: n=0;
                    break;
                }
            }
            long timeC = DateTime.Now.Ticks;
            Console.WriteLine(timeB-timeA);
            Console.WriteLine(timeC-timeB);
        }
    }
}

ILコードは次の通り

//  Microsoft (R) .NET Framework IL Disassembler.  Version 1.1.4322.573
//  Copyright (C) Microsoft Corporation 1998-2002. All rights reserved.

.assembly extern mscorlib
{
  .publickeytoken = (B7 7A 5C 56 19 34 E0 89 )                         // .z\V.4..
  .ver 1:0:5000:0
}
.assembly 'time-r'
{
  .hash algorithm 0x00008004
  .ver 0:0:0:0
}
.module 'time-r.exe'
// MVID: {2782757D-4895-4E4A-B2AD-1D9D2BB5D879}
.imagebase 0x00400000
.subsystem 0x00000003
.file alignment 512
.corflags 0x00000001
// Image base: 0x00d90000
//
// ============== CLASS STRUCTURE DECLARATION ==================
//
.namespace Project1
{
  .class private auto ansi beforefieldinit Program
         extends [mscorlib]System.Object
  {
  } // end of class Program

} // end of namespace Project1


// =============================================================


// =============== GLOBAL FIELDS AND METHODS ===================


// =============================================================


// =============== CLASS MEMBERS DECLARATION ===================
//   note that class flags, 'extends' and 'implements' clauses
//          are provided here for information only

.namespace Project1
{
  .class private auto ansi beforefieldinit Program
         extends [mscorlib]System.Object
  {
    .method public hidebysig static void 
            Main() cil managed
    {
      .entrypoint
      // コード サイズ       293 (0x125)
      .maxstack  2
      .locals init (int32 V_0,
               int64 V_1,
               int32 V_2,
               int64 V_3,
               int32 V_4,
               int64 V_5,
               valuetype [mscorlib]System.DateTime V_6,
               int32 V_7)
      IL_0000:  call       valuetype [mscorlib]System.DateTime [mscorlib]System.DateTime::get_Now()
      IL_0005:  stloc.s    V_6
      IL_0007:  ldloca.s   V_6
      IL_0009:  call       instance int64 [mscorlib]System.DateTime::get_Ticks()
      IL_000e:  call       void [mscorlib]System.Console::WriteLine(int64)
      IL_0013:  call       valuetype [mscorlib]System.DateTime [mscorlib]System.DateTime::get_Now()
      IL_0018:  stloc.s    V_6
      IL_001a:  ldloca.s   V_6
      IL_001c:  call       instance int64 [mscorlib]System.DateTime::get_Ticks()
      IL_0021:  stloc.1
      IL_0022:  ldc.i4.0
      IL_0023:  stloc.0
      IL_0024:  ldc.i4.0
      IL_0025:  stloc.2
      IL_0026:  br.s       IL_007b

      IL_0028:  ldloc.0
      IL_0029:  brtrue.s   IL_002f

      IL_002b:  ldc.i4.1
      IL_002c:  stloc.0
      IL_002d:  br.s       IL_0077

      IL_002f:  ldloc.0
      IL_0030:  ldc.i4.1
      IL_0031:  bne.un.s   IL_0037

      IL_0033:  ldc.i4.2
      IL_0034:  stloc.0
      IL_0035:  br.s       IL_0077

      IL_0037:  ldloc.0
      IL_0038:  ldc.i4.2
      IL_0039:  bne.un.s   IL_003f

      IL_003b:  ldc.i4.3
      IL_003c:  stloc.0
      IL_003d:  br.s       IL_0077

      IL_003f:  ldloc.0
      IL_0040:  ldc.i4.3
      IL_0041:  bne.un.s   IL_0047

      IL_0043:  ldc.i4.4
      IL_0044:  stloc.0
      IL_0045:  br.s       IL_0077

      IL_0047:  ldloc.0
      IL_0048:  ldc.i4.4
      IL_0049:  bne.un.s   IL_004f

      IL_004b:  ldc.i4.5
      IL_004c:  stloc.0
      IL_004d:  br.s       IL_0077

      IL_004f:  ldloc.0
      IL_0050:  ldc.i4.5
      IL_0051:  bne.un.s   IL_0057

      IL_0053:  ldc.i4.6
      IL_0054:  stloc.0
      IL_0055:  br.s       IL_0077

      IL_0057:  ldloc.0
      IL_0058:  ldc.i4.6
      IL_0059:  bne.un.s   IL_005f

      IL_005b:  ldc.i4.7
      IL_005c:  stloc.0
      IL_005d:  br.s       IL_0077

      IL_005f:  ldloc.0
      IL_0060:  ldc.i4.7
      IL_0061:  bne.un.s   IL_0067

      IL_0063:  ldc.i4.8
      IL_0064:  stloc.0
      IL_0065:  br.s       IL_0077

      IL_0067:  ldloc.0
      IL_0068:  ldc.i4.8
      IL_0069:  bne.un.s   IL_0070

      IL_006b:  ldc.i4.s   9
      IL_006d:  stloc.0
      IL_006e:  br.s       IL_0077

      IL_0070:  ldloc.0
      IL_0071:  ldc.i4.s   9
      IL_0073:  bne.un.s   IL_0077

      IL_0075:  ldc.i4.0
      IL_0076:  stloc.0
      IL_0077:  ldloc.2
      IL_0078:  ldc.i4.1
      IL_0079:  add
      IL_007a:  stloc.2
      IL_007b:  ldloc.2
      IL_007c:  ldc.i4     0x3b9aca00
      IL_0081:  blt.s      IL_0028

      IL_0083:  call       valuetype [mscorlib]System.DateTime [mscorlib]System.DateTime::get_Now()
      IL_0088:  stloc.s    V_6
      IL_008a:  ldloca.s   V_6
      IL_008c:  call       instance int64 [mscorlib]System.DateTime::get_Ticks()
      IL_0091:  stloc.3
      IL_0092:  ldc.i4.0
      IL_0093:  stloc.0
      IL_0094:  ldc.i4.0
      IL_0095:  stloc.s    V_4
      IL_0097:  br.s       IL_00fa

      IL_0099:  ldloc.0
      IL_009a:  stloc.s    V_7
      IL_009c:  ldloc.s    V_7
      IL_009e:  switch     ( 
                            IL_00cd,
                            IL_00d1,
                            IL_00d5,
                            IL_00d9,
                            IL_00dd,
                            IL_00e1,
                            IL_00e5,
                            IL_00e9,
                            IL_00ed,
                            IL_00f2)
      IL_00cb:  br.s       IL_00f4

      IL_00cd:  ldc.i4.1
      IL_00ce:  stloc.0
      IL_00cf:  br.s       IL_00f4

      IL_00d1:  ldc.i4.2
      IL_00d2:  stloc.0
      IL_00d3:  br.s       IL_00f4

      IL_00d5:  ldc.i4.3
      IL_00d6:  stloc.0
      IL_00d7:  br.s       IL_00f4

      IL_00d9:  ldc.i4.4
      IL_00da:  stloc.0
      IL_00db:  br.s       IL_00f4

      IL_00dd:  ldc.i4.5
      IL_00de:  stloc.0
      IL_00df:  br.s       IL_00f4

      IL_00e1:  ldc.i4.6
      IL_00e2:  stloc.0
      IL_00e3:  br.s       IL_00f4

      IL_00e5:  ldc.i4.7
      IL_00e6:  stloc.0
      IL_00e7:  br.s       IL_00f4

      IL_00e9:  ldc.i4.8
      IL_00ea:  stloc.0
      IL_00eb:  br.s       IL_00f4

      IL_00ed:  ldc.i4.s   9
      IL_00ef:  stloc.0
      IL_00f0:  br.s       IL_00f4

      IL_00f2:  ldc.i4.0
      IL_00f3:  stloc.0
      IL_00f4:  ldloc.s    V_4
      IL_00f6:  ldc.i4.1
      IL_00f7:  add
      IL_00f8:  stloc.s    V_4
      IL_00fa:  ldloc.s    V_4
      IL_00fc:  ldc.i4     0x3b9aca00
      IL_0101:  blt.s      IL_0099

      IL_0103:  call       valuetype [mscorlib]System.DateTime [mscorlib]System.DateTime::get_Now()
      IL_0108:  stloc.s    V_6
      IL_010a:  ldloca.s   V_6
      IL_010c:  call       instance int64 [mscorlib]System.DateTime::get_Ticks()
      IL_0111:  stloc.s    V_5
      IL_0113:  ldloc.3
      IL_0114:  ldloc.1
      IL_0115:  sub
      IL_0116:  call       void [mscorlib]System.Console::WriteLine(int64)
      IL_011b:  ldloc.s    V_5
      IL_011d:  ldloc.3
      IL_011e:  sub
      IL_011f:  call       void [mscorlib]System.Console::WriteLine(int64)
      IL_0124:  ret
    } // end of method Program::Main

    .method public hidebysig specialname rtspecialname 
            instance void  .ctor() cil managed
    {
      // コード サイズ       7 (0x7)
      .maxstack  1
      IL_0000:  ldarg.0
      IL_0001:  call       instance void [mscorlib]System.Object::.ctor()
      IL_0006:  ret
    } // end of method Program::.ctor

  } // end of class Program


// =============================================================

} // end of namespace Project1

//*********** 逆アセンブリが完了しました ***********************
// WARNING: Created Win32 resource file time-r.res

テスト

準備万端いよいよテストです。

632842745417500000
52500000
35781250

まあ、こんな結果です。しかしながら、この結果はこのコード、私のテスト環境、によって作られた結果であるため軽はずみに信用しないでください。主な理由次の通りです。

ネイティブの命令にどう落とされているのかがわからない。
これは仕方がないですが、JITが特殊な最適化をしない場合switchの命令をそのままジャンプテーブルに対応させそうな気がします。ただし、これがif文連続に対するILコードの節約だった場合はその限りでないと考えられます
ジャンプテーブルでは分岐予測ができない
まだ裏は取っていませんが、ユーザー側でプログラムレジスタを強制的に変えている時点で分岐予測に多大な影響があると思います。もしもジャンプテーブルに対しても分岐予測ができたとしても分岐命令と違い一箇所から同じ確率でまったく別な場所にジャンプしてしまうので精度の悪い予測しかできない可能性もあります。

ただし、このコストはif文側の分岐予測が最大2回以上外れるのと違い1回しか外れないため効率がよくなる場合も考えられます。しかし、この場合においても多回数分岐をまわすことによって統計的に分岐が当たりやすくなる可能性も考えられます。
実行環境の違いによる分岐予測精度と手法の違い。
JITコンパイラではプロセッサごとに最適化を行っているらしいですが、その最適化が分岐予測の精度をどの程度加味したものかはこちら側から把握することが出来ません。プロセッサによっては分岐予測精度も、分岐予測時のロスも違います。たとえば、Pen4ではパイプラインが深いため、分岐予測がはずれるとかなりのロスを生じます。

これらの結果から言えることは、よりJITコンパイラにとって最適化しやすいILコードを書くことです。たとえば、「case 0:」ラベルしかないようなswitchではブランチした方が、コード量も、コード意味も伝わると思います。色々と考えてみるのが良いと思います。

ページの一番上へ
前のページへ一覧に戻る次のページへ

初版2006-5-14 最終更新2006-5-26

質問から意見、誤字訂正まで気軽に連絡してください。
こちらに掲示板も用意しています。「プログラム掲示板」
リンクに関してはご自由にどうぞ。
書いてある情報については、特に断り書きがない限り自由に使ってください。そのまま転載しても、書き換えたりして再利用してもかまいません。