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

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

　スタブベース・ディスパッチのほかに、.NETの世界でお目にかかるインライン・メソッド・キャッシュといえば、DLR（Dynamic Language Runtime）での採用例が挙げられる。DLRのインライン・メソッド・キャッシュはパフォーマンス上重要で、頻発するobject型への処理に活躍する。この理由は、動的言語ならではの難しさにある。

　IronPythonやIronRubyで書かれたプログラム・コードは実行前にDLRの抽象構文木（DLR AST）に変換されるのだが、この段階で現れる型のほとんどはobject型（System.Objectクラス）とせざるを得ない。IronPythonやIronRubyといった動的言語では、コンパイル時に式の型を決めてしまうことが困難であったり不可能であったりするため、.NETの型システムとの対応を考えると、結局object型になってしまう。

　話はそれるが、冒頭で述べた次世代JavaScriptエンジンのTracing JITは、ここを頑張って最適化する。Tracing JITは、実行時型によって処理フローをツリー状に分解する。これによって、実行時型がstring型だった場合のループと、int型だった場合のループは、実行ルートとして別物になり、それぞれのケースでの適切なネイティブ・コードが生成される。詳細については前掲のAndreas Galの論文やomoさんの解説記事を参照していただきたい。

　これに比べれば、現在のDLRのアプローチは保守的だ。DLR ASTにばらまかれたobject型は、実行時に生成される動的メソッドのシグネチャにも引き継がれる。プリミティブ型のボックス化は頻発するし、object型として受け取ったパラメータに対する動的分岐も必要になる。

　例として、IronPython 2.0で次のような関数を考える。

def myadd(a, b):   return a + b

IronPython 2.0で記述した関数

　IronPython 2.0とDLRは、この式から以下のような動的メソッドを生成する。

object myadd(Closure closure, object a, object b) {   var addSite = (CallSite<Func<CallSite,object,object,object>>) closure.Constants[0];   return addSite.Target(addSite, a, b); }

IronPython 2.0とDLRにより上記の関数から生成された動的メソッド

　a、b、a + bの結果の型は事前に決められないので、すべてobject型として扱われていることが分かる。 addSite.Targetは、メソッドのように見えるが実際にはFunc<CallSite, object, object, object>型のフィールドで、このフィールドに実際の加算処理を行う動的メソッドが格納される。addSite.Targetがメソッドではなくフィールドであることに注意しつつ、以下では単にaddSite.Targetと書くことにしよう。（実際このCallSiteオブジェクトの設計は、Targetという名前のインスタンス・メソッドに見えるという視覚的効果を狙ったものだろう）

　比較のために、Microsoft.VisualBasic.dllアセンブリに存在するOperatorsクラスを紹介しよう。Operatorsクラスには、Operators.AddObjectという静的メソッドがある。このメソッドは、型指定されていないオブジェクトの加算のためにVisual Basicコンパイラが利用するものだ。

object  Microsoft.VisualBasic.CompilerServices.Operators.AddObject(object  a, object b)

Microsoft.VisualBasic.dllに存在する静的メソッドOperators.AddObject

ソース・コードは「Microsoft Reference Source Code Center」で公開されているので、興味がある方は参照してみるとよいだろう。その内部処理は巨大なswitch caseとリフレクションだ。可能な限りswitch caseで分岐し、それでも駄目ならリフレクションで加算を行うというコードである。

　Operators.AddObjectメソッドは最初からすべてのケースに対応するのに対し、差し替え可能という性質を持つaddSite.Targetは過去に遭遇した型のペアのみに対応する。

　もしも未知の型のペアがaddSite.Targetに渡されたときは、動的メソッド内部でaddSite.Updateメソッドがコールバックされる。addSite.Updateメソッドは、渡されたオブジェクトに対する正しい結果を返しつつ、必要に応じて動的メソッドを新しいものに差し替える。

　例えば、「myadd(1, 2)」を実行した直後のaddSite.Targetは次のコードと等価である。

static object _stub_(CallSite arg0, object arg1, object arg2) {   if ( (arg1 != null && arg1.GetType() == typeof(int))     && (arg2 != null && arg2.GetType() == typeof(int)) )   {     return (object)Int32Ops.Add((string)arg1, (string)arg2);   }   var site = (CallSite<Func<CallSite,object,object,object>>)arg0;   return site.Update(arg0, arg1, arg2); }

「myadd(1, 2)」を実行した直後のaddSite.Targetと等価なコード

　これはint型を仮定した単相的インライン・メソッド・キャッシュといえる。

　この後さらに、「myadd("1", "2")」を実行すると、addSite.Updateメソッドを経由して動的メソッドが更新され、次のようになる。

static object _stub_(CallSite arg0, object arg1, object arg2) {   if ( (arg1 != null && arg1.GetType() == typeof(string))     && (arg2 != null && arg2.GetType() == typeof(string)) )   {     return (object) StringOps.Add((string)arg1, (string)arg2);   }   var site = (CallSite<Func<CallSite,object,object,object>>) arg0;   return site.Update(arg0, arg1, arg2); }

