噂のループ最適化手法とベンチマーク／スニペット

.NET 9 のリリースブログで示されたループ最適化についての確認と Visual Studio 向けスニペットテンプレート。

https://devblogs.microsoft.com/dotnet/performance-improvements-in-net-9/#loops


--

- [はじめに](#はじめに)
- [逆ループは意外と面倒](#逆ループは意外と面倒)
- [面倒に対処したスニペット](#面倒に対処したスニペット)
    - [動作確認](#動作確認)
- [ベンチマーク](#ベンチマーク)
    - [.NET Standard 2.1（Unity）](#net-standard-21unity)
    - [.NET 8](#net-8)
    - [.NET 9](#net-9)
- [Visual Studio 用スニペット](#visual-studio-用スニペット)
- [ベンチマークコード](#ベンチマークコード)
- [おわりに](#おわりに)




# はじめに

上記ブログで示された最適化とはどのようなものかというと、
```cs
for (int i = 0; i < list.Count; i++)
    ...

for (int i = 0; i < 100; i++)
    ...
```

のような一般的な for ループを、

```cs
int i = 0;
for (int d = list.Count - 1; d >= 0; d--)
{
    i++;
}
```

といった具合に、ループ終了判定の条件式を専用命令<sup>※１</sup>がある `0` との比較に変形しようというものです。

> `JNS`: Jump if Not Signed (Positive or Zero)





# 逆ループは意外と面倒

実践するにはいくつか注意するべき点があります。

```cs
int i = -1;  // インクリメントをループ冒頭に持ってきたいときは -1 スタート
for (int r = length - 1; r >= 0; r--)
    i++;

for (int r = length - 1; r >= 0; r--)
{
    i++;  // ２回目まわすかー、でコピペする場合は i = -1 も持ってこないとダメだが実行しないとエラーが出ない

    // コピペでネストの場合も気を付けないとエンバグ、変数名を決めるのが面倒、etc.
    for (int nest = other - 1; nest >= 0; nest--)
    {
        i++;
    }
}

i  = 0;  // 変数スコープが for 文の外に漏れてしまう
```


# 面倒に対処したスニペット

それが 👇 コチラ。

```cs
for (int _______ = list.Count - 1, i = 0; _______ >= 0; _______--, i++) //perf
{
    Console.WriteLine($"{list[i]}, {_______}");
}
```

<p><details lang="ja" --open><summary>ポイント</summary>

- 初期化子が `for` 文に含まれているので変数スコープが適切
    - `i++` が不要（ではないが for 文内にあるので邪魔にならない）
    - 逆ループのカウンタを間違って参照してしまうミスが起きづらい
- コピペでネストした場合に初期化子が含まれているので IDE 上でちゃんとエラーが出る
- 逆ループで最適化している（なんか変なことしている）というのがパッと見で分かる違和感のある字面
    - ホイールコロコロで斜め読みしていても「ん？ ん？？」となる悪目立ち具合
    - 一方で行末にインクリメント変数が配置されているので `i` `j` または別の名前なのかを迅速に確認可能
- 新しい .NET 環境では不要な最適化なので、後々 `_______`（アンダースコア７連）で全文検索して修正できる

<!------- End of Details JA Tag -------></details></p>



## 動作確認

実行環境： https://dotnetfiddle.net/

```cs
using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        var list = new List<char>(){ 'a', 'b', 'c', 'd', 'e' };

        for (int _______ = list.Count - 1, i = 0; _______ >= 0; _______--, i++) //perf
        {
            Console.WriteLine($"{list[i]}, {_______}");
        }

        Console.WriteLine();

        // 通常の for ループと同じ変数スコープなので i を複数回使える
        for (int _______ = list.Count - 1, i = 0; _______ >= 0; _______--, i++) //perf
        {
            Console.WriteLine($"{list[i]}, {_______}");
        }
    }
}
```



# ベンチマーク

Unity なら逆ループをやる価値はありそうです。リストへのアクセスが下手な配列アクセスよりも速くなるケースもあります。要素数 1,000 万で数ミリ秒なので万単位のリストを毎フレーム走査しているなら気にしたほうが良いでしょう。（60fps = 16.67millisecs）

https://unity.com/ja/blog/engine-platform/10000-update-calls


.NET 8 ではむしろマイナスなのですべてコンパイラーに任せましょう。そして .NET 9 だと「遅くはならない」という感じです。不思議ですね。

- ⛔ 新しめの .NET 環境なら `List<T>` を `CollectionsMarshal` して `Span<T>` 経由でのアクセスが正解です。
    - https://learn.microsoft.com/ja-jp/dotnet/api/system.runtime.interopservices.collectionsmarshal.asspan
    - 逆ループなんてやると逆に遅くなるベンチマーク結果があります。
    - スパンを使った式変形も有効です。



## .NET Standard 2.1（Unity）

:::note info

🔰 そもそも論 🔰

配列やリスト、その他のコレクションで共通のループ最適化手法として「**クラスのフィールドやプロパティーに都度アクセスしない**」というモノがあり、そっちの方がよっぽど効果があります。

<p><details lang="ja" --open><summary>その他の箇条書き</summary>

- 配列やスパンは特殊対応が行われていますが、`List<T>` 含むそれ以外のコレクション型の場合は `.Count` というプロパティーへのアクセスが最もデカいオーバーヘッドです。
- 逆ループよりも `var count = list.Count;` して `for (int i = 0; i < count; i++)` する方が遥かにパフォーマンスへのインパクトがあります。
    - 逆ループ化すると `.Count` へのアクセスが初期化子の１回のみになり、結果的に上記と同等の最適化が行われることになります。
    - 変数と定数の比較に変形した結果として得られる CPU 命令の最適化という、逆ループそのものによる効果は微々たるものです。
- 添え字アクセスもオーバーヘッドです。
    - インデクサーの実態はプロパティーです。
        - ループ冒頭で `var item = list[i];` してローカル変数経由でアクセスする手癖をつけましょう。
        - `List<T>` の場合、アクセスの度にインデックスの境界チェックが入ります。
- `list.ElementAt(i).DoIt()` を何度も実行することには抵抗を感じると思いますが、`list[i].DoIt()` は何度も呼びだしても大丈夫そうな感じがしますね。
    - しかしプロパティーの実態はメソッドなので、上記ふたつは（ほぼ）同じことをやっています。
        - 処理が複雑でコストがかかる場合はプロパティーではなく `Get**` にしたほうが利用者にとって分かりやすく親切ですが、面倒でついついプロパティーに直書きすることも多いです。
        - 歴史的経緯から今更 API を変えられないという事情も場合によってはあるでしょう。
        - 配列やスパン `Span<T>` `ReadOnlySpan<T>` はまた別の話です。
    - なのでインデクサーもプロパティーもループ内ではローカル変数に代入してアクセスしましょう。
- `for` 文の初期化パート以外はループと同じ回数評価されます。

<!------- End of Details JA Tag -------></details></p>

:::


- ✅ Unity（.NET Standard 2.1）では逆ループによる最適化が期待できます。
    - が！ リストの場合は単純に `int count = list.Count;` とキャッシュするだけで十二分に速くなります。
    - 次いでインパクトがあるのがフィールドアクセス回数の削減です。`var list = this.list;`
    - 逆ループ迄やると配列と同等またはそれ以上の性能を発揮します。
- `[LongRunJob]` で計測
- **LocalVar**: クラスのフィールド参照をメソッド冒頭でローカル変数に代入
- **ListUsual**: `for (int i = 0; i < this.list.Count; i++)`
- **ListCountCache**: `int count = this.list.Count;` してから `for (int i = 0; i < count; i++)`
- **Downward**: 逆ループ


| **Array**             | Mean     | Ratio |
|---------------------- |---------:|------:|
| ArrayLength           | 0.0048 s |  1.00 |
| ArrayLengthLocalVar   | 0.0047 s |  0.99 |
| ArrayDownwardLocalVar | 0.0044 s |  0.93 |
| ArrayAsSpan           | 0.0046 s |  0.97 |
| **List**              |
| ListUsual             | 0.0079 s |  1.66 |
| ListCountCache        | 0.0051 s |  1.08 |
| ListDownwardCounting  | 0.0050 s |  1.06 |
| ListDownwardLocalVar  | 0.0045 s |  0.95 |


## .NET 8

⛔ 新しめの環境では `CollectionsMarhsal` を使うのが正解です。

https://learn.microsoft.com/ja-jp/dotnet/api/system.runtime.interopservices.collectionsmarshal.asspan


加えて、コレクションへの部分アクセスは `for (int i = start; i < end; i++)` ではなく、
```cs
var span = array.AsSpan(start, end - start);
for (int i = 0; i < span.Length; i++)
{
    var x = span[i];
}
```

のように `[start..end]` を `[0...Length]` に変形するのが正解です。境界チェックが不要になり C# コンパイラーによって内部処理が最適化されます。

> `ArrayDownwardLocalVar` のローカル変数化による改善を排除すると大体 x1.15 ぐらいになるでしょうか。境界チェック排除の効果は大きいです。


| **Array**             | Mean     | Ratio |
|---------------------- |---------:|------:|
| ArrayLength           | 0.0038 s |  1.00 |
| ArrayLengthLocalVar   | 0.0031 s |  0.81 |
| ArrayDownwardLocalVar | 0.0036 s |  0.96 |
| ArrayAsSpan           | 0.0031 s |  0.81 |
| **List**              |
| ListUsual             | 0.0046 s |  1.21 |
| ListCountCache        | 0.0045 s |  1.18 |
| ListDownwardCounting  | 0.0050 s |  1.32 |
| ListDownwardLocalVar  | 0.0044 s |  1.17 |


## .NET 9

⛔ 同上。リストは何やっても変わらなくなっていますね。


| **Array**             | Mean     | Ratio |
|---------------------- |---------:|------:|
| ArrayLength           | 0.0039 s |  1.00 |
| ArrayLengthLocalVar   | 0.0031 s |  0.79 |
| ArrayDownwardLocalVar | 0.0036 s |  0.91 |
| ArrayAsSpan           | 0.0030 s |  0.77 |
| **List**              |
| ListUsual             | 0.0044 s |  1.12 |
| ListCountCache        | 0.0045 s |  1.14 |
| ListDownwardCounting  | 0.0045 s |  1.14 |
| ListDownwardLocalVar  | 0.0043 s |  1.10 |





# Visual Studio 用スニペット

`forf` で使えます。

```xml
<CodeSnippet Format="1.0.0">
    <Header>
        <Title>Fast for-loop especially for List</Title>
        <Description>Optimizing CPU instructions</Description>
        <Shortcut>forf</Shortcut>
    </Header>
    <Snippet>
        <Code Language="CSharp" Kind="any" Delimiter="#">
            <![CDATA[for (int #end##decrement# = #collection#.Count - 1, #increment# = 0; #decrement# >= 0; #decrement#--, #increment#++) //perf
            {
            }]]>
        </Code>
        <Declarations>
            <Literal>
                <ID>increment</ID>
                <Default>i</Default>
            </Literal>
            <Literal>
                <ID>decrement</ID>
                <Default>_______</Default>
            </Literal>
            <Literal>
                <ID>collection</ID>
                <Default>do_not_use_for_array_or_span</Default>
            </Literal>
        </Declarations>
    </Snippet>
</CodeSnippet>
```





# ベンチマークコード

```cs
const int NUM_ITEMS = 10_000_000;

readonly int[] TheArray = new int[NUM_ITEMS];
readonly List<int> TheList = new (new int[NUM_ITEMS]);


[Benchmark(Baseline = true)]
public int ArrayLength()
{
    int result = 0;
    for (int i = 0; i < TheArray.Length; i++)
    {
        result += TheArray[i];
    }

    return result;
}

[Benchmark()]
public int ArrayLengthLocalVar()
{
    var array = TheArray;
    int result = 0;
    for (int i = 0; i < array.Length; i++)
    {
        result += array[i];
    }

    return result;
}

[Benchmark()]
public int ArrayDownwardLocalVar()
{
    var array = TheArray;
    int result = 0;
    for (int _______ = array.Length - 1, i = 0; _______ >= 0; _______--, i++) //perf
    {
        result += array[i];
    }

    return result;
}

[Benchmark()]
public int ArrayAsSpan()
{
    var span = TheArray.AsSpan();
    int result = 0;
    for (int i = 0; i < span.Length; i++)
    {
        result += span[i];
    }

    return result;
}

[Benchmark()]
public int ListUsual()
{
    int result = 0;
    for (int i = 0; i < TheList.Count; i++)
    {
        result += TheList[i];
    }

    return result;
}

[Benchmark()]
public int ListCountCache()
{
    int result = 0;
    int count = TheList.Count;
    for (int i = 0; i < count; i++)
    {
        result += TheList[i];
    }

    return result;
}

[Benchmark()]
public int ListDownwardCounting()
{
    int result = 0;
    for (int _______ = TheList.Count - 1, i = 0; _______ >= 0; _______--, i++) //perf
    {
        result += TheList[i];
    }

    return result;
}

[Benchmark()]
public int ListDownwardLocalVar()
{
    var list = TheList;
    int result = 0;
    for (int _______ = list.Count - 1, i = 0; _______ >= 0; _______--, i++) //perf
    {
        result += list[i];
    }

    return result;
}
```





# おわりに

逆ループよりもこっちのスニペットの方が実益があったかも。

```cs
var list = this.list;
for (int i = 0, count = list.Count; i < count; i++)  // for 文内で .Count をキャッシュ
{
    var item =  list[i];
    ...
}
```

やるならとことんまでという気もしますが、

```cs
string? line;
while ((line = reader.ReadLine()) != null)
{
    ...
}
```

程度には受け入れやすいコードです。


--

それでは良いお年を。

以上です。お疲れ様でした。