新規
編集
添付こちらも参考に。 
基本的な手順
基本的には次の手順で高速化します。
- 処理時間を計測する。計測項目は、以下の通り。
- トータル処理時間
- １回あたりの処理時間平均
- 処理回数
- できれば、コールグラフ（関数の呼び出し先、呼び出し元情報）
- 処理時間が一番大きいものや、処理回数が多いものを選ぶ。（おおよそ経験）
- 処理の中で高速化できそうな所を探す。（きっちりオーダをとってくのがいい）
- 処理を高速にする。
- 処理を端折る。
具体的な内容
何が重いのかを知る
すぐにやれること
処理を簡素化する（計算精度を犠牲にする）
呼び出され回数を減らす
繰返しの中で同じ計算をしていないかを調べる
コンパイル時に計算できるところは先にする
組み込み命令（SIMD、AltiVec、NEON）を使用する
浮動小数点数を固定長小数に変更する
ループ
ループ中で分岐しない
もしその分岐条件がループ中に変化しないのであれば、ループの外に分岐条件を出したほうが良い。
ループ展開する
以前した処理を覚えておき、再計算しないようにする
ハードウェアを改善する（CPUやメモリ、HDDなど）
並列処理への対応
OpenMP
MPI
GPUの利用
GPGPU
OpenCL
NVIDIA CUDA
アルゴリズム
単方向リストを双方向リストに変更する
ハッシュテーブルを導入する
データ個数が多い場合の検索、２分木やハッシュテーブル（連想配列）に置き換えることで高速になる可能性が高い。
動的計画法を導入する
BM法で検索する
並列アルゴリズムの検討
Bitonic-sort
言語の仕様を知る
使用するライブラリの仕様を知る
CPUを理解する
分岐を排除する
CPUアーキテクチャにも依りますが、x86/64系の分岐が不得意なCPUでは、ループ内で分岐させるくらいなら、SIMD命令で計算は全部してしまって、ループを抜けた後に利用する値を決めた方が良い。
キャッシュヒットミスを排除する
多くのシステムでは、CPU内部に多段階のキャッシュメモリを持ち、そこから主記憶装置（メモリ）にアクセスします。また仮想記憶システムを備えたOS（Linux、Mac、Windowsなど）では、主記憶装置に配置したメモリが補助記憶装置に書き出されてしまうことがあります。また、キャッシュメモリ、主記憶装置、補助記憶装置の順に読み書き速度が速く、価格も高く、容量は少ない・・・というのは常識です。また、CPUは近年、数GHzといったクロックで動作し、その速度に対し、主記憶装置の読み書き速度は遅すぎます。そこでキャッシュメモリを配置し、その差を埋めるようになりました。アスキーのサイトが分かりやすいです。
http://ascii.jp/elem/000/000/563/563800/
ということで、いかにキャッシュメモリにあるデータにアクセスするか、キャッシュヒットミスして主記憶装置にアクセスしないことが重要になります。また補助記憶装置はさらにそれ以上に遅いため、基本的には各種プロファイラー等が示す指標を見て、実行中に補助記憶装置にアクセスしていないことを確認します。（Windowsのタスクマネージャーで、ページアウト回数を見ておくなど。）
機械語、マシン語、アセンブラ
コンパイル後にどういう機械語に変換されるのかを知る
機械語レベルで命令数を減らす書き方に変更
機械語レベルで組み直し、命令数を減らす
エラー処理
正常動作でthrowを使わない
throwすると、ものすごく重い。本当に異常な動作の場合にだけ、throwする。throwすることの目的はエラーの回復ではなく、リソースの解放である。例外が発生するような状態において、その後の動作を保証できるものではないので、基本的に動作の継続は不能である。
用語集
- ILP, Instruction-level parallelism, 命令レベルの並列化
- １クロックでできるだけ多くの命令を実行するための技法のこと。
- IPC, Instructions per clock
- １クロックあたりの実行命令数。
- OoO, out-of-order execution, アウトオブオーダー実行
- ILPの１つ。通常、アセンブラソースに書かれた命令順序（プログラム順序）で実行するがこの順序をデータ順序に入れ替えることでIPCを多くする。
