【C#】ループの最適化手法　②List<T>編　～List<T>はSpan<T>化すると数倍早い～

## はじめに

この記事は配列編の続きです。先に配列編を読まれることをおすすめします。

https://qiita.com/Kujiro/items/fafd3468690a896139b3

## `List<T>` のパフォーマンス

関係するベンチマーク結果を抜き出すとこんな感じです。
ポイントは

- 配列より流石に遅い。
- `for` と `foreach` でパフォーマンスが違う
- `IEnumerable<T>` 扱いするよりは格段に早い

ことです。

`List<T>` では、利用者側でできる最適化手法は最後に紹介する１つ以外ありません。どちらかといえば、標準ライブラリ側でどんな工夫をしているかの紹介になります。

|                  Method |       Mean |    Error |   StdDev |
|------------------------ |-----------:|---------:|---------:|
|                ArrayFor |   530.3 μs |  7.36 μs |  6.89 μs |
|           ConstArrayFor |   547.2 μs |  2.47 μs |  2.06 μs |
|                 ListFor |   625.0 μs | 10.18 μs |  9.03 μs |
|             ListForeach | 1,097.5 μs | 11.69 μs | 10.36 μs |
|  IEnumerableListForeach | 5,215.4 μs | 68.93 μs | 61.10 μs |



## `List<T>` のしくみ

以下の説明で、`List<T>` というか可変長の配列リストというものがどういう仕組みなのか知っていないと困るので簡単に説明します。知っている人は読み飛ばしてください。

`List<T>` クラスは配列をフィールドとして保持しており、これが `List<T>` の中身です。そして、要素を追加するときにこの配列を拡張します。
ただし、拡張するとはいっても配列の長さを伸ばすことはできません。実際には、より長い新しい配列を確保して、もともとの配列から要素をすべてコピーして再代入しています。

ここで問題になるのがこの拡張操作のコストです。長さが `n` のとき、長さ `2n` の配列を確保して `n` 個の要素をコピーするので、これは計算量が `O(n)` の操作になります。
要素を追加するたびに `O(n)` かかるとたまったものではないので、ある程度まとめて拡張することを考えます。
ここで、「足りなくなったら配列の長さを2倍に拡張」ことを考えます。2のべき乗は (定数倍の) 計算コストが安いのでだいたいこの実装になります。
この場合、拡張操作で新たに `n` 個の余裕ができますから、`O(n)` 操作 が `1/n` 確率で発生することになり、要素の追加の計算量が平均して `O(1)` になります。 
狐につままれたような気がしますが、こういう理屈で `List<T>` への `Add` は `O(1)` です。

したがって、`List<T>` の実態は、その要素数 (`Count`) 以上の長さを常に持つ配列が裏側に存在するという状況です。
慣習的に、裏側の配列の長さは Capacity と呼称します。

`List<T>` は普通にクラスとして実装されているので、普通にソースコードが読めます。

https://source.dot.net/#System.Private.CoreLib/List.cs

冒頭はこんな感じです。

```cs
public class List<T> : IList<T>, IList, IReadOnlyList<T>
{
    private const int DefaultCapacity = 4;

    internal T[] _items; // Do not rename (binary serialization)
    internal int _size; // Do not rename (binary serialization)
    private int _version; // Do not rename (binary serialization)
}
```

配列、( `List<T>` としての ) 長さを保持していることがわかります。(あと書き換え時の一貫性保証のためのバージョンがあります) 
配列の最初のキャパシティは `4` で、(掲載はしませんが) 足りなくなると 2倍の長さで確保しなおして `Array.Copy` しています。

## `List<T>` のインデクサー実装

インデクサー (`[]`) は、配列に対しては専用命令でしたが、`List<T>` の場合は普通にメソッド呼び出しです。
その実装は

