List の列挙に関する最適化

# 概要

`List<T>` の列挙は ↓ のようにするとパフォーマンスがよくなる可能性がありますが、広く用いるべきテクニックとは言い難いです。

```cs
List<int> numbers = [1, 2, 3, 4, 5];
var sum = 0;
foreach (var n in System.Runtime.InteropServices.CollectionsMarshal.AsSpan(numbers))
    sum += n;
```

理由:

- [コレクション変更問題](#コレクション変更問題)
- [`null` 参照問題](#null-参照問題)
- [内部配列変更問題](#内部配列変更問題)

## [`CollectionsMarshal.AsSpan()`](https://learn.microsoft.com/ja-jp/dotnet/api/system.runtime.interopservices.collectionsmarshal.asspan?view=net-8.0) について

リストの内部配列からスパンを作成する関数です。だいたい ↓ のような実装です。

```cs
public static Span<T> AsSpan<T>(List<T>? list)
{
    if (list is null)
        return default;
    return list._items.AsSpan(0, list.Count);
}
```

後述の理由によりリストの中のスパンは副作用があるため、パフォーマンスや簡潔なコードを優先したい場面等にとどめておきたいところです。

## パフォーマンス比較

<details>
<summary>テストコード</summary>

```cs
```

</details>

**x64** のパフォーマンス

| Test                    |  Score |      % |  CG0 |
| ----------------------- | -----: | -----: | ---: |
| ListForEach             |  9,648 | 100.0% |    0 |
| **ListAsSpanForEach**   | 43,139 | 447.1% |    0 |
| ListIEnumerableForEach  |  3,216 |  33.3% |    0 |
| ListIEnumeratorForEach  |  9,691 | 100.4% |    0 |
| ArrayForEach            | 15,324 | 158.8% |    0 |
| ArrayAsSpanForEach      | 17,715 | 183.6% |    0 |
| ArrayUnsafeForEach      | 13,877 | 143.8% |    0 |
| ArrayIEnumerableForEach |  3,414 |  35.4% |    0 |
| ArrayIEnumeratorForEach |    273 |   2.8% |    7 |

実行環境: Windows11 **x64** .NET Runtime 9.0.0  
**Score** は高いほどパフォーマンスがよいです。  
**GC0** はガベージコレクション回数を表します（少ないほどパフォーマンスがよい）。

**x86** のパフォーマンス

| Test                    |  Score |      % |  CG0 |
| ----------------------- | -----: | -----: | ---: |
| ListForEach             | 28,361 | 100.0% |    0 |
| **ListAsSpanForEach**   | 45,596 | 160.8% |    0 |
| ListIEnumerableForEach  |  2,362 |   8.3% |    0 |
| ListIEnumeratorForEach  | 27,961 |  98.6% |    0 |
| ArrayForEach            | 40,134 | 141.5% |    0 |
| ArrayAsSpanForEach      | 36,812 | 129.8% |    0 |
| ArrayUnsafeForEach      | 26,968 |  95.1% |    0 |
| ArrayIEnumerableForEach |  3,019 |  10.6% |    0 |
| ArrayIEnumeratorForEach |    299 |   1.1% |    6 |

実行環境: Windows11 **x86** .NET Runtime 9.0.0  
**Score** は高いほどパフォーマンスがよいです。  
**GC0** はガベージコレクション回数を表します（少ないほどパフォーマンスがよい）。

- **ListAsSpanForEach** の % が、x64 と x86 ではかなり異なります。x64 環境だとよりパフォーマンスが改善しています。通常の ListForEach より顕著にパフォーマンスが良いです。
- ListIEnumerableForEach は、`IEnumerable<T>` インターフェイスごしにメソッドを実行しているため、仮想化のためスコアが落ちています。
- ArrayIEnumeratorForEach は非ジェネリックのためにループ変数を受け取るたびにボックス化と型変換が発生し、非常にパフォーマンスが良くないです。これは古い形式のため、基本的に使うことはないです。
- このテストは毎回結構スコアがぶれます（30 % くらい）。

## コレクション変更問題

リストのスパンを使用する上で問題になるのは、列挙の途中でコレクションが変更されても例外にならない点です。

```cs
`List<int> numbers = [1,` 2, 3, 4, 5];
`foreach (var n in numbers)
{
    if (n ==` 3)
        `numbers.Add(6);
}`
```

自分は昔、よくこのようなコードを書いて実行時 `InvalidOperationException` が投げられて**んもう**となったものです。列挙の途中でコレクションが変更されると「すべての要素を列挙」できなくなるため、例外になるべきです。無限ループになる場合もありますし。

<https://learn.microsoft.com/ja-jp/dotnet/fundamentals/runtime-libraries/system-invalidoperationexception#changing-a-collection-while-iterating-it>

[`CollectionsMarshal.AsSpan()` の定義](https://learn.microsoft.com/ja-jp/dotnet/api/system.runtime.interopservices.collectionsmarshal.asspan?view=net-8.0#definition)のところにも、コレクションを変更する操作をしないよう明記されています。

> `Span<T>` の使用中に、項目を `List<T>` に対して追加または削除することはできません。

## `null` 参照問題

列挙の途中で要素が削除されると、`null` 参照例外になる場合があります。

```cs
List<string> names = ["Alice", "Bob", "Charlie"];
Assert.Throws<NullReferenceException>(() =>
{
    var namesSpan = CollectionsMarshal.AsSpan(names);
    names.Clear();

    var sumNameLength = 0;
    foreach (var n in namesSpan)
        sumNameLength += n.Length;
});
```

これはリストの要素を削除すると、リスト内部の配列のそのアドレスを初期化するため起こります。基本的にリストを使う人はそのアドレスにアクセスできない前提なのですが、スパンを使うとアクセスできてしまうために起こります。

[`nullable`](https://learn.microsoft.com/ja-jp/dotnet/csharp/nullable-references) コードでもこれを検出できません。

## 内部配列変更問題

リストは要素数が増えたときに、内部配列を更新する処理が入ります。
スパンを取得したあとにリストの内部配列が更新されても、取得したスパンは古い配列を参照しているため、期待される動作になりません。

```cs
List<string> names = ["Alice", "Bob", "Charlie"];

var namesSpan = CollectionsMarshal.AsSpan(names);
names.Capacity = names.Capacity + 1;

names[0] = "Dave";
// 古い配列を参照しているため、変更が反映されない
Assert.NotEqual(names[0], namesSpan[0]);
// Assert.Equal("Alice", namesSpan[0]);
```

これらの問題があるため `List<T>.Span` や `List<T>.Memory` は公開できない、というわけですね。

## おわりに

スパンは変数で受け取らず直接 `foreach` に渡すのが無難です。

```cs
foreach (var n in CollectionsMarshal.AsSpan(list))
{
}
```

## おまけ

パフォーマンス以外でも、リストのスパンがほしい場面があります。リストの型が構造体の場合、参照を取って直接操作したいことがあります。

```cs
file record struct Person(string Name, int Age);

List<Person> people = [new Person("Alice", 20), new Person("Bob", 30), new Person("Charlie", 40)];
foreach (ref var n in CollectionsMarshal.AsSpan(people))
    n.Age++;
```

ループ変数を `ref` で受け取っていることが肝です。こうすることで `for` によるインデックス操作をなくすことができ、より簡潔にすることができます。