【C#】ループの最適化手法　①配列編　～境界値チェックと専用命令と～

## はじめに

`for` や `foreach` でループを回して、配列やリストなどのデータ集合に処理をする。
基本的な処理ですが、ここにも最適化手法が眠っています。

本記事では、より高速なループを記述するためのテクニック、あるいはループを高速化teするために
言語仕様や標準ライブラリで使用されている最適化手法について解説します。

少し詳しい人だと、境界値チェックの最適化や配列の専用命令などを聞いたことがあるかもしれませんが、完全に理解している人は少ないのではないでしょうか。本記事ではそのへんもちゃんと解説したいと思います。

## ベンチマーク

まずは、ここから先の解説の土台として、ベンチマークを実行してみます。
ベンチマークの内容は、0 から N-1 までの `int` 集合に N-1 が含まれるかどうか調べるというものです。つまり、N 回のループが回るようになっています。
`Contains` メソッドでできることですが、今回はループが回る処理の典型として見てください。


`int` 集合として
- 配列 `int[]`
- リスト `List<int>`
- イテレーター `Enumerable.Range`
- 以上を `IEnumerable<int>` でラップしたもの
- 以上を `IList<T>` でラップしたもの

を用意しています。
ループの回し方も

- `for` ループ
- `foreach` ループ
- Linq
- `Span` で `for`

などなど色々検証しております。

ベンチマーク環境は、アーキテクチャの違うCPUを搭載した2つのPCで行っています。
テストサイズは、CPUのL3キャッシュに収まる N = 1M と、収まらない N = 100M をそれぞれ実行します。

結果は解説パートでつまみつまみ見ていきますが、私が解説するより先に内容と結果をすべて公開するほうがフェアだと思うので
すべて載せておきます。適宜見てください。

### ベンチマークコード

<details><summary>コード全文を見る</summary>

```cs
public class Benchmark
{
    const int testSize = 1_000_000;

    const int target = testSize - 1;

    const int helfSize = testSize / 2;

    const int helfTarget = helfSize - 1;

    private static readonly int[] array;

    private static readonly List<int> list;

    private static readonly IEnumerable<int> iterator;

    private static readonly IEnumerable<int> wrappedArray;

    private static readonly IEnumerable<int> wrappedList;

    private static readonly IList<int> listWrappedArray;

    private static readonly IList<int> listWrappedList;

    static Benchmark()
    {
        array = Enumerable.Range(0, testSize).ToArray();
        list = Enumerable.Range(0, testSize).ToList();

        iterator = Enumerable.Range(0, testSize);

        wrappedArray = array;
        wrappedList = list;

        listWrappedArray = array;
        listWrappedList = list;
    }

    // 一般的な配列への for ループ。
    // ローカル変数に置き直しているのでスレッドセーフ => 境界値チェックの最適化を想定。
    [Benchmark]
    public bool ArrayFor()
    {
        var _array = array;
        for (int i = 0; i < _array.Length; i++)
        {
            if (_array[i] == target)
            {
                return true;
            }
        }
        return false;
    }

    // 静的フィールド配列への for ループ。
    // マルチスレッドで書き換えれる => 境界値チェックが入るかも。
    [Benchmark]
    public bool ArrayForField()
    {
        for (int i = 0; i < array.Length; i++)
        {
            if (array[i] == target)
            {
                return true;
            }
        }
        return false;
    }

    // 引数配列への for ループ。
    // これも境界値チェックの最適化が見込まれる。
    [Benchmark]
    public bool ArrayForArg()
    {
        return ArrayForInternal(array);
    }

    private bool ArrayForInternal(int[] _array)
    {
        for (int i = 0; i < _array.Length; i++)
        {
            if (_array[i] == target)
            {
                return true;
            }
        }
        return false;
    }

    // ループ条件を定数 = コンパイラが解析しにくい にした for ループ。
    // 境界値チェックの最適化が入らないだろうケース。
    [Benchmark]
    public bool ConstArrayFor()
    {
        for (int i = 0; i < testSize; i++)
        {
            if (array[i] == target)
            {
                return true;
            }
        }
        return false;
    }

    // foreach による配列へのループ。
    // C#コンパイラ時点で for 相当のコードに展開されるのでパフォーマンス差はほぼないはず。
    [Benchmark]
    public bool ArrayForeach()
    {
        foreach (var n in array)
        {
            if (n == target)
            {
                return true;
            }
        }
        return false;
    }

    // List への for ループ。
    // ldelem 命令じゃなくて関数呼び出しだし境界値チェック最適化できないし、で配列より遅いと思われる。
    // とはいえ、foreach よりは早いと思われる。
    [Benchmark]
    public bool ListFor()
    {
        for (int i = 0; i < list.Count; i++)
        {
            if (list[i] == target)
            {
                return true;
            }
        }
        return false;
    }

    // List への foreach ループ。
    // 多分遅い。
    [Benchmark]
    public bool ListForeach()
    {
        foreach (var n in list)
        {
            if (n == target)
            {
                return true;
            }
        }
        return false;
    }

    // 配列を Span<T> にしてみる。
    // 何故か早い。
    [Benchmark]
    public bool SpanArray()
    {
        return SpanInternal(array);
    }

    // List<T> を Span<T> にしてみる。
    // もともとList<T>遅いこともあり結構効く。
    [Benchmark]
    public bool SpanList()
    {
        return SpanInternal(System.Runtime.InteropServices.CollectionsMarshal.AsSpan(list));
    }

    private bool SpanInternal(Span<int> span)
    {
        for (int i = 0; i < span.Length; i++)
        {
            if (span[i] == target)
            {
                return true;
            }
        }
        return false;
    }

    // ポインタでやる。
    // 境界値チェックとかそもそも概念がないので最速になると思われる。
    // オーバーヘッド計測用の叩き台に。
    [Benchmark]
    public unsafe bool PtrArray()
    {
        fixed (int* ptr = array)
        {
            for (int i = 0; i < testSize; i++)
            {
                if (ptr[i] == target)
                {
                    return true;
                }
            }
        }
        return false;
    }

    // イテレータで舐める。
    // 多分遅い。
    [Benchmark]
    public bool IteratorForeach()
    {
        foreach (var n in iterator)
        {
            if (n == target)
            {
                return true;
            }
        }
        return false;
    }

    // IEnumerable で舐める。
    // 多分遅い。
    [Benchmark]
    public bool IEnumerableArrayForeach()
    {
        foreach (var n in wrappedArray)
        {
            if (n == target)
            {
                return true;
            }
        }
        return false;
    }

    // IEnumerable で舐める。
    // 多分遅い。
    [Benchmark]
    public bool IEnumerableListForeach()
    {
        foreach (var n in wrappedList)
        {
            if (n == target)
            {
                return true;
            }
        }
        return false;
    }

    // IList で舐める。
    // IEnumerable よりマシかもしれない。
    [Benchmark]
    public bool IListArrayFor()
    {
        for (int i = 0; i < listWrappedArray.Count; i++)
        {
            if (listWrappedArray[i] == target)
            {
                return true;
            }
        }
        return false;
    }

    // IList で舐める。
    // foreachなので多分遅い。
    [Benchmark]
    public bool IListArrayForeach()
    {
        foreach (var n in listWrappedArray)
        {
            if (n == target)
            {
                return true;
            }
        }
        return false;
    }

    // IList で舐める。
    // IEnumerable よりマシかもしれない。
    [Benchmark]
    public bool IListListFor()
    {
        for (int i = 0; i < listWrappedList.Count; i++)
        {
            if (listWrappedList[i] == target)
            {
                return true;
            }
        }
        return false;
    }

    // IList で舐める。
    // foreachなので多分遅い。
    [Benchmark]
    public bool IListListForeach()
    {
        foreach (var n in listWrappedList)
        {
            if (n == target)
            {
                return true;
            }
        }
        return false;
    }

    [Benchmark]
    public bool ArrayIndexof()
    {
        return Array.IndexOf(array, target) != -1;
    }

    [Benchmark]
    public bool ListContains()
    {
        return list.Contains(target);
    }

    [Benchmark]
    public bool ArrayLinq()
    {
        return wrappedArray.Contains(target);
    }

    [Benchmark]
    public bool ListLinq()
    {
        return wrappedList.Contains(target);
    }
}
```
</details>

