タイトル通りですが本記事執筆時点 (2020/4/15) の最新である .NET Core 3.1 ではList<T>のAddRangeメソッドにダイレクトにSpan<T>およびReadOnlySpan<T>を突っ込むことはできません。というのもList<T>のAddRangeメソッドは
public void AddRange(IEnumerable<T> items);
しかオーバーロードがないためです。Span<T>とReadOnlySpan<T>はforeach列挙可能ではあるがIEnumerable<T>ではありませんし、そもそもref structの制約で interface にキャスト不可によりIEnumerable<T>になりえません。
理想としてはAddRangeにReadOnlySpan<T>のオーバーロードが欲しい。(Span<T>はReadOnlySpan<T>への暗黙的キャストが効く上、キャストのコストは実質0なので問題ない`)
Span<int> span = ...; List<int> list = ...; list.AddRange(span); // これができるとうれしい
しかし、実際はできないので、現状の回避策としてはforeachとAddを使うしかない。
Span<int> span = ...; List<int> list = ...; foreach(var item in span) { list.Add(item); }
が、まあ当然列挙毎にAddと列挙のオーバーヘッドが入るのでAddRangeより遅い。Span<T>のもとになっているのが配列 (例えばint[]) とかなら、Span<int>にせず配列のままAddRangeすればIEnumerable<T>に入ってくれるし、AddRange内でのICollection<T>による要素数既知の最適化にハマるので十分早い。しかし、Span<T>のもとになっているのがアンマネージメモリだと配列ではないし、そもそもIEnumerable<T>ですらないのでどうしようもない。
上記のように foreachでAddする以外の選択肢がない。非常に悲しい。
個人的には非常に欲しい API なので .NET Core の github リポジトリの issue に同様の提案が上がっていないのか調べたら、案の定あった。それがこちら。
で、内容をまとめると、
- この API が必要という根拠、具体的なサンプルや場面が欲しい。
- 現状回避策として、自作の
List<T>で置き換えるのが妥当
というようなコメントがついてましたね。。。API の追加は簡単ではない。とはいえ、重要なのはこのリポジトリは本記事執筆時点では close されていません。というかよく見ると、.NET 5 (.NET Core 3.1 の次のメジャーバージョンの .NET) のマイルストーンに 提案 API が入っているではないですか！！歓喜
.NET 5 のリリース予定は 2020/11 までと予定されているため、それまではないですが、.NET 5 ではおそらくReadOnlySpan<T>のオーバーロードが入ると思われます。
.NET Core / .NET Framework ではどうするの
前述の通り、次期リリースでは入るんでしょうが .NET Core / .NET Framework で今私は使いたいんだ！！！と、当然話はそこに帰結する。なので unsafe なC# の暗黒面の力を借りて拡張メソッドで実装した。
static class ListExtension { internal static void AddRange<T>(this List<T> list, ReadOnlySpan<T> span) => list.InsertRange(list.Count, span); internal static void InsertRange<T>(this List<T> list, int index, ReadOnlySpan<T> span) { if(list is null) { throw new ArgumentNullException(); } static void EnsureCapacity(List<T> original, ListDummy<T> dummy, int min) { if(dummy._items.Length < min) { const int DefaultCapacity = 4; int newCapacity = dummy._items.Length == 0 ? DefaultCapacity : dummy._items.Length * 2; // Allow the list to grow to maximum possible capacity (~2G elements) before encountering overflow. // Note that this check works even when _items.Length overflowed thanks to the (uint) cast const int MaxArrayLength = 0X7FEFFFFF; // This size is compatible with Array.MaxArrayLength. (This is internal) if((uint)newCapacity > MaxArrayLength) newCapacity = MaxArrayLength; if(newCapacity < min) newCapacity = min; original.Capacity = newCapacity; } } var dummyList = Unsafe.As<ListDummy<T>>(list); if((uint)index > (uint)dummyList._size) { throw new ArgumentOutOfRangeException(); } int count = span.Length; if(count > 0) { EnsureCapacity(list, dummyList, dummyList._size + count); if(index < dummyList._size) { Array.Copy(dummyList._items, index, dummyList._items, index + count, dummyList._size - index); } span.CopyTo(dummyList._items.AsSpan(index)); dummyList._size += count; dummyList._version++; } } private abstract class ListDummy<T> { internal T[] _items = default!; internal int _size; internal int _version; #if NETFRAMEWORK internal object _syncRoot = default!; #endif private ListDummy() { } } }
[2020/07/25 追記]
これ、気が付いてしまったんですけど、これ単体ならおそらく問題ないような気がしますが、 以前の記事 で
List<T>からSpan<T>を 引っこ抜いてくるのと組み合わせるとちょっとマズイ気がします。 具体的には、List<T>の自分自身から引っこ抜いたSpan<T>を自身にこのAddRangeやInsertRangeすると、 容量拡大時やメモリ移動時におかしなことが起こりそうな気がします。ちょっと詳しく挙動を見ないとわからない (すいません)
これでAddRangeにSpan<T>をダイレクトに入れられます。ついでにInsertRangeも使えます。上記のソースコードを見て何をやってるかは把握してください。というか見て分からない人は使ってはダメです、Unsafeを悪用しているので問題が起こった時に困ると思います。
上記ソースコード中の#if NETFRAMEWORKですが、NETFRAMEWORKは .NET Framework をターゲットにコンパイルしたときには自動で追加されるシンボルです。.NET Framework と .NET Core ではList<T>の持つフィールドが異なるため、必要です。
この拡張メソッドを使うとAddRangeにSpan<T>をダイレクトアタックできます。
最後にベンチマーク。ベンチマークに使ったのは以下の3つのコードで 要素数 N=10000000
int[]をIEnumerable<T>でAddRangeしたものint[]をSpan<T>で自作のAddRangeしたものint[]を、foreach+Addしたもの
で、 BenchmarkDotNet で測定しました。
[MemoryDiagnoser] public class ListPerformanceTest { private const int N = 10000000; private static int[] _items; private List<int> _list; [GlobalSetup] public void GlobalSetup() { _items = new int[N]; } [IterationSetup] public void Setup() { _list = new List<int>(); } [Benchmark(Baseline = true)] public List<int> AddRange_IEnumerable() { IEnumerable<int> items = _items; _list.AddRange(items); return _list; } [Benchmark] public List<int> AddRange_Span() { ReadOnlySpan<int> items = _items; _list.AddRange(items); return _list; } [Benchmark] public List<int> Add_SpanIter() { ReadOnlySpan<int> items = _items; foreach(var item in items) { _list.Add(item); } return _list; } }
結果は以下の通り。
| Method | Mean | Error | StdDev | Ratio | RatioSD | Gen 0 | Gen 1 | Gen 2 | Allocated |
|---|---|---|---|---|---|---|---|---|---|
| AddRange IEnumerable | 18.23 ms | 2.751 ms | 8.111 ms | 1.00 | 0.00 | - | - | - | 38.15 MB |
| AddRange Span | 17.56 ms | 2.609 ms | 7.692 ms | 0.97 | 0.11 | - | - | - | 38.15 MB |
| Add SpanIter | 81.10 ms | 1.584 ms | 2.168 ms | 5.68 | 2.55 | - | - | - | 128 MB |
当然のごとくforeach+Addは遅い。AddRangeのIEnumerable<T>と自作のReadOnlySpan<T>は誤差の範囲内で自作の方が速い。何回か測定してもうちょっと速い時もあったがそれはまあ誤差。対象がint[]なので、ICollection<T>の型チェックによる分岐処理にハマるのでIEnumerable<T>でも十分速い。差が出るのは、IEnumerable<T>の方は他にも微妙に別の型チェックや引数チェックを行ったり、ReadOnlySpan<T>の自作メソッドより余計なことを少ししているせいだろうか。どちらにせよReadOnlySpan<T>のオーバーロードはAddより十分速い。
参考文献
.NET Framework と .NET Core のList<T>のソースコードは以下のリンク。
.NET Core
