【C#】Span を List<T>.AddRange する

※ この記事は以下のリンク先で学習した内容であり、参考リンク様1ページの内容が引き伸ばされたものになります。
C#11 による世界最速バイナリシリアライザー「MemoryPack」の作り方 - Speaker Deck

【追記】
.NET 8 ではList.AddRange(ReadOnlySpan)とできる拡張メソッドが追加されました。

現状、List<T>はSpanをAddRange()できない。

var list = new List<int>(10);
Span<int> numSpan = Enumerable.Range(0, 5).ToArray();

list.AddRange(numSpan); // ❌ 'System.Span<int>' から 'System.Collections.Generic.IEnumerable<int>' へ変換することはできません

この例なら配列をSpanで受けずそのまま渡せばいいのだけれど、当然Spanで渡ってきたならそうはできない。

ループで回して要素ごとにAdd()すればいいのだけれど、本来CopyTo()一発で済むところをオーバーヘッドを払わされるのは悲しい。
AddRange()にICollection<T>を渡せばコピー一発でやってくれるのだからなおさら。

// List<T>.AddRange の一部
if (collection is ICollection<T> c)
{
    int count = c.Count;
    if (count > 0)
    {
        if (_items.Length - _size < count)
        {
            Grow(checked(_size + count));
        }

        c.CopyTo(_items, _size);
        _size += count;
        _version++;
    }
}

なお、List<T>からSpanを取り出すCollectionsMarshal.AsSpanについては、カウントでスライスされるため、AddRange()の用途には使えない。

var list = new List<int>(10);
var span = CollectionsMarshal.AsSpan(list);
Console.WriteLine(span.Length);
// 0   <- List の内部配列はキャパシティぶん確保されているが、サイズがゼロなのでゼロ長の Span

ここで冒頭のスライド。
MemoryPack におけるList<T>のデシリアライズでは、書込みビューとなるクラスを用意し、リストをビューにUnsafe.Asして操作しているということ。

internal sealed class ListView<T>
{
    public T[] _items;
    public int _size;
    public int _version;
}

Unsafe.Asは構造体に使うのは普通（？）だけれど、クラスに適用！

今回の例に使ってみる。

ref var view = ref Unsafe.As<List<int>, ListView<int>>(ref list);
view._size = numSpan.Length; // ビューに長さを叩き込む
var span2 = view._items.AsSpan(0, view._size);
numSpan.CopyTo(span2); // 一気にコピー

Console.WriteLine($"Count: {list.Count}, Items: {list.ToListString()}"); // ToListString という拡張メソッドがあるものとする
// Count: 5, Items: [0, 1, 2, 3, 4]

AddRangeに落とし込む。

public static void AddRange<T>(this List<T> list, scoped ReadOnlySpan<T> items)
{
    int count = items.Length;
    if (count < 1) return;

    var len = list.Count + count;
    list.EnsureCapacity(len);

    ref var view = ref Unsafe.As<List<T>, ListView<T>>(ref list);
    items.CopyTo(view._items.AsSpan()[list.Count..]);
    view._size = len;
    view._version++;
}

効用がいかほどか BenchmarkDotNet にて計測。int15万件。

private const int N = 150000;
private List<int> numList = new(N);
private int[] numbers = Enumerable.Range(0, N).ToArray();
private ReadOnlySpan<int> NumberSpan => numbers;

[IterationCleanup]
public void IterationCleanup() => numList.Clear();

[Benchmark]
public int ByLoop()
{
    foreach (var i in NumberSpan) numList.Add(i);
    return numList.Count;
}

[Benchmark]
public int ByAddRangeSpan()
{
    numList.AddRange(NumberSpan);
    return numList.Count;
}

         Method |      Mean |     Error |   StdDev | Allocated |
--------------- |----------:|----------:|---------:|----------:|
         ByLoop | 504.77 μs |  42.80 μs | 2.346 μs |     600 B |
 ByAddRangeSpan |  56.50 μs | 121.66 μs | 6.669 μs |     600 B |

速い。が、N = 15万で100マイクロ秒単位ということや、渡せるならICollection<T>を渡して標準のAPIを使えるので、この例については普通の場面で必要かと言われるとなかなかかもしれない。

ただ、考え方は覚えておきたいと感じた。

てくメモ

trivial な notes

【C#】Span を List<T>.AddRange する