最適化概論



# 初めに

C#/Unityの使用者を対象に書いておりますが、**基本的には（ゲームのクライアントサイド）プログラミング全般**に言えるような内容です。
ただし、ライブラリやミドルウェアに関しては話が変わってくるのでケースバイケースです。

「最適化」などをキーワードに調べはずめると様々なテクニックが得られます。
例えば、

* どのAPIを使うべきか（類似するAPIのベンチマーク）
* どんな記法を取ると処理時間が短縮できるか
* キャッシュを使った方がよい

などなど…
これら個別のテクニックは非常に有用ではありますが、それを活用するまでの実務的なノウハウに関してはあまり見かけない印象です。
だからといってコードの片っ端から最適化テクニックを適用していけばよいというものではありません。最適化にはデメリットもあり、必要な部分に必要な分だけにとどめておくべきです。

とはいっても、ある日突然「今開発してるプロダクトを高速化して欲しい」と頼まれた時、慣れていないプログラマーにとっては何から手を付けたものか困るかと思います。

ここでは、実務的な手順を中心に「こんな風に進めてみたらいかがでしょうか」という紹介をしていきたいと思います。
ただし、これはあくまでも私個人の経験に基づくものであり、正解でもなければ、もっと効率的で効果的な流儀があると思いますので参考として自分なりのやり方をみつけてください。

# 「最適化」を任された！！

残念ながら現在のプロジェクトチームには、最適化の経験が豊富なプログラマーがおらず突然頼まれてしまったとします。
また、プロジェクトのコードは複数人のプログラマーで書いており、中にはもう実装者がおらず質問もできないコードもあります。

### 実行環境やコンパイラを変えてみる

OSやミドルウェア、コンパイラなどは日々進化しており、一般的に最新のも程効率的に動作します。C#のような中間コードを持つ言語、インタプリタ言語ではAOTやIL2CPPによって劇的に高速化される場合があります。
影響範囲は全体になってしまうので、簡単にはできないかもしれませんが…一応、こういうオプションもあるということは頭に入れておいて良いでしょう。

### 問題の把握

最適化を頼まれたからには、ユーザビリティに問題があるはずです。
次のようなものが考えられます。

* FPS低下/フレーム落ち
* 発熱問題（モバイル）
* 瞬間的にカクつく（操作時のレスポンスが悪い）
* クラッシュする
* ロードが長い


逆にユーザビリティに問題はないが「なんとなく」最適化をしようとしているならば、やめるように説得した方がよいです。
なぜなら、最適化をするためには何かを犠牲にしなければならない可能性が高いからです。
例えば、今まで正しく動いているものに手を加えて余分なバグを発生させるリスク（デバッグコスト）、コードの可読性が下がることで保守コストがが増加するといったデメリットが考えられます。

また、最適化は一般的に開発の最後の方でやるべきといわれています。これは、せっかく最適化しても仕様が変わってしまう可能性が高いことや、可読性を下げてしまうせいで開発効率を落としてしまわないためです。
開発効率を高めるためや、あまりにも我慢できないほど非効率でなければもう少し待ってみた方が良いです。

### 問題の分類から原因のアタリをつける

具体的な症状が分かればおおよその原因の潜んでいる個所を絞り込むことができます。
アタリを付けたら、最適化を助けてくれる便利なツールを使ってさらにメソッド単位までボトルネックを絞り込んでいきます。

|| ユーザビリティの問題 | 原因のアタリ | 次の対応の方針 |
|:-:|:-:|:--|:--|
|A| FPS低下/フレーム落ち | 1フレームに処理を詰め込み過ぎ。UnityではUpdate系や、GPUの描画が1/60秒を超過。 | [Profiler][prof]でフレーム中の処理時間の内訳を長い順で最適化を検討。 |
|B| 発熱問題 | GPUの描画負荷が高い。[^hot] | GPUの最適化については割愛 |
|C| 瞬間的にカクつく | 毎フレームヒープメモリを確保していることによるGCが発生。UnityではUpdate系の中でClassをnewするなど。確保された後、解放もされていないとDに発展する。 | [Profiler][prof]でアロケーションを発生しているものを探すか、[MemoryProfiler][mprof]でフレーム間のメモリ占有オブジェクトを比較して増加しているものを探す。 |
|D| クラッシュする | 使っているメモリの量が多すぎ | [MemoryProfiler][mprof]で占有量の多いものから最適化を検討。 |
|E| ロードが長い | アセットの読み込み過ぎや、まだ必要のないものまで読み込み。謎の待ち（何もしない）が発生している。 | 処理の塊ごとに[Stopwatch][sw]による時間計測をコード内に書き込んでいって、占有時間が長いものから最適化を検討。[^sws] 実装例 [LoadingProfiler][lprofiler] |

