C#におけるTypeをキーにした非ジェネリック関数の最適化法

MicroResolver 2.3.3！というわけで、例によってバージョンがデタラメになるんですが、アップデートしてました。MicroResolverとその解説については以前のブログ記事 MicroResolver - C#最速のDIコンテナライブラリと、最速を支えるメタプログラミングテクニック をどうぞ。そして、オフィシャルな(?)ベンチマーク結果でも、それなりに勝利を収めています。

|Container|Singleton|Transient|Combined|Complex|Property|Generics|IEnumerable| |:------------|------------:|------------:|-----------:|----------:|:------------|----------:|--------------:| |No|61
53|68
62|83
103|90
82|119
99|73
79|177
139| |abioc 0.6.0|27
37|31
57|48
84|63
72|
|
|741
506
| |Autofac 4.6.0|749
623|707
554|1950
1832|6510
6472|6527
6417|1949
1563|7715
5635| |DryIoc 2.10.4|29
42|38
63|55
80|62
70|82
92|50
84|259
184| |Grace 6.2.1|27
38|35
58|49
82|67
75|87
94|46
77|265
194| |Mef2 1.0.30.0|239
167|254
174|332
256|528
317|1188
680|261
429|1345
758| |MicroResolver 2.3.3|31
37|35
59|58
77|92
86|43
66|
|285
203| |Ninject 3.2.2.0|5192
3216|16735
11856|44930
30318|131301*
84559*|112654*
76631*|48775
27198|102856*
68908*| |SimpleInjector 4.0.8|66
68|77
70|103
103|129
105|212
146|75
82|795
451| |Unity 4.0.1|2517
1375|3761
1962|10161
5372|27963
16013|29064
16150|
|43685
23347|

前回の結果はジェネリック版だったのですが、やっぱ物言いがつきまして、非ジェネリック版でやれよ、という話になりました。で、2.0.0は非ジェネリック版で負けちゃってたのです。うーん、そこそこ気を使ってたはずなんですが、負けちゃった。ジェネリック版なら勝ってるんだぜ！とか主張するのは激ダサなので、なんとかして、非ジェネリック版の最適化を進めました。そして、なんとか幾つかのものは勝利を収めました。いや、普通に幾つかのでは負けてるじゃん、って話もありますが、概ね高水準だし、そこは許してください（？）、ジェネリック版なら勝ってるし（ダサい）。理論上、何やればこれ以上に縮められるかは分かってはいるんですけどねー。

