はじめに

上記ブログで示された最適化とはどのようなものかというと、

for (int i = 0; i < list.Count; i++)
    ...

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

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

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

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

JNS: Jump if Not Signed (Positive or Zero)

逆ループは意外と面倒

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

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 文の外に漏れてしまう

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

それが 👇 コチラ。

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

ポイント

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

動作確認

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

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）

.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）

🔰 そもそも論 🔰

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

その他の箇条書き

配列やスパンは特殊対応が行われていますが、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 文の初期化パート以外はループと同じ回数評価されます。

✅ 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 を使うのが正解です。

加えて、コレクションへの部分アクセスは for (int i = start; i < end; i++) ではなく、

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 で使えます。

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

ベンチマークコード

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;
}

おわりに

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

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

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

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

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

--

それでは良いお年を。

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