リファクタリングはパフォーマンスの改善にならない理由 （パフォーマンス診断の３ステップ＋Laravelでの例）

## はじめに

アプリケーションが重くなる時、どこから調査しますか？どうやって解決しますか？

リファクタリングしてソースコードの行数だけ減らせば処理が軽くなるという考え方を耳にすることもありますがその根拠が薄いと毎回思っちゃいます。

代わりに自分の勉強からまとめたパフォーマンス診断の３ステップをご紹介します！
セオリーの部分読んでいただければリファクタリングだけはパフォーマンスの改善にならない理由がわかります。
Laravelに全く親しみがない方にもお役に立つと思います。

パフォーマンス3ステップ診断：
1. データ使ってボトルネックを見つける
2. 計算複雑度を分析する
3. 計算複雑度を軽減する

## 目次
- [データ使ってボトルネックを見つける](#データ使ってボトルネックを見つける)
- [計算複雑度を分析する](#計算複雑度を分析する)
- [計算複雑度を分析する](#計算複雑度を分析する)
- [最後に](#最後に)

## データ使ってボトルネックを見つける

>If you fear performance may be a problem, I recommend that you conduct some experiments to prove that it will be a problem. Once proven, and only once proven, you should start considering how to speed things up.
パフォーマンスに問題があるのではないかと心配な場合は、実験を行って問題があることを証明することをお勧めします。 証明されたら、証明された場合だけは、パフォーマンス改善の方法を検討し始めて良いです。

– Robert Martin (Agile Software Development, Principles, Patterns, and Practices)

アンクルボブのお言葉に従えば良い：証拠のない最適化は自分でトラブルを作ることに違いありません。まずはデータから始めてください。

Laravelの場合、[Debugbar](https://github.com/barryvdh/laravel-debugbar)がおすすめです。リクエストごとにデータベースのタブ見て、クエリ数が多すぎるかどうか、または 1 つのクエリに時間がかかりすぎるかどうかを確認してください。ウェブアプリケーションにおいては一番よく見るボトルネックです。

![Screenshot 2024-03-23 at 17.22.32.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3742582/acb86e29-b4a9-9598-660a-a603ddc8b758.png)

重いページがわからない場合、ウェブサーバのログ見て一番アクセスが多いページを特定する。ページのどのAPIが重いか、もしくはフロントエンドかバックエンドが原因かわからない場合、Google Chromeのネットワークタブ見て判断する。パフォーマンスの問題を再現できない場合、本番環境と同じ件数までデータベースをシードしてください。

![Screenshot 2024-03-23 at 17.41.38.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3742582/f3e96079-bf72-9105-7ac1-b55eb657771b.png)

とにかく、デバッグと同じくデータ使って絞り込んでください。ボトルネックが分からない限りパフォーマンスの最適化が出来ません。リファクタリングだけはパフォーマンス改善できないの1つ目の理由はボトルネックとその証拠になるデータはまず提出していないからです。

## 計算複雑度を分析する

[計算複雑度理論](https://ja.wikipedia.org/wiki/%E8%A8%88%E7%AE%97%E8%A4%87%E9%9B%91%E6%80%A7%E7%90%86%E8%AB%96)さえ理解すれば、99％のパフォーマンス問題が解決できます。この理論は何か簡単に言うと、インプットデータが増加すると、実行時間 (と使用メモリ) がどのように増加するかの考え方です。

`n`をインプットデータの長さとします。何のインプットかと言うと、**ステップ1**からわかります！大きいテーブルに対してクエリが時間かかりすぎる場合、`n`はそのテーブルの件数になります。アップロードファイルが大きすぎる場合、`n`はそのファイルのバイト数になります。長いリストに対してループ実行している場合、`n`はそのリストの長さです。

次ですが、`n`と実行時間の関係性を[O記号](https://ja.wikipedia.org/wiki/%E3%83%A9%E3%83%B3%E3%83%80%E3%82%A6%E3%81%AE%E8%A8%98%E5%8F%B7)で表します。例えば、`O(f(n))`が`O(2n)`の場合、アプリの実行時間が`n * 2`と比例します。知っておいて欲しい`O`関数は次のとおりです。

#### O(1)
まず、`O(1)`は最高です。nのサイズに関係なく実行時間が一定の時です。ループがない時は大体O(1)になります。1000行の関数でも`O(1)`である可能性があります。実際、`O(1000)`は`O(1)`と等しいと言います。`n`が無限になると1000と1は大して変わらないからです。つまり、ソースコードを1000行から1に片付いても、パフォーマンスを改善出来たとは言えません。

#### O(logn)
続いて`O(logn)`も結構速いです。ソートされたリストまたはハッシュインデックスを検索している場合、`O(logn)`になります。 (計算は省いておきますが、二項検索だからです。）この場合、実行時間はnに応じて増加はしますが、無視できるほどとして良いです。なので、テーブルを正しくインデックスしていると、テーブルのサイズが倍になっても検索時間が1ループしか増えない状態が出来ます。

#### O(n)
最後に、`O(n)`は実行時間が`n`に比例する時です。ちなみに、`O(1000n)`は`O(n)`に等しいです。ループが配列の全部の要素を実行する時、インデックスのない列で検索する時、`O(n)`になる可能性が高いです。`n`が無限になると`O(n)`も無限になるので、`O(n)`以上のアルゴリズムはリリース前にリファクタリングする対象です。（何千件以上増えない`n`は無視して良いです。）

![chart.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3742582/96a9dfdb-3e36-c69d-3f21-f285b9700c4a.png)

上記以外にも、`O(nlogn)` (ほとんどのソートのアルゴリズム)、`O(n^2)` (二重ネスト ループ)、`O(2^n)`、`O(n!)` などもありますが、今のところは上記のことだけでも十分です。


## 計算複雑度を軽減する

ここからが楽しい部分です。計算複雑度をランクダウンさせます。 ご参考になればと思います！

#### LaravelのEager Loading
Laravelでは一番簡単で認知度が高い問題です。Debugbarで数百件の重複クエリの表示はEager Loadingが効いていない証拠です。`load()`か`with()`を使って修正してください。重複しているけど`O(1)`に等しい場合はパフォーマンス観点だけで言うと無視して良いです。

#### インデックス
検索されているカラムにインデックスがない場合はインデックス作ってください。インデックスがあるけど使われない場合は使われるように修正してください。Debugbarからクエリを切り取って`explain`でインデックスが使われているかどうか確認できます。` STR_TO_DATE()`や`CONCAT()`、または `%`から始まるLIKE式はインデックスが使えない可能性が高いです。

インデックス使われる場合
![Screenshot 2024-03-23 at 18.15.07.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3742582/5d479e4c-b38f-d743-7de2-b68eb1b0d013.png)
`CONCAT`によりインデックス使われない場合
![Screenshot 2024-03-23 at 18.18.13.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3742582/882eccea-556c-5284-d3ab-11c911ace0d4.png)

また、インデックスが複合インデックスであり、検索されるカラムがインデックスの一番最初のカラムではない場合も、インデックスが使えません。インデックス作成は時間とメモリーのトレードオフであるため、本当に速度の向上が必要かどうか、またカラムが検索の絞り込みに役立つかどうかをよく検討してください (ステータスとかは通常、候補としては不適切です)。

#### 連想配（ディクショナリ、ハッシュマップ）
ソート済み配列の`O(logn)`よりも検索時間が速い`O(1)`と言う素晴らしいデータタイプです。例えば、
```
＄collection->where(‘id’, ‘=’, $foo)->first()
```
をループ内で使うと、最悪の場合の時間が`O(n^2)`になるので一回
```
$keyed = $collection->keyBy(‘id’)
```
でディクショナリを作ってから`$keyed->get($foo)`で検索した方が`O(n)`で済ませてパフォーマンスが良いです。

#### メモ化／キャッシュ (と動的計画法)
時間がかかる計算を何回もしている時は[メモ化](https://ja.wikipedia.org/wiki/%E3%83%A1%E3%83%A2%E5%8C%96)が有効です。[動的計画法](https://ja.wikipedia.org/wiki/%E5%8B%95%E7%9A%84%E8%A8%88%E7%94%BB%E6%B3%95)と言うメモ化を使って計算複雑度を`O(2^n)`から`O(n)`に変更できる魔法の技もありますが現場で適用できる場面があまり見たことないです。代わりに、メモ化でちゃんとボトルネックになっている計算結果を再利用できるように変換して保存しているば結構良いパフォーマンス改善になることはあります。

#### ページネーション
一覧を返却するAPIには必ずページネーションを入れた方が良いです。時間もメモリーも両方`O(n)`になる可能性が高いからです。1週間か1ヶ月分のデータしか返却しないAPIでも結構な量になり痛い目あったことありますので全然油断が出来ないです！Laravelの`offset`を使うページネーションは`O(n)`なので必要であれば[Cursor Pagination](https://laravel.com/docs/11.x/pagination#cursor-pagination)の方がおすすめです。

#### チャンク
メモリーの計算複雑度はあまり触れていませんが、チャンクはその軽減が出来ます。PHPではよく見ることですが、`Out of memory (allocated XXXXX) (tried to allocate XXXXX bytes) `のエラーが出ると、安易に`ini_set(‘memory_limit’, 999999999)`が使われて使用メモリーが極限まで伸びて最終的にサーバーのアップグレードが必要になる状態…もう見たくないです！チャンク（Laravelの場合`$collection->chunk()`)を使ってください。アップロードファイルが大きすぎる時はブラウザでファイルをチャンクしてからアップロードした方が良いです。

#### キュー
計算複雑度がどうしても軽減できない場合（データのインポートや出力の時など）、キュー使って一気に`O(1)`にすることが出来ます。キューでも時間制限ありますのでチャンク使って分けてください。時間が`O(n)`以上の場合、`timeout`がどれぐらい大きく設定しても足りません。チャンクをしないと`timeout`だけではなくLaravelの`retry_after`とか、他にどこかの設定も変える必要があり忘れると地獄見ますので。


## 最後に

ベトナム人で日本語のブログを書いたことがないので日本語のご指摘はウエルカムです！
内容の異論だけは認めません＾＾