というわけで今回は非ジェネリック関数の最適化法について、です。まず、MicroResolverは(ZeroFormtterやMessagePack for C#もそうですが）ジェネリック版を全てのベースにしています。

// というクラスが生成される
public class ObjectResolver_Generated1
{
    // というコードが生成される
    public override T Resolve<T>()
    {
        return Cache<T>.factory(); // Func<T>.Invoke()
    }
}

Tを元にしてデリゲートを探して、それをInvokeする。その最速系がジェネリックタイプキャッシングだという話でした。非ジェネリックの場合は、Typeをハッシュキーにして、デリゲートを探さなければなりません。ここでMicroResolverの初期の実装ではオレオレハッシュテーブルを作って対処しました。

// こんな構造体を定義しておいて
struct HashTuple
{
    public Type type;
    public Func<object> factory;
}
 
// これがハッシュテーブルの中身、基本的に固定配列が最強です
private HashTuple[][] table;
 
// Resolve<T> は、つまりFunc<T> なわけですが、これはFuncの共変を使って直接 Func<object> に変換できます
// ExpressionTree経由で上からデリゲートを生成して変換する、という手が一般に使われますが、
// それは関数呼び出しが一つ増えるオーバーヘッドですからね！
// というわけで、MicroResolverのRegister<T>のTにはclass制約がかかってます
table[hash][index] = new Func<object>(Resolve<T>);
 
// で実際に呼び出すばやい
public object Resolve(Type type)
{
    var hashCode = type.GetHashCode();
    var buckets = table[hashCode % table.Length];
 
    // チェイン法によるハッシュテーブルの配列は、拡縮を考えなくていいので連結リストではなく固定サイズの配列
    // 当然これがループ的には最速だし、ついでに.Lengthで回せるので配列の境界チェックも削れる
    for (int i = 0; i < buckets.Length; i++)
    {
        if (buckets[i].type == type)
        {
            return buckets[i].factory();
        }
    }
 
    throw new MicroResolverException("Type was not dound, Type: " + type.FullName);
}

理屈的には全く良さそうです！しかし、この実装では「遅くて」他のDIライブラリに対してベンチマークで敗北したのです。敗北！許せない！というわけで、ここから更に改善していきましょう。限界まで最適化されているように見えて、まだまだ余地があるのです。目を皿のようにして改善ポイントを探してみましょう！

非ジェネリック関数はジェネリック関数のラップではない

当たり前ですが、ラップにしたらラップしているという点でのオーバーヘッドがかかり、遅くなります。↑のコードはラップではないように見えて、ラップだったのです。どーいうことかというと

// new Func<object>(Resolve<T>) で生成したデリゲートは、こういう呼ばれ順序になる
object Resolve(Type type) => T Resolve() => Cache<T>.factory()

// そう、短縮できますよね、こういう風に
object Resolve(Type type) => Cache<T>.factory()

// つまりこういう風に、生のデリゲートを直接登録しちゃえばよかったのです
table[hash][index] = (Func<object>)Cache<T>.factory();

// ちなみにExpressionTreeで生成する場合は、もっと呼ばれる段数が多くなるので、理屈として一番遅いですね
object Resolve(Type type) => (object)Resolve() => T Resolve() => Cache<T>.factory()

これはもう先入観として非ジェネリックはジェネリックのラップで作らなきゃいけない、と思いこんでいたせいで、全体のコード生成のパスを見渡してみれば、直接渡してあげても良かったんですね。これで、ジェネリック版も非ジェネリック版も、どちらもどちらかのラップではない、ネイティブなスピードを手に入れることができました。

ちなみにジェネリック版が非ジェネリック版のラップの場合は、Typeのルックアップのコストがどちらも必ずかかってしまうので（ジェネリック版がネイティブなスピードにならない）、とても良くないパターンです。

ハッシュテーブルを最適化する

一件、このケースに特化した最速なハッシュテーブルに見えて、既にアルゴリズム的に遅かったのです。剰余が。modulo is too slow。

// これがゲロ遅い
var buckets = table[hashCode % table.Length];

// こうすれば良い(ただしテーブルサイズは2のべき乗である必要があります！)
var buckets = table[hashCode & (table.Length - 1)];

// もちろんテーブルサイズは固定なので、予め -1 したのは変数に持っておきましょう
var buckets = table[hashCode & tableLengthMinusOne];

割と純粋なデータ構造とアルゴリズムのお話ですが、ハッシュテーブルのサイズはどうするのが高速なのか問題、で、テーブルサイズが2のべき乗の場合にはビット演算を使って、低速な剰余を避けることが可能です。ハッシュテーブルに関しては「英語版の」ほうのWikipediaが例によって詳しいです - Hash table - Wikipedia。

.NETのDictionaryはテーブルサイズとして素数を使っています、そのため剰余が避けられません。今回の最初の実装も.NETのものを参考に作っていたので剰余をそのまんま剰余で残してしまったんですねえ。ただし2のべき乗のほうも弱点はあって、ハッシュ関数が悪い場合に、偏りが生じやすくなるとのこと。素数のほうがそれを避けやすい。ので、一般の実装としてやるなら.NETのDictionaryが素数を使うのは最適なチョイスとも思えます。ただ、今回はTypeのGetHashCode、はそれなりにしっかり分散されてるもの（だと思われる）なので、2のべき乗をチョイスするのが効果的といえるでしょう。この辺を弄れるのも、汎用コレクションを使わない利点ですね。まぁ、エクストリームなパフォーマンスを求めるなら、という話ですが。

あとは衝突しなければしないほど高速（衝突したらforループ回る回数が多くなる)なので、テーブルに対するload factorは相当余裕のある感じの設定にしました。かなりスカスカ。まぁ、別にちょっと余計なぐらいでもいいでしょう。