### 結果(N = 1M)

<details>
<summary>結果を見る</summary>

``` 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
```
|                  Method |       Mean |    Error |   StdDev |
|------------------------ |-----------:|---------:|---------:|
|                ArrayFor |   530.3 μs |  7.36 μs |  6.89 μs |
|           ArrayForField |   543.6 μs |  8.33 μs |  7.79 μs |
|             ArrayForArg |   524.3 μs |  2.52 μs |  2.24 μs |
|           ConstArrayFor |   547.2 μs |  2.47 μs |  2.06 μs |
|            ArrayForeach |   530.3 μs |  7.80 μs |  7.29 μs |
|                 ListFor |   625.0 μs | 10.18 μs |  9.03 μs |
|             ListForeach | 1,097.5 μs | 11.69 μs | 10.36 μs |
|               SpanArray |   294.9 μs |  5.61 μs |  5.25 μs |
|                SpanList |   289.3 μs |  0.83 μs |  0.65 μs |
|                PtrArray |   293.7 μs |  5.45 μs |  5.10 μs |
|         IteratorForeach | 4,542.6 μs | 19.08 μs | 16.91 μs |
| IEnumerableArrayForeach | 4,570.1 μs | 24.51 μs | 21.73 μs |
|  IEnumerableListForeach | 5,215.4 μs | 68.93 μs | 61.10 μs |
|           IListArrayFor | 4,802.3 μs | 34.28 μs | 28.63 μs |
|       IListArrayForeach | 4,553.1 μs | 30.93 μs | 24.15 μs |
|            IListListFor |   623.8 μs | 11.22 μs | 10.49 μs |
|        IListListForeach | 5,188.2 μs | 19.26 μs | 16.08 μs |
|            ArrayIndexof |   173.2 μs |  1.10 μs |  0.86 μs |
|            ListContains |   175.3 μs |  2.82 μs |  2.64 μs |
|               ArrayLinq |   175.7 μs |  3.38 μs |  3.16 μs |
|                ListLinq |   162.7 μs |  1.38 μs |  1.23 μs |