[prof]: https://docs.unity3d.com/ja/2020.2/Manual/ProfilerWindow.html
[mprof]: https://docs.unity3d.com/ja/2020.2/Manual/com.unity.memoryprofiler.html
[profa]: https://blogs.unity3d.com/jp/2019/05/13/introducing-the-profile-analyzer/
[sw]: https://docs.microsoft.com/ja-jp/dotnet/api/system.diagnostics.stopwatch?view=net-5.0
[lprofiler]: https://github.com

[^hot]: 昨今のCPUは2コア以上が主流な一方で、特別なことをしていない限りアプリケーションは1つのコアしか同時に使うことができません。（特にゲームでは）なので、CPUのチップ全体で見たとき稼働率が100%に達するケースは少ないです。そのため、放熱が追い付かないほどCPUが熱を持つことはあまりありません。
[^sws]: 今のところ決定版的なツールが見つけられませんでした。（プロジェクトによって「処理の塊」が異なるため結局コードに仕込むしかないからでしょうか）[ProfilerAnalyzer][profa]を使うことで、複数Frameを合計してメソッドごとの占有時間が見られるのでこれで観ることもできます。何度もProfiling結果とにらめっこをすることを考えるとやはり、「ここ～ここまでは○○の処理」のように手動で埋め込んでいって、ガントチャートのような形式で見えるようにした方が効率的だと思います。

### 犯人が見つかった！

上記のようにしてボトルネックとなっているメソッドを見つけることが来ました。
「ロード時間が長い（5秒）」というEの問題に対して、あるメソッドが4秒の時間を使っていたとします。

ロード中には他の処理もしているかとは思いますが、1秒を50%にするよりも4秒を50%にする方がユーザビリティに良い影響をもたらすことは明らかです。これまでの過程でいろいろと気になる部分が見つかるかもしれませんが、最適化のことを考えるならば些末な部分は捨ておいて良いと思います。（気になってしまう気持ちはわかりますが）

また、この時に目標も決めておいた方が良いでしょう、キリがなくなるので…

ではさっそく、「最適化テクニック」を使ってメソッド内をチューニング！！！！
…する前にやった置いた方が良いことがあります。

### リファクタリング

最適化をすることで、要件を満たさなくなってしまったり、バグを発生させてしまったは元も子もありません。実務的にはこれが一番重要だったりします。

「最適化しやすいコード」「最適化しにくいコード」があります。

```csharp
// 最適化しづらい例
A[] GetSortedList(){
  for(var i=0; i<m_List.Count; i++){
    for(var j=1; j<m_List.Count+1; j++){
      if (m_List[j].Name.Id < m_List[j-1].Name.Id){
        var tmp = m_List[j];
        m_List[j] = m_List[1];
        m_List[i] = tmp;
      }
    }
  }
  return m_List;
}

// 最適化しやすい例
IReadOnlyList<A> GetSortedList(){
  SortImpl(m_List, ExtractId);
  return m_List;
}
static int ExtractId(A a) => a.Name.Id;
static void GetSortedList(IList<A> list, Func<A,int> keySelector){
  for(var i=0; i<m_List.Count; i++){
    for(var j=1; j<m_List.Count+1; j++){
      if (keySelector(m_List[j]) < keySelector(m_List[j-1])){
        var tmp = m_List[j];
        m_List[j] = m_List[i];
        m_List[i] = tmp;
      }
    }
  }
}
```

上記コードでは、「ソートアルゴリズム」と「ソートキーの決定」を分離しています。このように、「責任範囲」がメソッドやクラスに綺麗に分かれているのが理想です。
この例の場合、ソートアルゴリズムをバブルソートからクイックソートにすることで高速化が期待できます。しかし、前者の場合ではソートの最中にキーを決定する処理が挟まっているので、クイックソートを実装することだけに集中できません。
RAIIやSOLIDの考え方が参考になります。

例にはありませんが、配列や構造化されたデータを扱う場合にはImmutableにするのと、キャッシュやマルチスレッドによる最適化をしやすくなります。具体的には、関数型プログラミングの考え方が参考になります。

