Unity (C#) の各演算の処理コストのまとめ

# はじめに
Unity (C#) の各種の演算や処理を、何回までならフレーム落ちせずに実行できるか、限界ラインを計測してまとめてみました。

# TL; DR (結果の早見表)
#### 60FPSの頻度で実行した際にフレーム落ちが発生しない限界の回数
| 処理 | 60FPSで処理可能な回数 | コード |
| :---: | ---: | --- |
| `for ループ`| 5,000,000 | `for (int i=0; i<loopNum; ++i)`  |
| `foreach ループ` (Array以外[^1]) | 1,000,000 | `foreach (int _ in loopObject);` |
| 割り算 | 2,000,000 | `_ = i / 123456;` |
| 関数呼び出し | 1,000,000 | `func.Invoke();`|
| 型判定 | 5,000,000 | `myList is List<int>;` |
| ダウンキャスト | 5,000,000 | `myList as List<int>;`|
| 構造体の生成 | 5,000,000 | `new MyStruct() { a = 5, b = 10 };`|
| 参照型 (クラス) の生成 | 200,000 | `new Object(); `|
| ボクシング | 200,000 | `object _ = Num;` (Numは `int` 型)|
| 内部で foreach (Array以外[^2]) | 200,000 | `foreach(var _ in myList) {}`|
| IEnumerable.Any() [^3] | 100,000 | `myList.Any();` |
| 大きなヒープ領域の確保 | 5,000 | `_ = new int[1000];` |

##### GameObjectに対する操作
| 処理 | 60FPSで処理可能な回数 | コード |
| :---: | ---: | --- |
| GameObject作成 (new) | 2,000 | `new GameObject();`  |
| Instantiate() | 2,000 | `Instantiate(emptyObject);`|
| Instantiate + Destory()| 1,000 | 上 + `Destroy(clonedObj);` |
| GetComponent | 50,000 | `myObject.GetComponent<MyBehaviour>();`|
| SendMessage | 20,000 | `myObject.SendMessage("SayHello");`|
| FindObjectOfType | 10,000 | `FindObjectOfType<GameObject>();`|


##### 0~999までの`List<int>`に対してLINQの操作を実行した結果
| 処理 | 60FPSで処理可能な回数 | コード |
| :---: | ---: | --- |
| Any | 100,000 | `myList.Any();`  |
| Where | 50,000 | `myList.Where(x => x > 500);`  |
| Select | 50,000 | `myList.Select(x => x * 500);`  |
| ToArray | 5,000 | `myList.ToArray();`  |
| ToList | 5,000 | `myList.ToList();`  |
| ToHashSet | 200 | `myList.ToHashSet();`  |
| ToLookup (key多め) | 20 | `myList.ToLookup(num => num, num => num * num);`  |
| ToLookup (key少なめ) | 100 | `myList.ToLookup(num => num%10, num => num * num);`  |
| GroupBy (group少なめ) | 100 | `myList.GroupBy(num => num%10);`  |

- こちらは「1eN, 2eN, 5eN, ...」の区切りで、 `55FPS` (1秒間に55回) 以上で処理できた**最大のフレーム内処理回数**を測定したものです
  - 言い換えると、`MonoBehaviour` の`Update()` 内で処理可能な限界数です
- 「forループ」「foreachループ」以外の項目は、forループ内で処理しているため、「forループ」の分の処理負荷[^4]を含みます。


[^1]: `Array`のみ内部でEnumeratorを利用しないため速いようです。それ以外は内部で `enumerator.MoveNext()` を呼び出してループするので、関数呼び出しの分コストがかかっているようです。
[^2]: `Array`のみオブジェクトの生成を回避できます。`List`や`IEnumerable`の場合はEnumeratorの生成コストがかかります。`List`のEnumeratorはstructなのですが、内部の後処理で`IDisposable`にキャストする際にボクシングするようです。
[^3]: LINQの呼び出しの際にEnumerator起因のアロケーションが1~2回 (Enumeratorの実装がstructならボクシングのため2回) 発生します。型が`Array`や`List`でも同様です。`Any`の場合は`array.Length > 0` や `list.Count > 0` に置き換えることで回避できます。
[^4]: `for`文の式に含まれるインクリメントや比較演算のコストです。


# 基礎知識
Unityのスクリプトは基本的にメインスレッドで実行されます。CPUのクロック数4GHzとすると、**1秒間に40億回** 、60FPSのゲームであれば**1フレーム当たり6666万回** のCPUレベルでの演算が行われます。演算の種類や処理系、コンパイラによる最適化の有無などによって、実際にCPUで行われる演算量は変わります。演算のコストをすごくざっくりと分類すると、以下のような3段階に分けられます。

| 処理 | 処理コストの大きさ | 補足 |
| --- | --- | --- |
| 比較・算術演算・型判定・値型の生成・関数呼び出し | 小 | リテラルの`string`型もこちら |
| クラス（参照型）の生成、ヒープ領域の確保 | 中 | **GC管理**のため重い |
| GameObjectの作成や破棄| 大 | **Unity管理**のため重い |

:::note info
C#では、「クラス（参照型）の生成」が暗黙的に行われるケースが非常に多いので、注意が必要です。
:::

# 処理落ちラインを計測する
## 計測方法
単純にコードの処理時間を計測するとGC負荷のコストなどが正確に評価できないので、反復処理を行った時のFPSの実測値を計測しました。
`Application.targetFrameRate` を `60` に設定した上で、実際に `200フレーム` 処理した際の平均FPSを、単位フレームあたりの処理回数を増加させながら計測しました。
各処理のループ回数は 20, 50, 100, 200, 500, ...etc と刻みながら増加させて計測し、15FPSを下回った時点でストップしています。また、`実測FPSが55以上だった最大のループ数`を処理落ちしないラインとして採用しています。

### 実行環境
Windows11, Unity Editorの Play Modeで実行。
Unityのバージョン: 2022.2.4f1 (Roslyn, C#9.0)
CPU: Intel® Core™ i9-9900KF (クロック数: 3.6GHz. 最大5.0GHz)

### コード
計測には以下のコードを使用しました。長いのでコードの詳細は割愛しますが、各テストの単位は以下のようなコードで作成しています。
関数呼び出しのオーバーヘッドを避けるため、計測する処理はfor文と共に書き下しています。
```C#
yield return new FPSProfileTask(loopNum, () =>
{
    for (int i = 0; i < loopNum; ++i)
    {
        _ = i / 123456; // ここで各項目の処理を行います（こちらは「割り算」の例）
    }
});
```

コードの全文は以下になります。

【追記 2023/03/25】
さすがにコードが長いので、Profiler の定義は別ファイルにして、Profilerの説明は以下の記事に分けました。

https://qiita.com/uminohiyoko/items/f9b6a4e09082ce09cb57


<details><summary>コード全文</summary><div>

``` FPSProfiler.cs
using System;
using System.Collections.Generic;
using System.Linq;
using UnityEngine;
using IMGUIProfiler;

public class FPSProfiler : MonoBehaviour
{
    private MultiProfilerHandler _profilerHandler;

    private void Start()
    {
        Application.targetFrameRate = 60; // 目標FPSを60に設定
        
        // // EXP1
        _profilerHandler = new MultiProfilerHandler(GetExp1Profilers(new double[] {5e4, 1e5, 2e5, 5e5, 1e6, 2e6, 5e6, 1e7, 2e7, 5e7}));
        
        // EXP2
        // _profilerHandler = new MultiProfilerHandler(GetExp2Profilers(new [] {1e2, 2e2, 5e2, 1e3, 2e3, 5e3, 1e4, 2e4, 5e4, 1e5, 2e5, 5e5, 1e6, 2e6, 5e6, 1e7, 2e7, 5e7}));
    }

    private void OnGUI()
    {
        _profilerHandler.OnGUI();
    }

    private void Update()
    {
        _profilerHandler.Update();
    }

    struct MyStruct
    {
        public int a;
        public double b;
    }

    // contents of EXP1
    private IEnumerable<MultiTaskProfiler> GetExp1Profilers(IEnumerable<double> loopNumList)
    {
        ExperimentHelper.SetLoopNum(loopNumList.ToArray());

        yield return new MultiTaskProfiler(ExperimentHelper.CreateLoopTasks(loopNum =>
        {
            for (int i = 0; i < loopNum; ++i)
            {
                /* do nothing */
            }
        }), "forループ");
        yield return new MultiTaskProfiler(
            loopNumList.Select(loopNum => 
            {
                var loopObject = Enumerable.Repeat(0, (int) loopNum).ToList(); // O(N) なのでタスクの外で生成
                return new FPSProfileTask(loopNum, () =>
                {
                    foreach(int _ in loopObject) {}
                });
            }), "foreach ループ");
        yield return new MultiTaskProfiler(ExperimentHelper.CreateLoopTasks(loopNum =>
        {
            for (int i = 0; i < loopNum; ++i)
            {
                _ = i / 123456;
            }
        }), "割り算");

        yield return new MultiTaskProfiler(ExperimentHelper.CreateLoopTasks(loopNum =>
        {
            Action emptyFunc = () => { };
            for (int i = 0; i < loopNum; ++i)
            {
                emptyFunc.Invoke();
            }
        }), "関数呼び出し");

        yield return new MultiTaskProfiler(ExperimentHelper.CreateLoopTasks(loopNum =>
        {
            IReadOnlyList<int> myList = new List<int>();
            for (int i = 0; i < loopNum; ++i)
            {
                _ = myList is List<int>;
            }
        }), "型判定");

        yield return new MultiTaskProfiler(ExperimentHelper.CreateLoopTasks(loopNum =>
        {
            IReadOnlyList<int> myList = new List<int>();
            for (int i = 0; i < loopNum; ++i)
            {
                List<int> list = myList as List<int>;
            }
        }), "ダウンキャスト");
        yield return new MultiTaskProfiler(ExperimentHelper.CreateLoopTasks(loopNum =>
        {
            for (int i = 0; i < loopNum; ++i)
            {
                new MyStruct() {a = 5, b = 10};
            }
        }), "構造体の生成");

        yield return new MultiTaskProfiler(ExperimentHelper.CreateLoopTasks(loopNum =>
        {
            for (int i = 0; i < loopNum; ++i)
            {
                new System.Object();
            }
        }), "Object型の生成");

        yield return new MultiTaskProfiler(ExperimentHelper.CreateLoopTasks(loopNum =>
        {
            const int myNumber = 5;
            for (int i = 0; i < loopNum; ++i)
            {
                object _ = myNumber;
            }
        }), "ボクシング");
    }
    
    // contents of EXP2
    public class MyBehaviour : MonoBehaviour
    {
        private void SayHello() { /* No Hello because of performance reason...*/ } 
    }
    private IEnumerable<MultiTaskProfiler> GetExp2Profilers(IEnumerable<double> loopNumList)
    {
        ExperimentHelper.SetLoopNum(loopNumList.ToArray());
        // FPSProfileTask.ProfileFrameNum = 20; // For Debug
        FPSProfileTask.ProfileFrameNum = 60; // For Debug
        
        void RemoveGarbage()
        {
            var garbageObjects = FindObjectsOfType<GameObject>();
            foreach (var garbage in garbageObjects)
            {
                if (garbage.name != "Main Camera" &&
                    garbage.name != "Directional Light" &&
                    garbage.name != "ProfilerObject")
                {
                    DestroyImmediate(garbage);
                }
            }
        }

        yield return new MultiTaskProfiler(ExperimentHelper.CreateLoopTasks(loopNum =>
        {
            for (int i = 0; i < loopNum; ++i)
            {
                _ = new GameObject();
            }
        }), "new GameObject", RemoveGarbage);

        yield return new MultiTaskProfiler(ExperimentHelper.CreateLoopTasks(loopNum =>
        {
            var emptyObject = new GameObject();
            for (int i = 0; i < loopNum; ++i)
            {
                Instantiate(emptyObject);
            }
        }), "Instantiate", RemoveGarbage);
        
        yield return new MultiTaskProfiler(ExperimentHelper.CreateLoopTasks(loopNum =>
        {
            var emptyObject = new GameObject();
            for (int i = 0; i < loopNum; ++i)
            {
                var obj = Instantiate(emptyObject); 
                Destroy(obj);
            }
        }), "Instantiate + Destroy", RemoveGarbage);
        
        yield return new MultiTaskProfiler(ExperimentHelper.CreateLoopTasks(loopNum =>
        {
            for (int i = 0; i < loopNum; ++i)
            {
                FindObjectOfType<GameObject>();
            }
        }), "FindObjectOfType");
        
        yield return new MultiTaskProfiler(ExperimentHelper.CreateLoopTasks(loopNum =>
        {
            var myObject = new GameObject();
            myObject.AddComponent<MyBehaviour>();
            for (int i = 0; i < loopNum; ++i)
            {
                myObject.SendMessage("SayHello");
            }
        }), "SendMessage", RemoveGarbage);
        
        yield return new MultiTaskProfiler(ExperimentHelper.CreateLoopTasks(loopNum =>
        {
            var myObject = new GameObject();
            myObject.AddComponent<MyBehaviour>();
            for (int i = 0; i < loopNum; ++i)
            {
                myObject.GetComponent<MyBehaviour>();
            }
        }), "GetComponent");
    }
}

```

</div></details>


## 実験1: C#の各種処理
![スクリーンショット 2023-03-22 000404.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/606045/97ee4964-a491-dc52-1b97-26aec2100de2.jpeg)

#### 60FPS (1秒間に60回) の頻度で実行した際にフレーム落ちが発生しない限界の回数
| 処理 | 60FPSで処理可能な回数 | コード |
| :---: | ---: | --- |
| for ループ| 5,000,000 | `for (int i=0; i<loopNum; ++i)`  |
| foreach ループ (Array以外[^1]) | 1,000,000 | `foreach (int _ in loopObject);` |
| 割り算 | 2,000,000 | `_ = i / 123456;` |
| 関数呼び出し | 1,000,000 | `func.Invoke();`|
| 型判定 | 5,000,000 | `myList is List<int>;` |
| ダウンキャスト | 5,000,000 | `myList as List<int>;`|
| 構造体の生成 | 5,000,000 | `new MyStruct() { a = 5, b = 10 };`|
| 参照型 (クラス) の生成 | 200,000 | `new Object(); `|
| ボクシング | 200,000 | `object _ = Num;` (Numは `int` 型)|
| IDisposable | 200,000 | `using (new MyDisposable()) {};` |
| 内部で foreach (Array以外[^2]) | 200,000 | `foreach(var _ in myList) {}`|
| IEnumerable.Any() [^3] | 100,000 | `myList.Any();` |
| 大きなヒープ領域の確保 | 5,000 | `_ = new int[1000];` |

スクリプトを実行すると画像の結果が得られました。処理落ちラインをまとめると表のようになりました。
「割り算」以降は`for`ループ自体の処理コストが含まれまれることにご注意下さい。

#### 概要
- Object型（参照型・クラス）の生成コストが一際大きい
  - ボクシング, `foreach` の呼び出し,`Any`などはこのコストがかかっているため重い
- 関数呼び出しや、`foreach`ループのコストは比較的大きい
  - `foreach`ループが`for`ループと比較して遅いのは内部で関数呼び出しを行っているため[^1]
- ヒープ領域の確保は、領域のサイズ依存だがかなりコストが大きい
- 型判定やダウンキャストのコストは小さい


## 実験2: GameObjectの処理
![スクリーンショット 2023-03-26 124148.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/606045/73265be7-dfa5-be76-4c4b-fb69f1a794a9.jpeg)


#### 60FPS (1秒間に60回) の頻度で実行した際にフレーム落ちが発生しない限界の回数
| 処理 | 60FPSで処理可能な回数 | コード |
| :---: | ---: | --- |
| GameObject作成 (new) | 2,000 | `new GameObject();`  |
| Instantiate() | 2,000 | `Instantiate(emptyObject);`|
| Instantiate + Destory()| 1,000 | 上 + `Destroy(clonedObj);` |
| GetComponent | 50,000 | `myObject.GetComponent<MyBehaviour>();`|
| SendMessage | 20,000 | `myObject.SendMessage("SayHello");`|
| FindObjectOfType | 10,000 | `FindObjectOfType<GameObject>();`|

<details><summary> 実験方法の詳細 </summary><div>

デフォルトの3D SceneにProfiler用の`GameObject`のみ追加した状態で計測しました。
`Instantiate` は空の`GameObject`に対して実行しました。
`GetComponent`と`SenedMessage`で使用している`myObject`は、空の`GameObject`に次のMonoBehaviourを追加したものです。
```C#
public class MyBehaviour : MonoBehaviour
{
    private void SayHello() { /* 空のメソッド */ } 
}
```
エディタ上での実行のため、Hierarchyウィンドウはオーバーヘッドの回避のため閉じて実行しています。

##### 追加変更内容
 (2023/03/26) 計測タスク単位で`GameObject`を掃除するようにスクリプトを修正しました。表の結果には影響はありません。
 (2023/03/26) GetComponent, SendMessage, FindObjectOfTypeを追加しました

</div></details>

#### 概要
- GameObjectは `new`, `Instantiate()`, `Destroy()` などのオブジェクトの生成や破棄の処理は、いずれも非常に大きな処理コストがかかる。
- 生成や破棄ほどではないが、`GetComponent`、 `SendMessage`、 `FindObjectOfType`などのUnityオブジェクトに対する各種メソッドは、比較的大きな処理コストがかかる。

:::note info
（参考）
`SendMessage`、`BroadcastMessage` は直接の関数呼び出しに比べて1000倍単位で遅くなる場合があると[Microsoftの公式ドキュメント内の記事で](https://learn.microsoft.com/en-us/windows/mixed-reality/develop/unity/performance-recommendations-for-unity?tabs=openxr)警告されています。
:::

## 実験3: LINQの処理
![LINQその1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/606045/79b47c7b-89d7-5850-9608-18d7e3efbfb9.png)
![追試.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/606045/a701cfc1-bc9b-efd3-3a23-bed9c1316efb.jpeg)

#### サイズ1000の`List<int>`に対してLINQの操作を実行した結果
| 処理 | 60FPSで処理可能な回数 | コード |
| :---: | ---: | --- |
| Object型の生成 (参考) | 200,000 | `new Object();`  |
| Any | 100,000 | `myList.Any();`  |
| Where | 50,000 | `myList.Where(x => x > 500);`  |
| Select | 50,000 | `myList.Select(x => x * 500);`  |
| ToArray | 5,000 | `myList.ToArray();`  |
| ToList | 5,000 | `myList.ToList();`  |
| ToHashSet | 200 | `myList.ToHashSet();`  |
| ToLookup (key多め) | 20 | `myList.ToLookup(num => num, num => num * num);`  |
| ToLookup (key少なめ) | 100 | `myList.ToLookup(num => num%10, num => num * num);`  |
| GroupBy (group少なめ) | 100 | `myList.GroupBy(num => num%10);`  |

LINQの各操作について調査した結果がこちらです。LINQの処理時間は大体 `IEnumerable` オブジェクトの要素数に依存しますが、ここでは0から999までの値を持つ`List<int>`オブジェクトに対して処理を行って計測しました。Where, Select, GroupBy は、遅延評価を解決するために`Any()`を呼び出しています。

#### 概要
- LINQ の基本コストとして、Enumeratorに起因する **Objectの生成が1回または2回発生する** (Listの場合はEnumeratorがstructでボクシングするため2回)
  - `Where` などをチェインして何度も呼ぶ場合はその分だけコストがかかる
- `Where`, `Select`, `ToArray`, `ToList` はコレクションのサイズに応じて `O(n)` のコストがかかる
  - `ToArray`と`ToList` は配列のコピー時にヒープ領域を確保するので特にコストが重い。
- `ToHashSet` も基本的に `O(n)` だが、ArrayやListを作るよりはだいぶ重い。[^5]
- `ToLookup` はKeyごとにオブジェクトを生成するので、Keyが多いと処理が重くなる
- `GroupBy`もグループごとにオブジェクトを生成するので、グループが多いと処理が重くなる

[^5]: `List`の生成などと比べてここまで重い理由はよく分かっていません。`HashSet`は内部（のヒープ領域）にstructを大量に持つので、これが重いのかなと個人的に予想しています