``` ini
BenchmarkDotNet=v0.13.1, OS=Windows 10.0.22621
AMD Ryzen 7 4700U with Radeon Graphics, 1 CPU, 8 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
```
|                  Method |       Mean |    Error |   StdDev |
|------------------------ |-----------:|---------:|---------:|
|                ArrayFor |   475.6 μs |  6.07 μs |  5.68 μs |
|           ArrayForField |   508.9 μs |  6.57 μs |  5.83 μs |
|             ArrayForArg |   470.9 μs |  6.06 μs |  5.67 μs |
|           ConstArrayFor |   498.0 μs |  4.99 μs |  4.67 μs |
|            ArrayForeach |   455.4 μs |  8.40 μs |  6.56 μs |
|                 ListFor |   510.3 μs |  2.11 μs |  1.87 μs |
|             ListForeach |   976.1 μs |  4.88 μs |  4.07 μs |
|               SpanArray |   256.6 μs |  3.18 μs |  2.97 μs |
|                SpanList |   250.2 μs |  1.03 μs |  0.86 μs |
|                PtrArray |   259.6 μs |  3.99 μs |  3.74 μs |
|         IteratorForeach | 4,068.1 μs |  3.90 μs |  3.46 μs |
| IEnumerableArrayForeach | 4,084.7 μs | 13.40 μs | 11.87 μs |
|  IEnumerableListForeach | 4,565.7 μs | 10.08 μs |  9.42 μs |
|           IListArrayFor | 4,438.7 μs | 85.26 μs | 98.19 μs |
|       IListArrayForeach | 4,087.7 μs | 15.02 μs | 14.05 μs |
|            IListListFor |   522.5 μs |  2.87 μs |  2.68 μs |
|        IListListForeach | 4,570.1 μs |  9.79 μs |  9.16 μs |
|            ArrayIndexof |   160.9 μs |  1.60 μs |  1.34 μs |
|            ListContains |   167.7 μs |  3.18 μs |  3.54 μs |
|               ArrayLinq |   167.0 μs |  3.26 μs |  4.12 μs |
|                ListLinq |   150.2 μs |  1.19 μs |  0.93 μs |

</details>

### 結果(N = 100M)

<details>
<summary>結果を見る</summary>

``` 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
```
|                  Method |      Mean |    Error |   StdDev |
|------------------------ |----------:|---------:|---------:|
|                ArrayFor |  57.43 ms | 0.530 ms | 0.470 ms |
|           ArrayForField |  57.57 ms | 0.089 ms | 0.070 ms |
|             ArrayForArg |  57.03 ms | 0.107 ms | 0.084 ms |
|           ConstArrayFor |  58.92 ms | 0.850 ms | 0.754 ms |
|            ArrayForeach |  57.58 ms | 0.917 ms | 0.858 ms |
|                 ListFor |  66.11 ms | 0.823 ms | 0.730 ms |
|             ListForeach | 111.49 ms | 0.242 ms | 0.215 ms |
|               SpanArray |  38.52 ms | 0.137 ms | 0.128 ms |
|                SpanList |  38.26 ms | 0.134 ms | 0.105 ms |
|                PtrArray |  38.62 ms | 0.359 ms | 0.300 ms |
|         IteratorForeach | 384.51 ms | 5.253 ms | 4.914 ms |
| IEnumerableArrayForeach | 408.73 ms | 0.963 ms | 0.804 ms |
|  IEnumerableListForeach | 522.03 ms | 8.857 ms | 8.284 ms |
|           IListArrayFor | 438.44 ms | 6.355 ms | 5.634 ms |
|       IListArrayForeach | 408.31 ms | 0.170 ms | 0.151 ms |
|            IListListFor |  65.05 ms | 0.874 ms | 0.818 ms |
|        IListListForeach | 516.65 ms | 0.828 ms | 0.647 ms |
|            ArrayIndexof |  27.41 ms | 0.194 ms | 0.162 ms |
|            ListContains |  27.42 ms | 0.205 ms | 0.160 ms |
|               ArrayLinq |  27.20 ms | 0.296 ms | 0.247 ms |
|                ListLinq |  27.59 ms | 0.547 ms | 0.651 ms |


``` ini
BenchmarkDotNet=v0.13.1, OS=Windows 10.0.22621
AMD Ryzen 7 4700U with Radeon Graphics, 1 CPU, 8 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
```
|                  Method |      Mean |    Error |   StdDev |    Median |
|------------------------ |----------:|---------:|---------:|----------:|
|                ArrayFor |  58.05 ms | 0.197 ms | 0.184 ms |  58.07 ms |
|           ArrayForField |  59.52 ms | 0.552 ms | 0.516 ms |  59.61 ms |
|             ArrayForArg |  58.74 ms | 0.160 ms | 0.150 ms |  58.72 ms |
|           ConstArrayFor |  53.17 ms | 0.211 ms | 0.187 ms |  53.11 ms |
|            ArrayForeach |  57.54 ms | 0.479 ms | 0.448 ms |  57.50 ms |
|                 ListFor |  53.74 ms | 0.259 ms | 0.243 ms |  53.73 ms |
|             ListForeach | 100.57 ms | 0.760 ms | 0.711 ms | 100.71 ms |
|               SpanArray |  43.20 ms | 0.348 ms | 0.326 ms |  43.20 ms |
|                SpanList |  43.55 ms | 0.854 ms | 1.329 ms |  42.94 ms |
|                PtrArray |  42.03 ms | 0.833 ms | 0.959 ms |  42.33 ms |
|         IteratorForeach | 335.63 ms | 0.763 ms | 0.637 ms | 335.36 ms |
| IEnumerableArrayForeach | 363.98 ms | 1.358 ms | 1.204 ms | 363.33 ms |
|  IEnumerableListForeach | 456.95 ms | 1.193 ms | 1.116 ms | 456.84 ms |
|           IListArrayFor | 385.10 ms | 1.806 ms | 1.690 ms | 384.55 ms |
|       IListArrayForeach | 363.89 ms | 0.604 ms | 0.472 ms | 363.96 ms |
|            IListListFor |  53.51 ms | 0.331 ms | 0.309 ms |  53.55 ms |
|        IListListForeach | 456.60 ms | 1.099 ms | 0.974 ms | 456.08 ms |
|            ArrayIndexof |  30.07 ms | 0.583 ms | 0.818 ms |  29.63 ms |
|            ListContains |  29.46 ms | 0.183 ms | 0.180 ms |  29.42 ms |
|               ArrayLinq |  29.51 ms | 0.264 ms | 0.206 ms |  29.47 ms |
|                ListLinq |  29.42 ms | 0.174 ms | 0.155 ms |  29.41 ms |

