連載：深入り.NETプログラミング インライン・メソッド・キャッシュによる動的ディスパッチ高速化 NyaRuRu Microsoft MVP Windows - DirectX（Jan 2004 - Dec 2008） 2008/11/18
Page1 Page2 Page3

■インライン・メソッド・キャッシュ（inline method caching）

　多くのプログラミング言語では、同じように見える構文に異なる振る舞いを割り当てることが行われている（多態性）。振る舞いの決定にはしばしば型が用いられ、コンパイル時に確定する型情報を用いて振る舞いを決定する方法（静的多態）と、実行時型情報を用いて振る舞いを決定する方法（動的多態）の2つに大きく分けられる。

　動的多態には、オブジェクトの実行時型によって処理が分岐するもの（メソッド・オーバーライドなど）や、オブジェクトの実行時型とパラメータの実行時型のペアで処理が分岐するもの（ダブル・ディスパッチなど）がある。こういった動的分岐処理を想定しながら、次の疑似コードをご覧いただきたい。

void some_work1(object a, object b) {   a.foo(b); // fooは動的多態メソッドで、             // ほとんどの場合aはint型でbはstring型 } void some_work2(object a, object b) {   a.foo(b); // fooは動的多態メソッドで、             // ほとんどの場合aはstring型でbはint型 }

動的多態の疑似コード：some_work1メソッドとsome_work2メソッド

　ここで、インライン・メソッド・キャッシュによるsome_work1メソッドの書き換えを行う。

　まず、実際にsome_work1メソッドを実行してみて、その結果からほとんどの場合、オブジェクトaはint型で、オブジェクトbはstring型だと分かったとする。この結果を基に、some_work1を以下のように書き換える。

void some_work1(object a, object b) {   if ( a != null && a.GetType() == typeof(int)     && b != null && b.GetType() == typeof(string) )   {     // キャッシュ・ヒット時     specialized_foo1( (int)a, (string)b );   }   else   {     // キャッシュ・ミス時     generic_foo1(a, b);   } }

インライン・メソッド・キャッシュによるsome_work1メソッドの書き換え

　この例のように、1種類の型ペアのみを想定してメソッド・キャッシュを行うものが「単相的インライン・メソッド・キャッシュ（monomorphic inline method caching）」である。さらに想定するケースを増やしたものは「多相的インライン・メソッド・キャッシュ（polymorphic inline method caching）」と呼ばれる。

　実行時に動的に実行コードを変更できる処理系では、メソッド・キャッシュをネイティブ・コード自体に埋め込んでしまうことが多い。この場合、実行開始時には単相的インライン・メソッド・キャッシュを用いたネイティブ・コードを生成し、キャッシュ・ミスが多発するようであれば多相的インライン・メソッド・キャッシュを利用したネイティブ・コードに書き換える。

　キャッシュ・ヒット時の実装にもいくつかの手法が考えられる。

　まず、先ほど示したように型を特殊化したメソッド実装を1カ所にプールしておき、キャッシュ・ヒット時にはそこにジャンプさせる方法がある。あるいは、以下のように特殊化した処理をその場にインライン展開してしまうことも可能だ。

void some_work1() {   if ( a != null && a.GetType() == typeof(int)     && b != null && b.GetType() == typeof(string) )   {     // specialized_foo1( (int)a, (string)b );     // をここにインライン展開する     ･･････省略･･････   }   else   {     // キャッシュ・ミス時     generic_foo1(a, b);   } }

キャッシュ・ヒット時には特殊化した処理をその場にインライン展開させる方法

　JavaではHotSpot VMの時代にこのような研究が盛んに行われていたようである（日本IBMの石崎 一明さんがPPL Summer School 2004で行った講演資料）。

■スタブベース・ディスパッチ

　.NET Frameworkにおいては、CLR（Common Language Runtime） 2.0以降のJITコンパイラが、インターフェイス・メソッドの呼び出しにスタブベース・ディスパッチ（Stub-based dispatch）という手法を用いている。これは実質的に単相的インライン・メソッド・キャッシュである。

　現在のCLR実装では、インターフェイスを経由したメソッド呼び出しは、ほかの仮想メソッド（virtual method）呼び出しよりも若干オーバーヘッドを伴う。このオーバーヘッドはCLRが使用しているオブジェクト内部表現によるものだ。インターフェイスを経由したメソッド呼び出しでは、メソッドの実際のアドレスを得るために通常の仮想メソッド呼び出しよりも1段階余分なテーブル参照（インターフェイス・メソッド・テーブルの参照）が必要になる。

　以下に3種類のメソッド呼び出し（非仮想なメソッド呼び出し、インターフェイスを経由しない仮想メソッド呼び出し、インターフェイスを経由した仮想メソッド呼び出し）を素直にJITコンパイルするとどうなるかを示そう。MSDNマガジンの記事「Drill Into .NET Framework Internals to See How the CLR Creates Runtime Objects」より引用する。

; mc.Method1(); // 非仮想的なメソッド呼び出し mov  ecx,esi                  ; move "this" pointer into ecx cmp  dword ptr [ecx],ecx      ; compare and set flags call dword ptr ds:[009552D8h] ; directly call Method1 ; mc.Method3(); // 仮想メソッド呼び出し（インターフェイスを経由しない場合） Mov  ecx,esi              ; move "this" pointer into ecx Mov  eax,dword ptr [ecx]  ; acquire the MethodTable address Call dword ptr [eax+44h]  ; dispatch to the method at offset 0x44 ; mi1.Method1(); // 仮想メソッド呼び出し（インターフェイスを経由する場合） mov  ecx,edi                 ; move "this" pointer into ecx mov  eax,dword ptr [ecx]     ; move "TypeHandle" into eax mov  eax,dword ptr [eax+0Ch] ; move IVMap address into eax at offset 12 mov  eax,dword ptr [eax+30h] ; move the ifc impl start slot into eax call dword ptr [eax]         ; call Method1

3種類のメソッド呼び出しを「原則的に」JITコンパイルした際のネイティブ・コード

「原則的な」JITコンパイル後のネイティブ・コード（このコードは、MSDNマガジンの記事より引用したもの）。「原則的な」と書いたのは、実際には後述するテクニックが利用されることがあるためである。 インターフェイスを経由する場合のメソッド呼び出しは、仮想メソッド呼び出しよりもさらにテーブル参照が1回分多いオーバーヘッドを伴うことが分かる。

　では、実際に生成されるコードはどうだろうか？ 手元の環境（Windows Vista x86、.NET Framework 3.5 SP1）で筆者が調べてみたところ、インターフェイス・メソッド呼び出しは以下のようなネイティブ・コードに変換されていた。

; mi1.Method1();// 仮想メソッド呼び出し（インターフェイスを経由する場合） mov  ecx,esi                  ; move "this" pointer into ecx call dword ptr ds:[00170010h] ; 00170010h番地に書かれているアドレスを読み出してそこにジャンプ

筆者の環境（Windows Vista x86、.NET Framework 3.5

SP1）でのインターフェイスを経由した仮想メソッド呼び出し。Visual Studioのデバッガで確認可能だ。

　00170010h番地には、JITコンパイラが作り出したスタブ・コード（仲介コード）のアドレスが書かれている。ジャンプ先のアドレスを毎回取得しているのは、スタブ・コードの更新を容易にするためであろう。スタブ・コードを新しいものに差し替えたいときには、新しいスタブ・コードのアドレスを（アトミックに）00170010h番地へ書き込めばよい。

　初回実行時に00170010h番地から参照されているスタブ・コードは、仮想メソッドの分岐を行うだけでなく、初回実行時のオブジェクトの実行時型を記録するという役目も持っている。

　2回目にこのスタブ・コードにジャンプすると、いよいよスタブ・コードの更新が始まる。2代目のスタブ・コードが生成され、そのアドレスが00170010h番地に書き込まれる。新しく生成されたスタブ・コードは以下のような内容になっている。

cmp dword ptr [ecx],1649C8h ; 初回実行時に実行された型のオブジェクト・ヘッダと比較 jne 0017A1F1 ; 初回実行時とは型が異なる場合（汎用処理） jmp 003F04B0 ; 初回実行時と型が同じ場合は直接、対象メソッドにジャンプ

00170010h番地が新しく参照を始めた2代目のスタブ・コード

Visual StudioのデバッガはCLRが生成したネイティブ・コードを逆アセンブルしてくれないので、この逆アセンブル結果を見るにはSon of Strike（SOS）の「!u <アドレス>」コマンドを活用する。

　この2代目のスタブ・コードに含まれる003F04B0hというアドレスは、初回実行時に実行されたインスタンス・メソッドのアドレスである。つまり、初回実行時の型と同じ型が渡されると、インターフェイス・メソッドの呼び出しはcall＋cmp＋jmpの3命令で実行できる。現在のx86 CLRは、初回実行時と同じ型のオブジェクトが渡される可能性に賭けているようだ。

　もちろんCLRは賭に負け続ける可能性も想定している。0017A1F1hは、予想が外れた場合に実行されるコードで、インターフェイス・メソッド・テーブルを参照する教科書的な実装となっている。ただしこの処理にはカウンタが仕込んである。カウンタの初期値は100で、実行されるたびに（つまり最初の予想が外れるたびに）1減算される。カウントが0になると、CLRは「キャッシュ・ミスが多すぎる」として3代目のスタブ・コードを生成する。3代目のスタブ・コードは最初からインターフェイス・メソッド・テーブルを参照するだけの汎用実装である。この新しい実装にはカウンタは存在しない。賭けに負け続けるぐらいなら、賭けそのものをやめて、常にテーブル参照を行うようにするわけだ。

　今回紹介した振る舞いは、最初に単相的インライン・メソッド・キャッシュを試みて、うまくいかない場合はメソッド・キャッシュを削除する戦略と解釈できる。もちろんCLRが常にこのように振る舞うという保証はない。とはいえ、実際にインライン・メソッド・キャッシュが使われている実例には十分だろう。

INDEX
	［連載］深入り.NETプログラミング
	インライン・メソッド・キャッシュによる動的ディスパッチ高速化
	1．次世代JavaScriptエンジン
	2．インライン・メソッド・キャッシュ／スタブベース・ディスパッチ
	3．多相的インライン・メソッド・キャッシュ

「深入り.NETプログラミング」

＠ITメールマガジン　新着情報やスタッフのコラムがメールで届きます（無料）