```cs
public T this[int index]
{
    get
    {
        // Following trick can reduce the range check by one
        if ((uint)index >= (uint)_size)
        {
            ThrowHelper.ThrowArgumentOutOfRange_IndexMustBeLessException();
        }
        return _items[index];
    }

    set
    {
        if ((uint)index >= (uint)_size)
        {
            ThrowHelper.ThrowArgumentOutOfRange_IndexMustBeLessException();
        }
        _items[index] = value;
        _version++;
    }
}
```

となっています。色々と工夫がされていますね。

### 「0以上X未満」の最適化 

`index` として正当な値は、`0` 以上、`List<T>` の `Count` (`_size`) 未満です。
愚直に実装すると、

```cs
if (index < 0 || index >= size)
{
    // throw exception
}
```

と、2回比較して OR になります。

しかし、負の整数の場合、先頭の符号ビットに `1` が立っていることに注目しましょう。
`size` は常に正なので、先頭の符号ビットは常に `0` です。したがって、**符号なし** 整数としてみると、負の数のほうが常に大きいことになります。
この点を理解すると、`List<T>` の実装で使われている `if ((uint)index >= (uint)_size)` がよくできていることがわかります。
この方法では 1 比較で済むので、愚直な方法より高速です。

### 例外スローの切り出し

`throw` 文 (あるいは式) は、インライン化を阻害することが知られています。
今回のような、短い関数の場合は通常であればインライン化されることが期待されるため、`throw` を書くのを避けたいです。
そのため、例外をスローするための関数を用意する手法がよく使われます。
今回の `List<T>` でも、`ThrowHelper.ThrowArgumentOutOfRange_IndexMustBeLessException();`という形で、 `throw` を避けています。