</details>

## 結果の概観

速度を比較すると、
1. Linq や `IndexOf` などの「検索」に特化したメソッドを使用するケース
2. `Span` (配列やリストより有意に高速といえる)
3. 配列 `int[]`。ただし、ループの実装によりややパフォーマンスに差がある。
4. `List<T>` 。配列よりは低速だが、それでもインターフェイスを介した場合よりはかなり高速。
5. インターフェイスを介する場合。`for` を活用できる `IList<T>` の使用は `List<T>` に対しては有効だが配列に対しては効果がない。

それぞれの理由についてはこれから個別に取り上げて順に説明していきます。

## 配列とパフォーマンス

まず、配列は一般的なコレクションとしては最も高速であることがわかります。
では、なぜ配列は高速なのでしょうか。配列とパフォーマンスの関係を追ってみましょう。

### 配列と境界値チェックの挿入

C# の配列はメモリ安全性を確保したつくりになっています。ここでいうメモリ安全性とは以下の二点に代表されるでしょう。

- GCにより確実に解放される。`free()` とかしなくてよい。もちろん忘れることもない。
- 未初期化領域への読み書きができない。1 でもインデックスが配列長を超えた操作を実行しようとした時点でプログラムが停止する。

これらは C# では当たり前のことですが、これらは原始的には当たり前ではないわけです。
したがって、これらは C# および .NETランタイムが頑張って保証しています。そして、そのコストはタダではないわけです。

特に、後者の配列として確保した領域をはみ出さないという特性が問題になります。
要は、`array[array.Length]` とかやると一瞬で `IndexOutOfRangeException` が飛んできて怒られるという仕組みの裏側なわけですが、
これは配列の読み書きの操作をするたびに、操作しようとしているインデックスが配列長を超えていないかをチェックし、超えていれば例外をスローするコードを、ランタイムが暗黙的に挿入することにより実現されており、配列への操作のパフォーマンスにクリティカルに影響します。本記事ではこの振る舞いを「境界値チェック」と呼ぶことにしましょう。

ところが、今回のベンチマークのような、一般的な配列へのループ操作が配列の範囲外を操作する可能性がないことは明らかでしょう。
ループ条件が `i = 0` から `i < _array.Length` である以上、範囲外になる余地はありません。

```cs
public bool ArrayFor()
{
    var _array = array;
    for (var i = 0; i < _array.Length; i++)
    {
        if (_array[i] == target)
        {
            return true;
        }
    }
    return false;
}
```

この事実を、ランタイムは多少考慮してくれる作りになっています。すなわち、ランタイムが境界外操作のリスクが絶対にないと判断した場合、境界値チェックをするコードの挿入をキャンセルしてくれます。

### 境界値チェックの最適化が入るケース・入らないケース

配列へのループ処理を最適化する場合、この境界値チェックが入らないようにランタイムが最適化してくれる書き方をすることが有効なわけですが、
この最適化はコードを局所的にしか見ておらず、大局的にフローを追って最適化とかはしてくれません。
また、ランタイムレベルで暗黙的に挿入されるため、目に触れることが少なく、最適化されているかどうかがわかりにくいです。
本記事では、ベンチマークおよび逆アセンブルによりこの境界値チェックの最適化の挙動に関して研究します。

今回検証したループの回し方は以下の 5 種です。
コード・結果は最初に載せたものの再掲になります。ベンチマーク中で、`array` は、クラスの静的フィールドであるテストデータです。

```cs
public class Benchmark
{
    private const int testSize = 100_000_000;
    private const int target = testSize - 1;
    private static readonly int[] array;
}
```

#### 1. 普通の `for`

ローカル変数を普通にループするものです。基準。

```cs
public bool ArrayFor()
{
    int[] _array = array;
    for (var i = 0; i < _array.Length; i++)
    {
        if (_array[i] == target)
        {
            return true;
        }
    }
    return false;
}
```
#### 2. フィールドを直接 `for`

フィールドを直接ループ処理します。ネタバレですが遅いです。

```cs
public bool ArrayForField()
{
    for (var i = 0; i < array.Length; i++)
    {
        if (array[i] == target)
        {
            return true;
        }
    }
    return false;
}
```

#### 3. ループを関数に切り出し

ループ処理を関数に切り出したものです。これだけで結果が変わるのが難しいところ。

```cs
public bool ArrayForArg()
{
    return ArrayForInternal(array);
}

private bool ArrayForInternal(int[] _array)
{
    for (var i = 0; i < _array.Length; i++)
    {
        if (_array[i] == target)
        {
            return true;
        }
    }
    return false;
}
```

#### 4. ループ条件を定数に

`Length` プロパティをみる代わりに定数を使います。遅いです。

```cs
public bool ConstArrayFor()
{
    for (var i = 0; i < testSize; i++)
    {
        if (array[i] == target)
        {
            return true;
        }
    }
    return false;
}
```