TypeがKeyで、Value側がジェネリックで自由に変更可能な、汎用な固定サイズハッシュテーブルの実装はFixedTypeKeyHashtable.csに置いておきますんで、使えるケースがありそうな人は是非どうぞ。ハヤイデス。Keyは別にType以外にしてもいいんですが、汎用にするとIEqualityComaprer経由で呼ばなきゃいけなくてオーバーヘッドがあるので、もしKeyを他のに変えたければ、そこだけ変えた特化実装を別途用意するのが良いでしょう。Value側は気にする必要はないんですけどね。あと、KeyのGetHashCodeの性質には注意したほうがいいかもです（上述の通り、素数ではないので性質に影響されやすい）

まとめ

どちらの対策も同じように効果絶大でした。どっちも普通だったらそこまで大したことないようなことなんですけどね、マイクロベンチマークで超極小の差を競い合ってる状況では、この差が死ぬほどでかい。というわけで、もう完全に限界の領域。とはいえ、まだまだIoC Performance的には、Singletonには明確に改善の余地があって、事前に生成済みインスタンスを渡してあげるオーバーロードを用意して、その場合は直接埋め込んじゃえばいいとか、そういうこともできます。これは幾つかのDIライブラリがやってますね。役に立たないとは言わないけれど、基本的にはベンチマークハックっぽくて好きくないですが、まぁ、まぁ。

非ジェネリックに関しては type == type を削る余地が残ってます（信頼性は若干犠牲にしますが、事実上問題にならない）。どうやって、というと、登録すべきTypeが全部既知なんですよね、コード生成時に。つまり、非ジェネリック版ももっとアグレッシブにコード生成する余地があり、ハッシュテーブルのルックアップ部分まで含めてコード生成すれば、より改善され（る余地があ）るということです。擬似コードでいえば

// こういうコードを生成する
object Resolve(Type type)
{
    var hashCode = type.GetHashCode();
    switch(hashCode)
    {
        case 341414141:
            // もしハッシュコードが同一のものがあった場合は、生成時に追加でifを入れる
            // ただし通常そんなことは起こらない + 同一ハッシュコードの別タイプが来るケースはほぼない、のでtypeの真の同一値比較を省く
            return new Transient1(); // この中でインライン生成する
        case 643634533:
            return HogeSingleton.Value; // シングルトンは値をそのままルックアップするだけ
        // 以下、型は全て既知でハッシュコードも全部知っているので、羅列する
    }
}

ってコードを作ればいいわけです。こういうのは、まさに動的コード生成の強みを120%活かすって感じで面白くはあります。

ただしintの数値がバラバラの場合は「C#コンパイラが」二分探索コードを作るので - C#のswitch文のコンパイラ最適化について - Grani Engineering Blog、IL生成でこれやるのはかなり骨の折れる仕事です。しかも、二分探索と高速化したハッシュテーブルでは、かなりいい勝負が出来ている状態なので、あえてここまでやるのはちょっと、ってとこもあります。でも、生成部分まで完全にインライン化するのは効果大なので、やればきっと速くなりそうです（でも生成コードサイズはクソデカくなりそうだ）。このアプローチはabiocというIoCライブラリが取っていて、なので実際に最速のパフォーマンスを出せているわけですね。abiocのコード生成はIL EmitではなくRoslynを使っているので、こういった「C#コンパイラ」がやる仕事を簡単に記述できます。アプローチとして面白いやりかたです。

というわけで（？）理論値に挑んだわけですが、どうでしょう。速いコードって実は難しいコードではなくて、コードパスが短いコードが速くなるわけです、どうしても、そりゃそうだ、と。複雑なことをどうやって短い命令数のコード（短いコードという意味ではない）で表現するか。実行時にのみ知りうる情報を使ったコード生成技術を駆使することで、最短のパスを作り込んでいく。そういうことなんですね。

そのうえで、超基本的なアルゴリズムの話が残ってたりするところがあったりで、コンピューターの世界はモダンになったようで、実はあまり変わってないね、という側面もあったりで面白い感じです。

C#は簡単に遅いコードが書ける言語だし、正直割と痛感しているところもあるのですが、とはいえかなりの部分で高速に仕上げる余地が残っている言語でもあります（テンプレートメタプログラミングはできませんが！）。ILを自由に弄れる技術が身につくと「理論上存在する想像する最高のコード」に到れる道のりがグッと広がるので、ぜひぜひ習得してみるのも面白いかと思います。