[前回の配列編で自作配列型を実装するとき](https://qiita.com/Kujiro/items/fafd3468690a896139b3#%E9%85%8D%E5%88%97%E5%9E%8B%E3%81%AE%E5%86%8D%E7%8F%BE%E5%AE%9F%E9%A8%93)に、最初この点を忘れて実装してしまい、とんでもない差がついてびっくりしました。
`List<T>` の内部実装と同じ手法で正しく実装した自作配列型は、以下のように配列と変わらないパフォーマンスでしたが

|        Method |     Mean |    Error |   StdDev |
|-------------- |---------:|---------:|---------:|
|      ArrayFor | 57.11 ms | 0.193 ms | 0.151 ms |
| ConstArrayFor | 58.88 ms | 0.195 ms | 0.163 ms |
|   MyArraySafe | 59.54 ms | 0.294 ms | 0.260 ms |
| MyArrayUnsafe | 57.42 ms | 0.101 ms | 0.079 ms |

例外を投げる部分を関数に切り出すのを忘れ、普通に `throw` すると

|        Method |      Mean |    Error |   StdDev |
|-------------- |----------:|---------:|---------:|
|      ArrayFor |  57.25 ms | 0.366 ms | 0.306 ms |
| ConstArrayFor |  58.75 ms | 0.209 ms | 0.163 ms |
|   MyArraySafe | 218.97 ms | 0.572 ms | 0.477 ms |
| MyArrayUnsafe |  57.81 ms | 0.526 ms | 0.492 ms |

3.7倍遅くなりました。単純な関数であればあるほどインライン化の有無の差が開くので注意が必要です。

### 境界値チェックの問題

以上のように、`List<T>` のインデクサーの実装は結構工夫がされています。この工夫がどう影響するのか、逆アセンブル結果を見てみましょう。

```nasm:Benchmark.ListFor ()
L0000    push    rsi
L0001    sub    rsp, 0x20
L0005    xor    esi, esi
L0007    mov    rcx, 0x7ff847e3cea8
L0011    mov    edx, 1
L0016    call    0x00007ff8a709dae0
L001b    mov    rdx, [rax+8]
L001f    cmp    dword ptr [rdx+0x10], 0
L0023    jle    short L004f
L0025    mov    rdx, [rax+8]
L0029    cmp    esi, [rdx+0x10]
L002c    jae    short L0062
L002e    mov    rdx, [rdx+8]
L0032    cmp    esi, [rdx+8]
L0035    jae    short L0068
L0037    movsxd    rcx, esi
L003a    cmp    dword ptr [rdx+rcx*4+0x10], 0xf423f
L0042    je    short L0057
L0044    inc    esi
L0046    mov    rdx, [rax+8]
L004a    cmp    esi, [rdx+0x10]
L004d    jl    short L0025
L004f    xor    eax, eax
L0051    add    rsp, 0x20
L0055    pop    rsi
L0056    ret    
L0057    mov    eax, 1
L005c    add    rsp, 0x20
L0060    pop    rsi
L0061    ret    
L0062    call    System.ThrowHelper.ThrowArgumentOutOfRange_IndexException()
L0067    int3    
L0068    call    0x00007ff8a709f120
L006d    int3    
```

例外スローを関数に切り出したことから期待される通り、インライン化が実行され、インデクサーの関数呼び出しは消失し、境界値チェックも少ない命令数で表現され、配列への `for` に近いアセンブリが生成されています。しかし、配列の場合よりループ本体がやや長いようです。

`List<T>` では、`Count` (`_size`) を超えていないかどうかをチェックしていました。裏の配列の長さ、キャパシティは、`List<T>` としての長さより長いことがあるため、この独自の境界値チェックが必要なのです。もちろん、`List<T>` は普通のクラスなので、配列と異なりランタイムでの特殊扱いなどはなく、ループごとにチェックされます。

この時点で、裏の配列へのアクセスが範囲外にならないことは保証されています。しかし、前回説明したように配列への境界値チェックの最適化は結構狭い範囲を見て自明かどうかを判断しており、ここまで大局的な判断はしてくれません。よって、無慈悲にも境界値チェックがランタイムによりさらに挿入されます。

結果として、ループ本体に境界値チェックが 2 回入るという悲しい結果になります。
`L0025` ~ `L002c` の3命令が `List<T>` としての境界値チェック、`L002e` ~ `L0035` が 裏側の配列への境界値チェックです。
これは、境界値チェック 0 回が実現できる配列への `for` と比較するとまぁまぁのペナルティで、今回だと 20% 程度のオーバーヘッドになっています。

## List<T> への `foreach`

`List<T>` への `foreach` に関して注目されるのは

- `for` より低速
- `IEnumerable<T>` 扱いより高速

という点です。配列の場合とは異なり、`foreach` が `for` 相当に展開されるということはやはりないので、一旦は `GetEnumerator()` ~ `MoveNext()` ~ `Current` にコンパイルされます。

```cil:Benchmark.ListForeach ()
IL_0000	ldsfld	Benchmark.list
IL_0005	callvirt	List <Int32>.GetEnumerator ()
IL_000A	stloc.0	
IL_000B	br.s	IL_001F
IL_000D	ldloca.s	00 
IL_000F	call	Enumerator <Int32>.get_Current ()
IL_0014	ldc.i4	FF E0 F5 05  // 99999999
IL_0019	bne.un.s	IL_001F
IL_001B	ldc.i4.1	
IL_001C	stloc.1	
IL_001D	leave.s	IL_003A
IL_001F	ldloca.s	00 
IL_0021	call	Enumerator <Int32>.MoveNext ()
IL_0026	brtrue.s	IL_000D
IL_0028	leave.s	IL_0038
IL_002A	ldloca.s	00 
IL_002C	constrained.	List <T>.Enumerator
IL_0032	callvirt	IDisposable.Dispose ()
IL_0037	endfinally	
IL_0038	ldc.i4.0	
IL_0039	ret	
IL_003A	ldloc.1	
IL_003B	ret	
```

ここで、`foreach` の仕様の面白い部分があります。「`foreach` は `IEnumerable` を処理できる」は正しいですが、実はそれ以外も処理することができるのです。
つまり、`GetEnumerator()` の部分はいわゆるダックタイピングになっていて、`IEnumerable` を実装することは必要条件ではなく、単に `GetEnumeraor` というメソッドを実装すればよいです。シンプルに `{object}.GetEnumerator()` というコード相当に展開されるため、インスタンスメソッド・拡張メソッドの別も問いません。

この仕様を `List<T>` はうまく活用しています。

```cs
public Enumerator GetEnumerator()
    => new Enumerator(this);

IEnumerator<T> IEnumerable<T>.GetEnumerator()
    => new Enumerator(this);

IEnumerator IEnumerable.GetEnumerator()
    => new Enumerator(this);
```

と、`IEnumerable<T>` インターフェイスを実装するための `GetEnumerator` とは別の `GetEnumerator` メソッドが用意されているのです。
そして、`foreach` はダックタイピングなので、ここでオーバーロード解決が入ります。もちろん、一致度が高い `List<T>.GetEnumerator` に解決されます。

このとき、`Enumerator` として、`IEnumerator<T>` 型ではなく、具象型の `List<T>.Enumerator` 型が返っています。
この型は以下のような **構造体** です。

```cs
public struct Enumerator : IEnumerator<T>, IEnumerator
{
    private readonly List<T> _list;
    private int _index;
    private readonly int _version;
    private T? _current;

    internal Enumerator(List<T> list)
    {
        _list = list;
        _index = 0;
        _version = list._version;
        _current = default;
    }

    public void Dispose()
    {
    }

    public bool MoveNext()
    {
        List<T> localList = _list;

        if (_version == localList._version && ((uint)_index < (uint)localList._size))
        {
            _current = localList._items[_index];
            _index++;
            return true;
        }
        return MoveNextRare();
    }

    private bool MoveNextRare()
    {
        if (_version != _list._version)
        {
            ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumFailedVersion();
        }

        _index = _list._size + 1;
        _current = default;
        return false;
    }

    public T Current => _current!;

    object? IEnumerator.Current
    {
        get
        {
            if (_index == 0 || _index == _list._size + 1)
            {
                ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumOpCantHappen();
            }
            return Current;
        }
    }

    void IEnumerator.Reset()
    {
        if (_version != _list._version)
        {
            ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumFailedVersion();
        }

        _index = 0;
        _current = default;
    }
}
```

結果として、`MoveNext()` や `Current` が静的関数呼び出しになります。
これがダックタイピング、パターンベースの強い所の1つで、インターフェイスを介する場合に発生する仮想関数呼び出しのコストを回避できるのです。
静的関数呼び出しはインライン化できますから、`foreach` はJITコンパイル時には関数呼び出しがすべて消失します。

```nasm:Benchmark.ListForeach ()
L0000    sub    rsp, 0x28
L0004    mov    rcx, 0x7ff847e3cea8
L000e    mov    edx, 1
L0013    call    0x00007ff8a709dae0
L0018    mov    rdx, [rax+8]
L001c    mov    edx, [rdx+0x14]
L001f    mov    rax, [rax+8]
L0023    mov    edx, [rax+0x14]
L0026    mov    ecx, edx
L0028    xor    r8d, r8d
L002b    jmp    short L0036
L002d    cmp    r9d, 0xf423f
L0034    je    short L0076
L0036    cmp    ecx, edx
L0038    jne    short L0080
L003a    cmp    r8d, [rax+0x10]
L003e    jae    short L0067
L0040    mov    r9, [rax+8]
L0044    cmp    r8d, [r9+8]
L0048    jae    short L0086
L004a    movsxd    r10, r8d
L004d    mov    r9d, [r9+r10*4+0x10]
L0052    inc    r8d
L0055    mov    r10d, 1
L005b    test    r10d, r10d
L005e    jne    short L002d
L0060    xor    eax, eax
L0062    add    rsp, 0x28
L0066    ret    
L0067    mov    r8d, [rax+0x10]
L006b    inc    r8d
L006e    xor    r9d, r9d
L0071    xor    r10d, r10d
L0074    jmp    short L005b
L0076    mov    eax, 1
L007b    add    rsp, 0x28
L007f    ret    
L0080    call    System.ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumFailedVersion()
L0085    int3    
L0086    call    0x00007ff8a709f120
L008b    int3    
```

と、`foreach` の C# コンパイラのレベルでのコンパイル結果からは想定できないくらいマシなアセンブリが生成されます。
ただし、
- もちろん、配列への境界値チェックの最適化は入らない
- `for` のときの 2 重境界値チェックはないが、列挙中に `List<T>` が編集されていないことを保証する比較がある
- 終端に達した場合の特殊対応がある
 
と、やはりオーバーヘッドはそれなりにあり、`List<T>` への `for` のときよりさらにループ本体が長くなっています。
これはベンチマーク結果にも表れていて、配列や `List<T>` への `for` よりさらに遅いです。

しかし、`IEnumerable<T>` 扱いより 5 倍 も高速であることはとにかく素晴らしいの一言です。
これはおもにインライン化の恩恵であり、ダックタイピングが生きています。

## 追記：`ForEach` メソッド

ちょうどこの記事を書いている頃、別の方がこんな記事を書いていました。

https://qiita.com/AtaruMatsudaira/items/a3f801043d50326dcbff

`ForEach` メソッドの存在を忘れていたのですが、せっかくなので検証してしまいましょう。
こんなテストケースを追加します。

```cs
public bool ListForeachMethod()
{
    bool found = false;
    list.ForEach(n =>
    {
        if (n == target)
        {
            found = true;
        }
    });
    return found;
}
```

### 結果

``` ini
BenchmarkDotNet=v0.13.1, OS=Windows 10.0.22621
AMD Ryzen 7 1700, 1 CPU, 16 logical and 8 physical cores
.NET SDK=6.0.301
  [Host]     : .NET 6.0.6 (6.0.622.26707), X64 RyuJIT
  DefaultJob : .NET 6.0.6 (6.0.622.26707), X64 RyuJIT
```

#### N=1M

|                 Method |       Mean |    Error |   StdDev |
|----------------------- |-----------:|---------:|---------:|
|               ArrayFor |   530.3 μs |  3.46 μs |  3.07 μs |
|                ListFor |   826.6 μs |  2.84 μs |  2.37 μs |
|            ListForeach | 1,107.3 μs |  9.96 μs |  9.31 μs |
|      ListForeachMethod | 2,184.0 μs |  7.19 μs |  5.61 μs |
|               SpanList |   293.8 μs |  1.93 μs |  1.51 μs |
| IEnumerableListForeach | 4,654.7 μs | 35.60 μs | 31.55 μs |
|               ListLinq |   174.6 μs |  0.37 μs |  0.31 μs |

#### N=100M

|                 Method |      Mean |    Error |   StdDev |
|----------------------- |----------:|---------:|---------:|
|               ArrayFor |  57.13 ms | 0.273 ms | 0.242 ms |
|                ListFor |  83.72 ms | 0.503 ms | 0.446 ms |
|            ListForeach | 111.20 ms | 0.144 ms | 0.113 ms |
|      ListForeachMethod | 219.46 ms | 1.657 ms | 1.384 ms |
|               SpanList |  38.29 ms | 0.287 ms | 0.255 ms |
| IEnumerableListForeach | 465.18 ms | 5.701 ms | 5.054 ms |
|               ListLinq |  27.10 ms | 0.290 ms | 0.271 ms |

と、元記事と同じ傾向の結果が得られました。

### 考察

結果を得て満足せずに、原因を探しに行き汎用的なテクニックを発見するのが私のモットーなので今回も考察をしましょう。
まずは `ForEach` メソッドのソースコードをば。

```cs
public void ForEach(Action<T> action)
{
    if (action == null)
    {
        ThrowHelper.ThrowArgumentNullException(ExceptionArgument.action);
    }

    int version = _version;

    for (int i = 0; i < _size; i++)
    {
        if (version != _version)
        {
            break;
        }
        action(_items[i]);
    }

    if (version != _version)
        ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumFailedVersion();
}
```

- 実態は `for` 文
  - だがループ条件が最適化掛かる形式ではないので境界値チェックが入る 
  - とはいえ、二重ではない
- `List<T>` が列挙中に変更されてないことを確認している
  - ただし、ループの前と後で比較してるだけでループごとに確認はしてない
- `Action<T>` による仮想関数呼び出しがある
  - インライン化を阻害

しかし、`ForEach` は標準ライブラリ内の関数なので、そのままでは LinqPadで逆アセンブルできないのでどうしたものか悩んだのですが
結局 `List<T>`のソースコードの要所をコピペして逆アセンブルしました。  

```nasm:List <Object>.ForEach (Action <Object>)
L0000	push	rdi
L0001	push	rsi
L0002	push	rbp
L0003	push	rbx
L0004	sub	rsp, 0x28
L0008	mov	rsi, rcx
L000b	mov	rdi, rdx
L000e	test	rdi, rdi
L0011	je	short L0053
L0013	mov	ebx, [rsi+0x14]
L0016	xor	ebp, ebp
L0018	cmp	dword ptr [rsi+0x10], 0
L001c	jle	short L0045
L001e	cmp	ebx, [rsi+0x14]
L0021	jne	short L0045
L0023	mov	rcx, [rsi+8]
L0027	cmp	ebp, [rcx+8]
L002a	jae	short L0076
L002c	movsxd	rdx, ebp
L002f	mov	rdx, [rcx+rdx*8+0x10]
L0034	mov	rax, rdi
L0037	mov	rcx, [rax+8]
L003b	call	qword ptr [rax+0x18]
L003e	inc	ebp
L0040	cmp	ebp, [rsi+0x10]
L0043	jl	short L001e
L0045	cmp	ebx, [rsi+0x14]
L0048	jne	short L0070
L004a	add	rsp, 0x28
L004e	pop	rbx
L004f	pop	rbp
L0050	pop	rsi
L0051	pop	rdi
L0052	ret	
L0053	mov	ecx, 1
L0058	mov	rdx, 0x7ffe2ec8c060
L0062	call	0x00007ffe8e010390
L0067	mov	rcx, rax
L006a	call	ThrowHelper.ThrowArgumentNullException(System.Object)
L006f	int3	
L0070	call	ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumFailedVersion()
L0075	int3	
L0076	call	0x00007ffe8e16f120
L007b	int3	
```

ループ本体に関数ポインタをオペランドにした `call` 命令が残っていることがわかります。
`for` でみられた、二重の境界値チェックや、`foreach` でみられた、バージョンの確認といったコストは回避できているのですが、
ループ本体に関数ポインタによる関数呼び出しが残っていることのペナルティが非常に大きいです。

ということで、仮想関数呼び出しとそれに伴うインライン化阻害のペナルティが致命的で、`foreach` よりは低速であるが、
いずれにせよ仮想関数呼び出しを避けられない `IEnumerable<T>` 扱いと比較すれば、`MoveNext()` ~ `Current` とループごとに二回呼び出すよりマシですし
境界値チェックやバージョン確認のコストは比較的回避できている、というところでしょうか。

## 内部イテレーター vs 外部イテレーター

`foreach` などの、列挙操作の実装として、内部イテレーターと外部イテレーターの2つがあります。
`List<T>.ForEach` メソッドは、コレクション内部で列挙操作を実装し、列挙ごとに行うメソッドを外部から挿入してもらう方式になっていますが、こういうのを、列挙操作をコレクション内部で実装することから、内部イテレーターと呼びます。
逆に、`foreach` では、`MoveNext()` ~ `Current` メソッドを公開することで、要素の取得操作をする方法を提供されています。ループ (制御フローを前に飛ばす行為) は利用者側で行うことから、こういうのは外部イテレーターと呼ばれます。

https://ufcpp.net/study/csharp/sp2_itpattern.html

つまり、`List<T>.ForEach` と `foreach` とのパフォーマンス差というのは、内部イテレーターと外部イテレーターのパフォーマンス差と言えるわけです。
ご存知の通り、C# は `IEnumerable<T>` 経済圏なので、言語全体として外部イテレーターを選択したことになります。
外部イテレーターの方が柔軟に操作ができる、などのメリットもありますが (途中でやめたり、無限に続くイテレーターを作ったりしてもOK) 、実装が複雑になります。

通説では、実装が複雑で `MoveNext()` ~ `Current` とループあたり2回呼び出さなければいけない外部イテレーターの方が遅いことになっていますが、

- ラムダ式で渡したものはインライン化されない
　-　内部イテレーターは絶対にインライン化されない 
- foreach はダックタイピング `GetEnumeraotr` を介する
  - 外部イテレーターは、`List<T>` など具象型に対してはインライン化される可能性がある

ということを考慮すると、先程のように、
`List<T>に外部イテレーター < List<T>に内部イテレーター < IEnumerable<T>に外部イテレーター`
という実行時間順になります。つまり、

- 具象型(`List<T>`など) には 外部イテレーターが高速
- 抽象型(`IEnumerable<T>`など) には 内部イテレーターが高速

という事情になるわけです。この辺は `foreach` がダックタイピングにした言語設計者の妙という感です。

## `List<T>` の `Span<T>` 化

では、最後に `List<T>` に対するループを高速化する方法を検討します。
逆アセンブル結果を踏まえると、`for` ループを回すときに、境界値チェックが 2 回も入るのが問題でした。これを 0 回に減らすことができれば、オーバーヘッドはなくなるでしょう。

これには、配列に対する場合と同じような境界値チェックの最適化を、任意の型に対して適用できればよいことは明らかです。
しかし、無数にある型それぞれを特殊扱いするようにランタイムに手を入れるのは、メンテナンスなども含めれば高コストで、いい選択ではありません。
よって、このニーズはありながらもずっと配列だけが特殊扱いされる状況で、これを回避するにはアンマネージドポインタくらいしか選択肢がありませんでした。

しかし、C# 7時代に `Span<T>` という包括的な解決策が導入されました。
これにより、「境界値チェックの最適化」を配列以外でも享受できるようになったのです。
さらに、.NET 5 で `List<T>` を `Span<T>` に変換するメソッドが標準ライブラリに導入され、(それ以前から黒魔術的に知られていた手法ではありましたが)、`List<T>` の `Span<T>` 化は、かなり実践的な最適化テクニックに昇格した感があります。

`Span<T>` 化の理屈はシンプルで、`List<T>` の裏側の配列のうち、「`List<T>` の `Count` まで」をスライスして取得するだけです。
この領域は、**もとの `List<T>` の要素数を変更しない限り** 範囲外になる可能性はありません。
なお、**もとの `List<T>` の要素数を変更しない限り** の部分は **実装者責任** です。



やり方はとてもシンプルで、

```cs
System.Runtime.InteropServices.CollectionsMarshal.AsSpan(list)
```

で終わりです。このメソッドの内部実装は

```cs
public static Span<T> AsSpan<T>(List<T>? list)
    => list is null ? default : new Span<T>(list._items, 0, list._size);
```

と、やはりかなり単純です。しかし、ベンチマークをとると

|                  Method |       Mean |    Error |   StdDev |
|------------------------ |-----------:|---------:|---------:|
|                ArrayFor |   530.3 μs |  7.36 μs |  6.89 μs |
|           ConstArrayFor |   547.2 μs |  2.47 μs |  2.06 μs |
|                 ListFor |   625.0 μs | 10.18 μs |  9.03 μs |
|             ListForeach | 1,097.5 μs | 11.69 μs | 10.36 μs |
|  IEnumerableListForeach | 5,215.4 μs | 68.93 μs | 61.10 μs |
|                SpanList |   289.3 μs |  0.83 μs |  0.65 μs |

と、**驚異的** なパフォーマンスが出ます。
`Span<T>` の方が配列より早いという不思議な結果が出てしまいました。
このへんの謎は、また次回解説したいと思います。

## 次回

https://qiita.com/Kujiro/items/21d004bc74449765dbf7