(C#) List<T>からSpan<T>を引き抜いて高速化

List<T>はGetEnumerator()を実装しているため当然foreachで回せる。foreachの速度を落とさないために具象型のEnumeratorを返したりEnumeratorを構造体実装していたりと工夫は凝らされているが、それでもSpan<T>やT[]には数倍～10倍程度遅い。この点に関しては、List<T>は状態をバージョン管理しており、列挙中の変更を検知しているためどうしようもない。forで回したところで、ランタイムによってインデックスの境界値チェックが消える特殊最適化がかかるSpan<T>やT[]には原理的に勝てない。

しかし、List<T>は柔軟で使いやすい。ただ列挙速度も落としたくない。そこで列挙時だけList<T>をSpan<T>にしてしまおうという話。

以下List<T>の実装を簡略化したもの。

public class List<T>
{
    private T[] _items;
    // ・
    // ・
    // ・
}

List<T>の中身はただの配列なので、System.Runtime.CompilerServices.Unsafeで中身を引き抜く。ただし、.NET Framework と .NET Core でList<T>の内部実装が異なるので注意。上記のように、先頭にT[]があるのは共通なのでそこだけ利用する。(メモリレイアウトは必ずしもソースコードの定義順に並ぶわけではないが、今回T[]は先頭に来る)

ちなみに .NET Framework のList<T>ソースはこちら。 github.com

.NET Core のList<T>ソースはこちら。

github.com

List<T>からSpan<T>の引き抜き方は、ダミークラスを用意して拡張メソッドを用意するだけ。

class ListDummy<T>
{
    internal T[] Items;
}

static class ListExtensions
{
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    internal static Span<T> AsSpan<T>(this List<T> list)
    {
        return Unsafe.As<ListDummy<T>>(list).Items.AsSpan(0, list.Count);
    }
}

あとはこれでforeachを回すだけ。

var list = new List<int>();
foreach(var item in list.AsSpan())
{
    Console.WriteLine(item);
}

注意点は3つ。1つはList<T>の中身をすっぽ抜いているので、容量の拡大時に参照が変わるのでSpan<T>を保持してはいけない。これは一般的な可変長配列の実装を理解していれば分かると思う。上記のAsSpan()はUnsafeの力によって実質無料みたいなものなのでその都度AsSpan()してください。

2つ目はこの方法はList<T>の内部実装に依存しているため、将来的にランタイムのバージョンが上がった時にList<T>のメモリレイアウトが変わると正しく動かない点。なのでpublicなライブラリとして公開するのは怖い。自分で管理できる範囲でどうぞ。

3つ目は、yield returnできない点。これはどちらかというとref structの制約。Span<T>.Enumeratorはref structなのでインスタンスがヒープに乗ってしまうyield returnはできない。

List<T>をSpan<T>にしてforeachを回すと当然Span<T>と同速が得られるため、使いどころによっては速度改善につながるかもしれない。

[2020/12/31 追記]

.NET5 からは新たに追加されたSystem.Runtime.InteropServices.CollectionsMarshal.AsSpanメソッドを使うと、Unsafeクラスを使わず合法的にList<T>からSpan<T>を取り出せます。

var list = new List<int>();
Span<T> span = CollectionsMarshal.AsSpan(list);

ネコのために鐘は鳴る

寺院に住み着くパソコ〇好き

(C#) List<T>からSpan<T>を引き抜いて高速化