プログラムの高速化をする手法はいろいろありますが(個人的)重要度別でまとめてみました。
この記事では各手法について細かくは述べず、概要にだけ触れます。
(適宜更新予定)
はじめに
高速化に取り掛かるにあたって下記2点が重要だと思います。
- 始めから高速化しようとしない。
- テストを整備する。
高速化の解説記事で言うのも何ですが、高速化は手法によっては可読性を下げたりデバッグの難易度を高めたりすることがあります。
基本的にはある程度仕様通りに動くようになるまでは、高速化を考えすぎるよりも可読性を重視して書くのがセオリーだと思います。
ただし手法によっては設計段階から検討すべきものもある(並列化など)ため、性能要件が厳しい場合等には注意が必要です。
そして高速化に着手する際にはテストがきちんと整備されていることが重要です。
もちろん対象にテストが整備されているという状況ばかりでは無いと思いますが、安全に高速化するためには部分的にでもテストを追加することで、安全に様々な手法を試すことが出来ます。
重要度高
並列化
昨今のコンピュータのリソースを鑑みると、並列化は最も汎用性が高い高速化手法であると思います。
組み込み等でリソースが限られている場合は例外ですが、通常のPCレベルのリソースでも細かい施策をちまちまやるより効果がある場合が多いです。
ただよく知られている通り並列化は排他処理をきちんと行わなければ発見しにくいバグの原因になりかねず、デバッグも複雑になります。
高速な動作が要求される場合には設計段階から並列化を見越した設計を行う必要があります。
そうした設計が行われていないアプリケーションを後から並列化対応するのはそれなりに難易度の高い作業になります。
ただ、ソフトウェア全体ではなく部分的な並列化という手法もあります。
C/C++でよく使われるOpenMPを使うとループを手軽に並列化出来たりと、全体の設計を見直さずとも一部の重い処理を手軽に並列化できます。
ただもちろん並列化されたループ間での排他処理は考える必要がありますし、むやみにこの手法を乱用しスレッドを作りすぎれば、むしろスレッド作成のオーバーヘッドにより速度が下がる場合もあります。
速度とリソース消費量をこまめに検証しつつ少しずつ適用していくのが良いと思います。
I/Oアクセスの最適化
一般的にRAMに比べるとストレージへのアクセス、すなわちファイルの読み書きは遥かに遅いです。
外部のポートとの通信、ネットワークの通信等、ここではまとめてI/Oアクセスと呼ぶことにしますがこれらはさらに遅くなります。
アクセス1回につきオーバーヘッドが発生するような場合には、まとめてやるようにするだけでかなり改善します。
ファイルの読み書きであれば1バイトずつループで回すよりも必要なサイズをまとめて読み書きしたり、書き込む情報をRAMに貯めておいて、ある程度貯まった時点でまとめて書き込みを実行するなど、アクセスする回数を減らす工夫を行うと良いと思います。
また、明らかに1アクセスに時間がかかることが分かっている場合には、そこで処理を待つのではなく可能であれば平行処理や並列処理などで先に他の処理を進める手段も有効となります。(ただし設計段階でアクセスと処理の進め方について十分に検討しておく必要があります。)
重要度中
計算量オーダーを下げる
大きなデータを処理する際に計算量オーダーを下げるのはとても大切ですが、重要度を中としたのは難易度がそれなりに高いと思うからです。
ソートなど、有名なアルゴリズムであればあえて遅いアルゴリズムを採用している場合などありえないでしょうし、そもそも基本的なアルゴリズムはライブラリを使うのが普通で自前で用意することは無いでしょう。
完全に独自のアルゴリズムに対し、計算量を下げるアルゴリズムを探すのはそれだけで1つの研究テーマになることもあるぐらい難易度が高いと思います。
よって基本的には「世の中で似たようなアルゴリズムが既に研究されていないか」ということを探すことになると思います。
なお、入力データが少ない場合には計算量オーダーを下げても必ずしも高速化するわけではないことを以下で解説していますのでよろしければご覧ください。
事前計算
ルックアップテーブルなどに代表される「事前に計算出来るものはやっておく」という考え方です。
計算が重い場合や、重くはないが呼び出し回数が多いところに着目するのが基本となります。
近似の利用
数学的な方法により近似を行うことで計算が高速化する場合があります。
よく使われる近似:
(1+x)^n\simeq1+nx\quad(|x|\ll1)
\sin\theta\simeq\theta\quad(|\theta|\ll1)
ただし、近似の精度については問題ないかよく検証する必要があります。
適切な型の選択
変数の型として何bitを選択するかにより速度が変わる場合があります。
近年のPC向けCPUであればdoubleの代わりにfloatを選択する意味は(速度的な面では)ほぼ無いとされますが、環境により差がある部分です。
機械学習等でGPUを利用する場合、GPUのアーキテクチャにより得意とする精度が異なる場合があります。
重要度低
コンパイルの最適化
コンパイラ型の言語に限定されますが、C/C++で言えば
- 関数のinline化やマクロ化
- const修飾子付与
- 一時変数の削減
- 除算を乗算に置き換える
等々、定番とされるテクニックは多数あります。
ただ現代のコンパイラは最適化が優秀なため、これらの施策は手間の割りに効果がほとんどない(最適化により既に行われている)場合が多いように感じます。
古いコンパイラを使っている、何らかの事情で最適化を切っている場合などに最終的なチューニングの目的で使うのが良いかと思います。
関数のinline化やマクロ化はデバッグがやりにくくなりますし、一時変数の削減も本来名前がつけられるべき値から名前が無くなるなど、可読性への影響があります。
デメリットも多いため、既に十分に検証されたコードに対し、最後の一手ぐらいで行うのが良いでしょう。
可読性を犠牲にするような変更をする場合、その旨をコメントやコミットログに詳細を残しておくことである程度後任者のメンテナンス性の助けにもなります。