#### 5. `foreach`

`foreach` を使ってみます。

```cs
public bool ArrayForeach()
{
    foreach (var n in array)
    {
        if (n == target)
        {
            return true;
        }
    }
    return false;
}
```

ベンチマークには誤差もあるため、わかりにくいかもしれませんが、結論からいうと今回のベンチマークでは

- ArrayFor
- ArrayForArg
- ArrayForeach

が最適化されているケースです。一方

- ArrayForField
- ConstArrayFor

が最適化されておらず、境界値チェックが入っています。

結果は N = 1M の場合が見やすいでしょうか。該当部分を取り出すと以下のようになります。

|                  Method |       Mean |    Error |   StdDev |
|------------------------ |-----------:|---------:|---------:|
|                ArrayFor |   530.3 μs |  7.36 μs |  6.89 μs |
|           ArrayForField |   543.6 μs |  8.33 μs |  7.79 μs |
|             ArrayForArg |   524.3 μs |  2.52 μs |  2.24 μs |
|           ConstArrayFor |   547.2 μs |  2.47 μs |  2.06 μs |
|            ArrayForeach |   530.3 μs |  7.80 μs |  7.29 μs |

|                  Method |       Mean |    Error |   StdDev |
|------------------------ |-----------:|---------:|---------:|
|                ArrayFor |   475.6 μs |  6.07 μs |  5.68 μs |
|           ArrayForField |   508.9 μs |  6.57 μs |  5.83 μs |
|             ArrayForArg |   470.9 μs |  6.06 μs |  5.67 μs |
|           ConstArrayFor |   498.0 μs |  4.99 μs |  4.67 μs |
|            ArrayForeach |   455.4 μs |  8.40 μs |  6.56 μs |

差がついているのがわかるでしょうか。

### マルチスレッド安全性

まず、最適化の有無を分けたのがマルチスレッド安全性です。
クラスの静的フィールドとして持っている配列をそのままループで処理した `ArrayForField` では、マルチスレッド安全性が担保できません。
クラスの静的フィールドは、別のスレッドから書き換えることができるためです。ループ処理中により長さの短い別の配列にフィールドが書き換えられると
範囲外の読み取りが発生することになり、この可能性を排除することはできません。したがって、境界値チェックを省略できないのです。
一方、ローカル変数に一旦代入したケースや関数の引数としたケースでは、これらはスレッド内で閉じているため安全であり、最適化がなされています。

実際、このようになっていることはアセンブラからわかります。
理解したい人のために読解のコツを書いておくと、まず先にループ本体をつかむことです。

```nasm:Benchmark.ArrayFor ()
L0000    sub    rsp, 0x28
L0004    mov    rcx, 0x7ff847e3cea8
L000e    mov    edx, 1
L0013    call    0x00007ff8a709dae0
L0018    mov    rax, [rax]
L001b    xor    edx, edx
L001d    mov    ecx, [rax+8]
L0020    test    ecx, ecx
L0022    jle    short L0038
L0024    movsxd    r8, edx
L0027    cmp    dword ptr [rax+r8*4+0x10], 0xf423f
L0030    je    short L003f
L0032    inc    edx
L0034    cmp    ecx, edx
L0036    jg    short L0024
L0038    xor    eax, eax
L003a    add    rsp, 0x28
L003e    ret    
L003f    mov    eax, 1
L0044    add    rsp, 0x28
L0048    ret    
```

```nasm:Benchmark.ArrayForField ()
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]
L001e    cmp    dword ptr [rdx+8], 0
L0022    jle    short L0043
L0024    mov    rdx, [rax]
L0027    cmp    esi, [rdx+8]
L002a    jae    short L0056
L002c    movsxd    rcx, esi
L002f    cmp    dword ptr [rdx+rcx*4+0x10], 0xf423f
L0037    je    short L004b
L0039    inc    esi
L003b    mov    rdx, [rax]
L003e    cmp    [rdx+8], esi
L0041    jg    short L0024
L0043    xor    eax, eax
L0045    add    rsp, 0x20
L0049    pop    rsi
L004a    ret    
L004b    mov    eax, 1
L0050    add    rsp, 0x20
L0054    pop    rsi
L0055    ret    
L0056    call    0x00007ff8a709f120
L005b    int3    
```

後者では、L0024 ~ L002a の `jae` (~以上でジャンプ) で、インデックスが配列の長さ以上のときに制御を飛ばし、例外をスローする処理を `call` で呼び出しています。
これに相当する命令は前者の最適化が入ったアセンブラではないことがわかります。
わずか 3 命令ではありますが、これはループ内部に入っているため、そもそもループの中身が短い今回のケースではまぁまぁパフォーマンスに響きます。

また、ループ処理を関数に切り出した場合の、切り出した関数側を見てみましょう。
同様に最適化がかかっていることがわかります。このアセンブラは短いのでなんとなく読めるのではないでしょか。

```nasm:Benchmark.ArrayForInternal (Int32[])
L0000    xor    eax, eax
L0002    mov    ecx, [rdx+8]
L0005    test    ecx, ecx
L0007    jle    short L001d
L0009    movsxd    r8, eax
L000c    cmp    dword ptr [rdx+r8*4+0x10], 0xf423f
L0015    je    short L0020
L0017    inc    eax
L0019    cmp    ecx, eax
L001b    jg    short L0009
L001d    xor    eax, eax
L001f    ret    
L0020    mov    eax, 1
L0025    ret    
```

