連載:深入り.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オブジェクトを使用しているのを確認できる

- C# "dynamic" - Chris Burrows' Blog
- C# 4.0 - Why Dynamic Binding and Extension Methods Don't Mix - Anders Norås' Blog
- DynamicObjectのパフォーマンス -匣の向こう側 - あまりに.NETな

 最後に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プロジェクトの動向にも注目しておくとよいだろう。End of Article


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

インデックス・ページヘ  「深入り.NETプログラミング」


Insider.NET フォーラム 新着記事
  • 第2回 簡潔なコーディングのために (2017/7/26)
     ラムダ式で記述できるメンバの増加、throw式、out変数、タプルなど、C# 7には以前よりもコードを簡潔に記述できるような機能が導入されている
  • 第1回 Visual Studio Codeデバッグの基礎知識 (2017/7/21)
     Node.jsプログラムをデバッグしながら、Visual Studio Codeに統合されているデバッグ機能の基本の「キ」をマスターしよう
  • 第1回 明瞭なコーディングのために (2017/7/19)
     C# 7で追加された新機能の中から、「数値リテラル構文の改善」と「ローカル関数」を紹介する。これらは分かりやすいコードを記述するのに使える
  • Presentation Translator (2017/7/18)
     Presentation TranslatorはPowerPoint用のアドイン。プレゼンテーション時の字幕の付加や、多言語での質疑応答、スライドの翻訳を行える
@ITメールマガジン 新着情報やスタッフのコラムがメールで届きます(無料)

注目のテーマ

Insider.NET 記事ランキング

本日 月間