今日はちょっと将来の話。 提案ドキュメントとか予備実験的な実装はあるんですが、 リリースされる時期については未定のものです。

Guarded Devirtualization という最適化手法。

(余談ですが、この提案に当たっての調査レポート、ものすごく丁寧で良い内容です。 何かを提案する際の理想形。)

Devirtualization の実情

昨日のDevirtualization 最適化の話で書きましたが、 仮想呼び出しを通常のメソッド呼び出しに置き換える最適化があって、これを devirtualization といいます。

ただ、devirtualization できる状況はかなり限られています。 coreclr 内で統計を取ってみたところ、クラスの仮想メソッドの呼び出ししているところのうち15%程度しか、devirtualization 最適化が掛からないそうです。 インターフェイスを介しているものについてはもっときつくて、5%程度だそうです。

なんせ、devirtualization が有効になるためには、「メソッド内をさかのぼれば静的な型が1つに確定している」という状態でないといけない。 それに対して、実際のところ多い状況は、 「ほとんどの場合には決まったある1つの型のが来るものの、まれに別の型が来る」というものです。

if + Devirtualization

そこで、最頻で来てそうな1つ(あるいはせいぜい数個)の型に対してだけ if を挟んでしまうという最適化が考えられます。

例えば、以下のようないくつかの型があったとして

interface I { void M(); }
struct A1 : I { public void M() { } }
struct A2 : I { public void M() { } }
struct A3 : I { public void M() { } }
struct A4 : I { public void M() { } }

以下のような呼び出しを考えます。

static void M(I[] items)
{
    foreach (var i in items)
    {
        i.M();
    }
}

何の前提もないと、このコードは最適化のやりようがないんですが、 例えば、 「ほとんどの場合にA1A4の構造体が来る。他の型が来る率は低い」、 「その中でもA1の頻度が特に高い」みたいな前提が入ると、 以下のようなコードが速くなったりします。

static void M(I[] items)
{
    foreach (var i in items)
    {
        if (i.GetType() == typeof(A1)) ((A1)i).M();
        else if (i.GetType() == typeof(A2)) ((A2)i).M();
        else if (i.GetType() == typeof(A3)) ((A3)i).M();
        else if (i.GetType() == typeof(A4)) ((A4)i).M();
        else i.M();
    }
}

数個程度の if 分岐であれば仮想呼び出しのコストよりも安くなります。 特に、発生確率に偏りがある場合には分岐予測が効くので、 「ほとんどがA1」みたいな状況では分岐のコストがほぼ消えます。 また、メソッド M の実装がインライン展開可能なものだった場合、 インライン展開の効果でかなり速くなります。

ベンチマークを取ってみた感じ、 普通に i.M() で仮想呼び出しするよりも、3倍くらい高速です。

ということで、こういう「よく来る型」を実行時に検出して、上記のようなif分岐を生成するような最適化を CoreCLR に入れたいみたいです。 「ほとんどが A1」という予想が外れたときのための“防護策”(guard)としてif挿入するので、 Guarded Devirtualization と呼ばれます。