### `Length` 以外を条件にしない

この最適化は、愚直にループ条件が配列の `Length` プロパティかどうかを見ていると思われます。
そのため、ループ条件として整数リテラル(定数)などを使用すると最適化が入りません。
定数を使用するなど、わかりにくい書き方をすると最適化を阻害します。

```nasm:Benchmark.ConstArrayFor ()
L0000    push    rsi
L0001    sub    rsp, 0x20
L0005    xor    esi, esi
L0007    mov    rcx, 0x7ff847e3cea8
L0011    mov    edx, 1
L0016    call    0x00007ff8a709dae0
L001b    mov    rax, [rax]
L001e    cmp    esi, [rax+8]
L0021    jae    short L004d
L0023    movsxd    rdx, esi
L0026    cmp    dword ptr [rax+rdx*4+0x10], 0xf423f
L002e    je    short L0042
L0030    inc    esi
L0032    cmp    esi, 0xf4240
L0038    jl    short L0007
L003a    xor    eax, eax
L003c    add    rsp, 0x20
L0040    pop    rsi
L0041    ret    
L0042    mov    eax, 1
L0047    add    rsp, 0x20
L004b    pop    rsi
L004c    ret    
L004d    call    0x00007ff8a709f120
L0052    int3    
```

### 配列では `foreach` は `for` 相当に最適化

`foreach` は、C# 言語仕様的には、`GetEnumerator()` を呼び出して、`MoveNext()` ~ `Current` 参照、というパターンになるわけですが、これは遅いので C# コンパイラは、配列に対しては特殊扱いで `for` 相当のコードを生成します。そのため、今回のケースでは中間言語の時点で同じアセンブリです。

```cil:Benchmark.ArrayFor ()
IL_0000	ldsfld	Benchmark.array
IL_0005	stloc.0	   // _array
IL_0006	ldc.i4.0	
IL_0007	stloc.1	   // i
IL_0008	br.s	IL_001A
IL_000A	ldloc.0	   // _array
IL_000B	ldloc.1	   // i
IL_000C	ldelem.i4	
IL_000D	ldc.i4	FF E0 F5 05  // 99999999
IL_0012	bne.un.s	IL_0016
IL_0014	ldc.i4.1	
IL_0015	ret	
IL_0016	ldloc.1	   // i
IL_0017	ldc.i4.1	
IL_0018	add	
IL_0019	stloc.1	   // i
IL_001A	ldloc.1	   // i
IL_001B	ldloc.0	   // _array
IL_001C	ldlen	
IL_001D	conv.i4	
IL_001E	blt.s	IL_000A
IL_0020	ldc.i4.0	
IL_0021	ret	
```

```cil:Benchmark.ArrayForeach ()
IL_0000	ldsfld	Benchmark.array
IL_0005	stloc.0	
IL_0006	ldc.i4.0	
IL_0007	stloc.1	
IL_0008	br.s	IL_001A
IL_000A	ldloc.0	
IL_000B	ldloc.1	
IL_000C	ldelem.i4	
IL_000D	ldc.i4	FF E0 F5 05  // 99999999
IL_0012	bne.un.s	IL_0016
IL_0014	ldc.i4.1	
IL_0015	ret	
IL_0016	ldloc.1	
IL_0017	ldc.i4.1	
IL_0018	add	
IL_0019	stloc.1	
IL_001A	ldloc.1	
IL_001B	ldloc.0	
IL_001C	ldlen	
IL_001D	conv.i4	
IL_001E	blt.s	IL_000A
IL_0020	ldc.i4.0	
IL_0021	ret	
```

同じ中間言語コードなのですから、あえて掲載はしませんが生成されるx64アセンブリも同じです。
マルチスレッド安全性やループ条件で最適化されない可能性を考慮しなくてよい分だけ、`foreach` の方が楽でしょうか。

### 配列と中間言語(IL)専用命令
配列は、生成、読み取り、書き込み、長さの取得、それぞれに中間言語レベルでの専用命令が割り振られています。

| 操作 | 命令 |
|:-:|:-:|
| 生成 | `newarr` |
| 読み取り | `ldelem` / `ldelema` |
| 書き込み | `stelem` |
| 長さの取得 | `ldlen` |

実際に、今回のベンチマークコードの一部を見てみましょう。~~中間言語にもシンタックスハイライトがほしい~~

```cil
Benchmark.ArrayFor ()
IL_0000	ldsfld	Benchmark.array
IL_0005	stloc.0	   // _array
IL_0006	ldc.i4.0	
IL_0007	stloc.1	   // i
IL_0008	br.s	IL_001A
IL_000A	ldloc.0	   // _array
IL_000B	ldloc.1	   // i
IL_000C	ldelem.i4	
IL_000D	ldc.i4	FF E0 F5 05  // 99999999
IL_0012	bne.un.s	IL_0016
IL_0014	ldc.i4.1	
IL_0015	ret	
IL_0016	ldloc.1	   // i
IL_0017	ldc.i4.1	
IL_0018	add	
IL_0019	stloc.1	   // i
IL_001A	ldloc.1	   // i
IL_001B	ldloc.0	   // _array
IL_001C	ldlen	
IL_001D	conv.i4	
IL_001E	blt.s	IL_000A
IL_0020	ldc.i4.0	
IL_0021	ret	
```

先程紹介したような、専用命令が使用されていることがわかります。

### 配列型の再現実験

