LoginSignup
2
2

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@sator_imaging(サトー™)

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

Last updated at Posted at 2024-12-26

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

--

はじめに

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

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 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)
{
    ...
}

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

--

それでは良いお年を。

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

2
2
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
2
2

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?