更新された動的メソッド

　今度はstringを仮定した単相的インライン・メソッド・キャッシュになった。

　ここでもう一度、「myadd(1, 2)」を実行してみよう。これは再度addSite.Updateメソッドを呼び出すはずだ。

static object _stub_(CallSite arg0, object arg1, object arg2) {   if ( (arg1 != null && arg1.GetType() == typeof(string))     && (arg2 != null && arg2.GetType() == typeof(string)) )   {     return (object) StringOps.Add((string)arg1, (string)arg2);   }   if ( (arg1 != null && arg1.GetType() == typeof(int))     && (arg2 != null && arg2.GetType() == typeof(int)) )   {     return (object) Int32Ops.Add((string)arg1, (string)arg2);   }   var site = (CallSite<Func<CallSite,object,object,object>>)arg0;   return site.Update(arg0, arg1, arg2); }

再度更新された動的メソッド

　結果として、addSite.Targetはint型とstring型の両方を想定する多相的インライン・メソッド・キャッシュに変化した。myadd関数の使われ方によって最適化が進行したといえる。

　最後に、これがインライン・メソッド・キャッシュであることも説明しておこう。新しく次のようなmyadd2関数を作成すると、myadd2関数には別のaddSiteオブジェクトが結び付けられる。

def myadd2(a, b):   return a + b

新たに作成したmyadd2関数

　ここでmyadd2関数には「myadd2(1.0, 2.0)」のようにdouble型のみを使ってみる。すると、myadd2関数に結び付けられたaddSite.Targetはdouble型に特化したものになる。

static object _stub_(CallSite arg0, object arg1, object arg2) {   if ( (arg1 != null && arg1.GetType() == typeof(double))     && (arg2 != null && arg2.GetType() == typeof(double)) )   {     return (object) DoubleOps.Add((double)arg1, (double)arg2);   }   var site = (CallSite<Func<CallSite,object,object,object>>) arg0;   return site.Update(arg0, arg1, arg2); }

myadd2関数に結び付けられたaddSite.Target

　もちろんmyadd関数に結び付けられたaddSite.Targetは元のままだ。myadd関数とmyadd2関数の使われ方の違いはきちんと動的メソッドに反映されており、インライン・メソッド・キャッシュとして働いていることが分かる。

　これらの仕組みは、DLR内で自動化されている。そのおかげで、すべてのDLR言語がメソッド・キャッシュの恩恵を受けることができる。

　Visual Basicではどうだろうか？ Visual Basicの事前型付けされない加算処理では、呼び出し元ごとの傾向の違いは考慮されない。プログラム中の足し算はすべて単一のOperators.AddObjectメソッドに丸投げされ、呼び出し経路によらず同じ汎用処理が行われる。この部分では、呼び出し経路に応じた適応型の最適化を行うDLRの方が高速に動作しても不思議ではない。

■まとめ

　今回は動的多態メソッドの高速化テクニックとしてインライン・メソッド・キャッシュを取り上げ、その利用例としてCLRのスタブベース・ディスパッチとDLRの多相インライン・メソッド・キャッシュを紹介した。アイデア自体は冒頭のSelf言語の論文にも登場する汎用的なものなので、今後も目にする機会はあるだろう。

　一方で、DLRのメソッド・キャッシュがどのように実装されているかは紹介しきれなかった。興味がある方は、IronPython 2.0のソース・コードを入手し、IronPythonConsoleをVisual Studioでデバッグ実行しながら処理過程を追いかけてみるとよいだろう。やや情報が古いが、Martin Malyによる解説記事も参考になる。また、C# 4.0の新機能dynamicを追いかけていた何人かのブロガーは、その背後にCallSiteオブジェクトを発見したようだ。もし需要があれば、この連載でもあらためて詳細な解説を行いたい。

　以下のブログ記事で、C# 4.0の新機能がCallSiteオブジェクトを使用しているのを確認できる

　最後にDLRに関してもう少し補足しておこう。DLR 1.0では、TraceMonkeyが行っているような大域的な最適化はサポートされない見込みだ。今後、DLRにTracing JITを組み込みたいという話も出るだろう。とはいえ、Tamarin Tracing（ActionMonkey）の失敗を教訓とするなら、ある程度の慎重さと、実績ある前例を参考にすることが必要かもしれない。

　1つの方向性として、Michael Foord氏はPyPyプロジェクト（PythonでPythonの処理系を書くプロジェクト）の名前を挙げている（source）。PyPyプロジェクトはTracing JITへの取り組みを開始しており、さらに出力コードとして.NETの中間コードが利用できる。つまり、PyPyによってTracing JITされたPythonとCLRの組み合わせのポテンシャルを知ることができるわけだ。DLRの速度的なポテンシャルが気になる方は、PyPyプロジェクトの動向にも注目しておくとよいだろう。

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

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

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