中間言語レベルでの専用命令があれば高速、という話は結構聞く話なのではないでしょうか。
自分もずっとそう思っていたのですが、今回せっかくなので検証してみようと思います。
ということで、配列型を自作してみましょう。今回の検証環境は64bitなので、実装は64bit決め打ちになっています。
配列のメモリレイアウトに関しては、[以前に書いた記事](https://qiita.com/Kujiro/items/e1998b14176419b3ad1a) をあわせて見ていただけると理解できると思います(宣伝)。

```cs
public unsafe sealed class MyArray<T> where T : unmanaged
{
    private readonly void* ptr;

    private readonly int headerSize = sizeof(nint) + sizeof(nint);

    public MyArray(int length)
    {
        ptr = Marshal.AllocHGlobal(headerSize + length * sizeof(T)).ToPointer();
        ((nint*)ptr)[0] = (nint)0xDEADBEAF;
        ((nint*)ptr)[1] = length;
    }

    public T this[int index]
    {
        get => (uint)index < Length ? ((T*)((nint)ptr + 16))[index] : ThrowIndexOutOfRange();
        set => _ = (uint)index < Length ? ((T*)((nint)ptr + 16))[index] = value : ThrowIndexOutOfRange();
    }

    private static T ThrowIndexOutOfRange()
    {
        throw new IndexOutOfRangeException();
    }

    public T GetUnsafe(int index)
    {
        return ((T*)((nint)ptr + 16))[index];
    }

    public void SetUnsafe(int index, T value)
    {
        ((T*)((nint)ptr + 16))[index] = value;
    }

    public int Length
    {
        get => *(int*)((nint)ptr + 8);
    }
}
```

簡単に実装を説明します。
`Marshal.AllocHGlobal` (要は `malloc` ) でヒープを確保し、その上に配列を再現します。
配列の先頭には、仮想関数テーブルのポインタと長さが入ります。今回は、仮想関数テーブルの部分は適当な値を入れておきます。
次に配列の要素数が入ります。それに続いて書く要素が並びます。
なお、この `MyArray<T>` クラスのインスタンス自体がポインタですので、本当の配列と比較して間接参照が1段階余計に入ります。
インデクサーによるアクセスでは境界値チェックを掛けています。最適化で境界値チェックがない状況は `GetUnsafe` 関数で再現できます。

### 結果

`MyArraySafe` は、境界値チェックが入っているテストケースで、`ConstArrayFor` 相当です。
`MyArrayUnsafe` は、境界値チェックを消したテストケースで、`ArrayFor` 相当です。

#### N=1M

``` 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
```
|        Method |     Mean |   Error |  StdDev |
|-------------- |---------:|--------:|--------:|
|      ArrayFor | 532.6 μs | 7.21 μs | 6.02 μs |
| ConstArrayFor | 547.9 μs | 3.04 μs | 2.54 μs |
|   MyArraySafe | 547.9 μs | 3.49 μs | 2.92 μs |
| MyArrayUnsafe | 526.0 μs | 1.44 μs | 1.28 μs |


``` ini
BenchmarkDotNet=v0.13.1, OS=Windows 10.0.22621
AMD Ryzen 7 4700U with Radeon Graphics, 1 CPU, 8 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
```
|        Method |     Mean |   Error |  StdDev |
|-------------- |---------:|--------:|--------:|
|      ArrayFor | 471.3 μs | 8.96 μs | 8.80 μs |
| ConstArrayFor | 499.6 μs | 5.24 μs | 4.91 μs |
|   MyArraySafe | 492.1 μs | 3.85 μs | 3.41 μs |
| MyArrayUnsafe | 456.1 μs | 7.52 μs | 7.04 μs |


#### N=100M

``` 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
```
|        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 |



``` ini
BenchmarkDotNet=v0.13.1, OS=Windows 10.0.22621
AMD Ryzen 7 4700U with Radeon Graphics, 1 CPU, 8 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
```

|        Method |     Mean |    Error |   StdDev |
|-------------- |---------:|---------:|---------:|
|      ArrayFor | 56.82 ms | 1.122 ms | 1.049 ms |
| ConstArrayFor | 53.84 ms | 1.001 ms | 1.028 ms |
|   MyArraySafe | 53.26 ms | 0.931 ms | 0.871 ms |
| MyArrayUnsafe | 51.00 ms | 0.650 ms | 0.608 ms |

### 専用命令はパフォーマンスに貢献するか

やはり多少誤差によるばらつきが発生していますが、以上の結果を見る限り、自作配列型と本当の配列型でほぼ同じ性能であることがわかります。ところが、

```cil:Benchmark2.MyArraySafe ()
IL_0000	ldc.i4.0	
IL_0001	stloc.0	   // i
IL_0002	br.s	IL_001C
IL_0004	ldsfld	Benchmark2.array2
IL_0009	ldloc.0	   // i
IL_000A	callvirt	MyArray <Int32>.get_Item (Int32)
IL_000F	ldc.i4	3F 42 0F 00  // 999999
IL_0014	bne.un.s	IL_0018
IL_0016	ldc.i4.1	
IL_0017	ret	
IL_0018	ldloc.0	   // i
IL_0019	ldc.i4.1	
IL_001A	add	
IL_001B	stloc.0	   // i
IL_001C	ldloc.0	   // i
IL_001D	ldsfld	Benchmark2.array2
IL_0022	callvirt	MyArray <Int32>.get_Length ()
IL_0027	blt.s	IL_0004
IL_0029	ldc.i4.0	
IL_002A	ret	
```

```cil:Benchmark2.MyArrayUnsafe ()
IL_0000	ldc.i4.0	
IL_0001	stloc.0	   // i
IL_0002	br.s	IL_001C
IL_0004	ldsfld	Benchmark2.array2
IL_0009	ldloc.0	   // i
IL_000A	callvirt	MyArray <Int32>.GetUnsafe (Int32)
IL_000F	ldc.i4	3F 42 0F 00  // 999999
IL_0014	bne.un.s	IL_0018
IL_0016	ldc.i4.1	
IL_0017	ret	
IL_0018	ldloc.0	   // i
IL_0019	ldc.i4.1	
IL_001A	add	
IL_001B	stloc.0	   // i
IL_001C	ldloc.0	   // i
IL_001D	ldsfld	Benchmark2.array2
IL_0022	callvirt	MyArray <Int32>.get_Length ()
IL_0027	blt.s	IL_0004
IL_0029	ldc.i4.0	
IL_002A	ret	
```

と、自作配列型では専用命令は全く使用されておらず、すべて `callvirt` 命令による普通の仮想関数呼び出しにコンパイルされています。

つまり、中間言語レベルでの専用命令は、必ずしもパフォーマンスに貢献はしません。
x64アセンブリをみると

```nasm:Benchmark2.MyArraySafe ()
L0000	push	ebp
L0001	mov	ebp, esp
L0003	push	edi
L0004	push	esi
L0005	push	ebx
L0006	xor	esi, esi
L0008	mov	ecx, 0xdfeca20
L000d	mov	edx, 2
L0012	call	0x04975760
L0017	mov	edx, [eax+8]
L001a	mov	edx, [edx+4]
L001d	cmp	dword ptr [edx+8], 0
L0021	jle	short L0051
L0023	mov	edx, [eax+8]
L0026	xor	ecx, ecx
L0028	mov	edx, [edx+4]
L002b	mov	edi, [edx+8]
L002e	mov	ebx, edi
L0030	sar	ebx, 0x1f
L0033	cmp	esi, edi
L0035	sbb	ecx, ebx
L0037	jge	short L0062
L0039	mov	edx, [edx+esi*4+0x10]
L003d	cmp	edx, 0xf423f
L0043	je	short L0058
L0045	inc	esi
L0046	mov	edx, [eax+8]
L0049	mov	edx, [edx+4]
L004c	cmp	esi, [edx+8]
L004f	jl	short L0023
L0051	xor	eax, eax
L0053	pop	ebx
L0054	pop	esi
L0055	pop	edi
L0056	pop	ebp
L0057	ret	
L0058	mov	eax, 1
L005d	pop	ebx
L005e	pop	esi
L005f	pop	edi
L0060	pop	ebp
L0061	ret	
L0062	call	dword ptr [0xdfedcec]
L0068	int3	
```

```nasm:Benchmark2.MyArrayUnsafe ()
L0000	push	ebp
L0001	mov	ebp, esp
L0003	push	esi
L0004	xor	esi, esi
L0006	mov	ecx, 0xdfeca20
L000b	mov	edx, 2
L0010	call	0x04975760
L0015	mov	edx, [eax+8]
L0018	mov	edx, [edx+4]
L001b	cmp	dword ptr [edx+8], 0
L001f	jle	short L003d
L0021	mov	edx, [eax+8]
L0024	mov	edx, [edx+4]
L0027	cmp	dword ptr [edx+esi*4+0x10], 0xf423f
L002f	je	short L0042
L0031	inc	esi
L0032	mov	edx, [eax+8]
L0035	mov	edx, [edx+4]
L0038	cmp	esi, [edx+8]
L003b	jl	short L0021
L003d	xor	eax, eax
L003f	pop	esi
L0040	pop	ebp
L0041	ret	
L0042	mov	eax, 1
L0047	pop	esi
L0048	pop	ebp
L0049	ret	
```

となっており、ループ本体に関しては先程みた `for` でのアセンブリと非常に近いことがわかるでしょう。
間接参照が 1 回多い点が、`mov` 命令が 2 回連続するところに影響している以外の違いはほとんどないです。
自作配列型も、(そうなるよう工夫しているので)完全にインライン化が入り、関数呼び出しなどは消去されるため、結局中間言語レベルで専用命令だろうが関数呼び出しだろうが関係なくなってしまいます。

ちなみに、インライン化されるために自作配列型では
- 例外を直接スローしない
- 継承させない

という最適化をしています。また、境界値チェックもちょっとしたトリックを活用して最適化しています。
ここまでやれば配列と同じパフォーマンスが出せます。

結論として、配列が高速であるのは、中間言語レベルでの専用命令そのものの恩恵というより
- インライン化
- 境界値チェックの最適化

などが掛かり、かつ無駄がないシンプルな構造であることによるといえるでしょう。
このうち境界値チェックの最適化に関しては安全に模倣するのが難しいため、この恩恵がいわゆる「専用命令によるアドバンテージ」の正体であると思われます。

## まとめ

話が長くなり、エディタが重くなってきたのでこの辺で一旦まとめて次回へ続くことにしましょう。

- 配列は `List<T>` や interface扱いより早い
  - 境界値チェックが消えるかどうかが大事
    - マルチスレッド安全性やループ条件による
  - `foreach` は `for` 相当に展開
    - もちろん境界値チェックは最適化される、確実
- 配列に専用命令があるから早いっていうことではない
  - 自作の配列型を作ると同じパフォーマンスになる 

## 次回

https://qiita.com/Kujiro/items/9569e91b942bcf9d528b