Edited at

迫真DynamicMethod! FieldAccessExceptionをスルーした先輩!

新年明けましておめでとうございます。

初投稿です。


問題提起

C#大統一理論にも書いてあるとおり、.NETで唯一信頼できるコレクションはT[]のみです。

この間System.Collections.Generic.SortedSet<T>のMinとMaxの実装を読んたのですが、ゲッターを呼ぶ度にdelegate新規作成とメモリアロケーションが発生していました。

2019年にもなってこんな頭おかしい実装をしているとは……

System.Collections.Generic.List<T>はかなりまともな実装をしていますので性能的に悲惨なことにはなりません。

Tが参照型であるならば……

Tが巨大な値型の時、我々はList<T>に喰い潰されるのだ!(ダダオーン!)

そもそもint[]の読み書きと比較してList<int>のインデクサは3~4倍程度遅いです。

そしてList<T>のインデクサは参照戻り値を返さないのでTが巨大な値型の時コピーコストが嵩んで性能的にますます不利になります。

また、for文においてT[]ならば範囲チェックを免れることもありますが、List<T>は常に範囲チェックを行われてしまいます。

どうですか?

System.Collections.Generic.List<T>を使う気が失せてきやしませんか?

今までHoge Function<T>(IList<T> list)とか書いていたメソッドシグネチャを是非Hoge Function<T>(ref T[] array, ref int length)に書き改めましょう!

上記提案は十割本気ですが、既存資産を大事にしたい方も多いでしょうから、妥協的現実的魔術的代案を今回記事にします。


解決策


りふれくしょん(おそーい)

using System;

using System.Reflection;
using System.Collections.Generic;

public struct GetArrayFromList<T>
{
public static T[] GetArray(List<T> list) => (T[])arrayField.GetValue(list);
private static readonly FieldInfo arrayField;
static GetArrayFromList()
{
// 全privateフィールドを取得
FieldInfo[] fis = typeof(List<T>).GetFields(BindingFlags.NonPublic | BindingFlags.Instance);
for(int i = 0; i < fis.Length; ++i)
{
// 配列であるならばそれをarrayFieldにぱぱっと格納して、終わり!
if(fis[i].FieldType.IsArray)
{
arrayField = fis[i];
break;
}
}
}
}

軽く解説すると上記コードはGeneric Type Cacheという技法を使用しています。参考文献

GetArray静的メソッドは内部的に静的コンストラクタによって用意されたFieldInfoオブジェクトを通じてプライベートフィールドを得ます。

静的コンストラクタでは全プライベートフィールドを線形に走査して配列型のフィールドを探しています。

あ^^ー、GetArrayを呼ぶ度にリフレクションが走るんじゃ~。

AOTなUnityのIL2CPP環境でもない限り上記コードは遅すぎて使う気にもなりませんね。

T[]がList<T>よりも高速に読み書き可能とはいえ、それを得るためのオーバーヘッドが大きすぎます。


DynamicMethod

以下のコードは.NET 4.x系と.NET Core系でしか動きません。.NET Standard 2.0で動かないです。

.NET Standard 2.1からは動かせるようになる予定です。

using System;

using System.Reflection;
using System.Reflection.Emit;
using System.Collections.Generic;

public struct GetArrayFromListChache<T>
{
// staticメソッドではなくstatic delegateを定義します。
public static readonly Func<List<T>, T[]> GetArray;
static GetArrayFromListChache()
{
DynamicMethod method = new DynamicMethod("GetArray", MethodAttributes.Public | MethodAttributes.Static, CallingConventions.Standard, typeof(T[]), new Type[] { typeof(List<T>) }, typeof(List<T>), true);
FieldInfo[] fis = typeof(List<T>).GetFields(BindingFlags.NonPublic | BindingFlags.Instance);
FieldInfo arrayField;
for(int i = 0; i < fis.Length; ++i)
{
if(fis[i].FieldType.IsArray)
{
arrayField = fis[i];
break;
}
}
ILGenerator ilgen = method.GetILGenerator();
ilgen.Emit(OpCodes.Ldarg_0); // 第0引数について
ilgen.Emit(OpCodes.Ldfld, arrayField); // その内部に抱えているprivateなT[]なフィールドを
ilgen.Emit(OpCodes.Ret); // 戻り値とせよ
GetArray = (Func<List<T>, T[]>)method.CreateDelegate(typeof(Func<List<T>, T[]>));
}
}

実はList<T>におけるprivateなT[]フィールドの名前は_itemsとわかっていて、Type.GetFieldメソッドで直接入手可能ではありますが、なにせprivateフィールドなのでいつ何時リファクタリングされないともわからないのでプログラム実行時に動的にFieldInfoを得るようにしています。

前と今の最大の違いはなんと言ってもSystem.Reflection.Emit.DynamicMethodクラスでしょう。

これは実行時に動的にメソッドを作成するためのクラスです。

そのコンストラクタのシグネチャは

public DynamicMethod(string name, MethodAttributes attributes, CallingConventions callingConvention, Type returnType, Type[] parameterTypes, Type owner, bool skipVisibility);

です。(CallingConventionsは常にStandardでなければなりません。)

このコンストラクタの引数であるType ownerにList<T>、bool skipVisibilityにtrueを渡すことで、我々が今新たに作成するメソッドがあたかも元からList<T>のメンバーメソッドであるかのように扱われるのです。つまりprivateメンバを好き勝手できます。

具体的にどう好き勝手するかはGetILGeneratorで返されるILGeneratorオブジェクトを通じてILを書いて決めます。

ここでは今回作成するメソッドの第0引数のフィールドを値で返しています。つまりList<T>内部にあるT[]を返しています。

そして最後にobject DynamicMethod.CreateDelegate(Type)でデリゲートを作成し、static readonlyなFunc<List<T>, T[]> GetArrayに代入しましょう。

我々はGetArrayデリゲートを使用する時に内部的にリフレクションを使用せずとも良くなりました。


結論

List<T>しか受け取らないAPIを用意した奴は反省して、どうぞ。


感想

デリゲートは性能的に割と駄目な子なのでldftn+calliでもっと速くできると思いました(小並感)