### 最適化テクニックを適用！

リファクタリングをして、動作確認（テスト）をパスしたらいよいよ核心部分を書き換えます。
上記のソードでは、原始的なバブルソートからクイックソートに変更するのも良いでしょうし、境界値チェックを外してみるのも良いでしょう。

### 計測・デバッグ

実装が完了したら、変更前後でユーザビリティが改善されていることと、バグが起きていないことを確認します。もし、改善が見られなかったりさらに改善が必要であれば地道に改善を繰り返していくことになります。

# ボトルネックの嗅覚

どんなところがボトルネックになりやすいか知っておくとよいでしょう。

### コードが汚い箇所

これに尽きるのですが…

腕の良いプログラマーが書いたコードであっても、仕様変更やバグ修正を繰り返していくうちに初見で簡単に理解することが難しいほどに汚れていってしまうものです。また、エンジンや言語が古い時代に古い記法で書かれたコードなど…
こういったコードは簡単には全貌を理解することができないため、適当にif文かませて辻褄を合わせたり、処理が完了しているか分からないので余分に待つ・念のためでなんども同じ処理をするなどのことが起こっている可能性が高いです。
仕様がオミットになり要らなくなった処理が残っているけど怖くて消せない…なんてこともよくあります。
そもそもこういった、無駄を削るだけでかなりの改善が期待できます。

普段から、無駄なく漏れなくちゃんと理解してコーディングをすべきなのはもちろんのことですが。
（そうも言ってられない日だって…）

### アルゴリズムレベルの問題

母数の多い検索・シミュレーションなどです。オーダーが下げられればいいですがそう簡単ではないです。
しかし、バックスレッドに逃がしてフライングさせたり、キャッシュするなどの手はあります。
こういうのは新規実装時にある程度考慮されていたり織り込み済みだと思うので、後々問題になってくることは実際少ないです。

### 副作用（特にキャッシュ）

最初にキャッシュを実装したプログラマーはきっと「超効率的や～！」と思っていることでしょう。
しかし、引き継いだプログラマーはそんなキャッシュがあることなんてツユと知らない可能性があります。そうなってしまえば、キャッシュのプリロードは処理の重複でしかないばかりか、メモリも無駄に浪費することになってしまいます。
キャッシュというのはいってしまえば副作用そのものです。パフォーマンス上、必要になるまではできるだけ使わないのが吉です。また、どうしても使う場合には、キャッシュがされている場合もそうでない場合も透過的に扱えるようにしておくと「念のため再生成」を避けることができます。
C#では`Lazy<T>`を使うとよいでしょう。

```csharp
class A
{
  Asset m_HeavyObject = null;
  void AssetUser(){
    // ちゃんと皆こう書いてくれればいいが…
    if(m_HeavyObject == null){
      m_HeavyObject = new HeavyObject();
    }
    m_HeavyObject.DoSomething();
    // こう書かれちゃうかもしれない（非同期ならもっと酷くなり得る）
    m_HeavyObject = new HeavyObject(); // まだ作られてないような気がするから、念のため
    m_HeavyObject.DoSomething();
  }

  // Better
  readonly Lazy<Asset> m_HeavyObject = new Lazy<Asset>(() => new HeavyObject());
  void AssetUser(){
    m_HeavyObject.DoSomething();
  }
}
```

# まとめ

あくまで経験則ですが、最適化をしているとき実際にはそのほとんどの工数を処理の把握とリファクタに費やされています。

ユーザビリティに影響が出るほど遅くなったりメモリを食っている個所というのは、そもそもコードが汚れてしまってアンタッチャブルになってしまっています。そうでなければ、何万もの要素のリストを扱うなど本当にクリティカルな部分です。

整然としているならば放置されずとっくに修正されていることでしょう。逆説的ではありますが、綺麗なコードは速いのです。
より正確に言うなら、「綺麗なコードは速くできるが、汚いコードを早くするのはものすごく労力とリスクを伴う」でしょうか。

よく、LinqやEnumerable+foreachは遅いからfor+インデクサを使いましょうとか、キャッシュしましょうとかの話を聞きますが、長い目で見たときに本当にユーザビリティに悪影響を与えないのは前者だと思います。（もちろんケースバイケースですが）

**中途半端に速度/省メモリを意識して汚くするよりも**
**あとから最適化しやすい切れなコードを書きましょう**
**（もちろんケースバイケース）**