c-lang:最適化

ループ展開（loop unrolling）

（そのうち）

条件分岐を減らすために行います。

code:cpp

for(i = 0; i < 4; i++)}

}

という式があった場合、コレを展開してしまい、

code:cpp

としてしまうような動作です。

インライン関数

（そのうち）

呼び出しコスト

テーブル参照

（そのうち）

ハンドアセンブル

（そのうち）

レジスタ変数

（そのうち）

グローバル変数

（そのうち）

固定小数点演算

（そのうち）

変数領域の使い回し

関数の前半で使用しているが途中から参照もしていない、という変数があった場合、途中からその変数を削除してしまいます。

コレにより、メモリ効率を向上させ、変数をレジスタに割りつける可能性を向上させます。

定数式の除外

code:cpp

a = v * w * x * y * z;

b = v * w * x * y;

c = v * w * x;

という式を次のように展開して、演算回数を減らします。

code:cpp

int X = v * w * x;

a = X * y * z;

b = X * y;

c = X;

値が変化しない参照の除外

ループ内部の定数式をループの外に配置します。コレにより演算回数を減らします。

code:cpp

for( n = 0; n < 8; n++){

}

という式は次のように展開されます。

code:cpp

int X = b * c * d;

for( n = 0; n < 8; n++){

}

値の変化しない演算をループの外に配置してしまうのです。

一般にコンパイラは式の評価順序まで変えるような最適化は行いませんので、このようなテクニックは有効です。

また、評価順序を変えてしまうコンパイラは意図に反したバグも生成することがありますので注意が必要です。

ifを減らせ

ifは条件分岐を行うための文です。

一般にコレはジャンプ命令にコンパイルされます。

非常に基本的な制御文ですが、このようなときにはifを使うべきではありません。

これをifを使って書くとこのようになります。

code:cpp

if(A==0){

B=1;

}else{

B=0;

}

このような文であれば三項演算子 ? を使うべきです。

code:cpp

B=(A==0) ? 1 : 0;

ifは条件分岐の文なのでどうしても分岐してしまうのですが、三項演算子の場合、ただの演算ですから分岐を前提としたコードを吐き出しません。

さらにここで出てきたxはたいていレジスタを使用しますので更に効率がいいコードになります。

クロック削り

（そのうち）

原則

1. システム構造

2. アルゴリズムとデータ構造

3. アルゴリズムチューニング（アルゴリズムの調整）

4. データ構造の再構成

5. コードチューニング

6. ハードウェア

少々のスピードアップが必要なら、最善のレベルをひとつ選んで考える。

非常に大きなスピードアップが必要なら、すべてのレベルを考える。

コードチューニングのルール

時間節約のためにメモリを使う

データ構造の拡張

データへの操作に情報を付け加えたり、構造内の情報を変えることで、アクセスしやすくし、実行時間を減らすことが出来る。

計算した結果を保持する

時間のかかる計算は、一度だけにして、後はその結果を保持しておいて、実行時間を減らせる。

関数による計算結果をテーブルに入れ、必要なときに参照することで、再計算せずに済むことが多い。

キャッシュを使う

もっとも繁雑に使われるデータは、もっともアクセスしやすいところにおく。

怠け者式評価

実際に必要になるまで評価（計算）をしないことで、不要な計算をさけることが出来る。

メモリ節約のために時間を使う

詰め込み

データを圧縮して保持すると、データの出し入れに時間がかかるが、使用するメモリを減らすことができる。

インタープリタ

ループ

ループの外に出す

ループの中で何度も実行し直すより、ループの外に出したほうが良い．

テスト（比較）はまとめる

内側のループは、できる限り簡単なテスト（比較）にする。

ループの終了条件のチェックを別の方法でできないか考えてみるべきである。

ループを展開する

ループを展開することで、ループインデックスを変更していく操作を省くことができる。

代入に注目したループ展開

無条件分岐をなくする

ループの結合

論理

代数を使う

単調関数のショートカット

テストの順番を変える

論理関数を前もって計算しておく

ブール変数をなくす

プロシージャ（関数）のルール

関数の階層的呼び出しをなくする

よくある場合を利用する

コルーチン

再帰関数の書換え

並列処理

表現

コンパイル時の初期化

代数を使う

繰り返す部分をなくする

ペアをまとめる

ワードの並列性を利用する