(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>
ソースはこちら。
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);