『プログラミング作法』まとめ16

頻繁に使われる値をキャッシュしよう

キャッシュされた値は計算し直す必要がない。
キャッシングは、局所性（プログラムや人間が最近アクセスされた項目や手近にある項目を再利用したがる傾向のこと）を利用している。ハードウェアにもキャッシュがふんだんに利用されているようにソフトウェアにも利用されている。たとえば、WebブラウザのページキャッシュはInternetからの低速なデータ転送を実行しないで済むようにしている。

専用のアロケータを書こう

mallocやnewの呼び出しを大量に実行するメモリ割り当ての部分が、プログラム中の唯一のホットスポットとなっているケースがよくある。大半が同一サイズのブロックを要求する呼び出しであれば、専用のアロケータ（mallocを1回呼び出して大きな配列を確保しておき、必要に応じて1個ずつ項目を渡す、開放された項目は、再利用できるようにフリーリストに並ぶ。）を利用することで大幅な高速化が見込める。
（要求サイズが近い場合には、常に最大の要求を満たすサイズを割り当てる：領域より時間を優先）

入力と出力をバッファリングしよう

バッファリングによってトランザクションがまとまり、付随する処理のオーバーヘッドが減る。処理のコストが複数のデータ値に分散する。

printfの場合は、文字をバッファ中にためて、バッファがいっぱいになるかフラッシュするまでOSに渡されない。OS自体もディスクへの書き込みを遅らせる場合がある。
短所として出力バッファをフラッシュする手間が必要、プログラムがクラッシュするとバッファ中の情報が失われることがある。

特殊なケースは個別に処理しよう

同一サイズのオブジェクトを別個のコードで処理する専用のアロケータを使用すれば、汎用アロケータを使用した場合の時間と、領域のオーバーヘッドが減少し、メモリの分断も緩和される。

結果を事前に計算しておこう

必要な時点ですぐ利用できるように値を事前に計算しておくと、高速化できる場合がある。サインなどの数学関数を使用する繰り返し計算で、離散値の集合で済む場合は360個のテーブルを事前に計算してインデックスでアクセスするようにする。（領域を犠牲にして時間を優先）
コードの代わりにデータを使ったり、コンパイル時に計算を実行したりできる場面が数多くある。時間と場合によって領域の節約になる。

近似値を使おう

それほど正確さが問われないなら、低い精度のデータ型を使用する。古いマシンや小規模なマシン、浮動小数点をソフトウェアでシミュレートするマシンでは、倍精度演算より端精度演算のほうが速いことが多い。(doubleではなくfloatを使って時間を節約する）
浮動小数点の結果が表現可能範囲の下限に近づいたときにアンダーフローする際にゼロに切り捨てることによって時間の節約ができる（イメージの場合にはアンダーフローする機能は不要）
整数のsinとcosルーチンを利用することも近似値の使用例となる。

より低級な言語で書き直そう。

プログラム時間のコストがかかるが、低級な言語ほど効率が高くなる傾向がある。C++,Javaのクリティカルな部分をCで書き直したり、インタープリタ用のスクリプトを言語コンパイラで作成したプログラムに書き換えれば、はるかに高速に動作する可能性がある。
　マシンに依存するコードを使って大幅に高速化できることもある。最後の手段で軽率にやってはならない。（移植性が台無し、メンテナンスや修正作業が大変）
アセンブリ言語で記述するのは、ライブラリに埋め込まれる比較的小さな関数。memset,memmove，グラフィックス処理などがその例。高級言語でなるべくきれいに書き、テストで正しく動作することを確認後、アセンブリ言語バージョンの関数をもとの関数を基準にテストをする。バグが発生するのは、移植性のないコードのほうになる。（比較用の実装を作っておくと安心）