まっつーのブログ

本の感想や振り返りなど雑多に書いてます

第5章 プログラム性能の最適化

CS:APP コンピュータ･システム

5章について
この章では、コードの性能を向上させる数多くのテクニックが紹介されていました。
またコンパイラの最適化について知り、どのようなコードが最適化をサポートするのかを理解することができます。
以下まとめです。


プログラムの最適化

最新のコンパイラの性能はますます向上しているが、実行環境に依存するプログラムには弱いため、コンパイラが最適化しやすいコードを書く必要がある。

具体的には、条件分岐や関数呼び出しなどの不要な処理を削除すること。

またアセンブリを見ることで、クリティカル･パスを発見し、実行時間を特定することができる。


最適化コンパイラ

コンパイラはプログラムでどの値が計算され、どう利用されるかを特定するアルゴリズムを持つ。

また利用者が最適化のレベルを指定できる。

例えば gcc -Og を指定すると基本的な最適化が適用される。

これら最適化により性能は向上するが、標準的なデバッガーによるデバッグが困難になることもあるので注意が必要。


保守的な最適化

コンパイラは安全な最適化のみを適用する。

そのため最適化により、結果が異なってしまうリスクがある場合には最適化を行わない。

具体例としては、メモリ･エイリアシングや、副作用を持つ(プログラムの状態を変更する)関数の呼び出しなどが挙げられる。


メモリ･エイリアシング : 2つのポインタが同一のメモリ位置を指していること。

x = 1000, y = 3000;
*q = y;  // 3000
*p = x;  // 1000
t1 = *q; // 1000 or 3000 // 事前に q = &pしているかによって結果が異なる

対策としては、ポインタを restrict で修飾して、が別名を持たないことをコンパイラに指示するという手法がある。


コードレベルの最適化

インライン展開 : 関数のコードを展開(実際のコードに置き換え)し、関数への制御転送をしないようにする手法。


コード移動

// ループの回数分関数が呼ばれる
for (int i = 0; i < strlen(s); i++)

// 前計算する
len = strlen(s);
for (int i = 0; i < len; i++)


不要なメモリ参照の削除

// ループの回数分destにアクセスする
for (int i = 0; i < len; i++) {
    *dest = *dest + acc;
}

// 一時変数に結果を累積する
int acc;
for (int i = 0; i < len; i++) {
    acc = acc + data[i];
}
*dest = acc;

この場合、一時変数を用いて結果を累積することで、dest へのアクセスが1回だけで済む。

ループのたびにメモリから値を読み書きするとコストがかかってしまう。


また累積器を複数もたせるという手法もある。

// 偶奇で2つの累積器を使う
for (int i = 0; i < max; i+=2) {
        even = even + data[i]; 
        odd = odd + data[i+1]; 
}
int res = even + odd;


スーパースカラ

複数の命令を同時にフェッチし、複数の実行ユニットを並列に動作させる。

プログラムの持つ命令レベルの並列性を利用して性能の向上を図るアーキテクチャ。


投機実行

プロセッサは、分岐が進むであろう方向のフェッチとデコード、演算の実行を分岐予測が正しいか分かる前に開始する。

演算は評価されるが、実際に実行すべきと判断されるまでレジスタやメモリを更新しない。

分岐予測が間違っていた場合、分岐の時点に状態をリセットする。


レジスタ関連

レジスタの分類

ループを構成するコードに対して、レジスタを4種に分類できる。

  1. Read-only : 計算するための値として利用されるが、ループ中で更新されることはない。

  2. Write-only : データ移動演算のデスティネーションとして利用される。

  3. Local : 更新かつ利用されるが、イテレーション間に依存しない。

  4. Loop : ソースとデストの両方で利用され、イテレーションで生成された値は別のイテレーションでも利用される。


レジスタ･リネーミング
レジスタを再利用しているために不必要な順序依存性が生じているのを、避ける手法。
他のレジスタを利用して再利用されているレジスタに割り当て、依存を無くすことができる。


レジスタ･スピル

並列実行を行う上で利用可能なレジスタ数を超える場合、スピルが発生する。

スピル : 実行時スタックに割り当てられたメモリ上の領域に一時的な値を格納する。

メモリはレジスタよりも遅いため、コストがかかる。


ループ･アンローリング

ループ命令を展開(アンロール)することで、並列実行可能なコードを増やし高速化を図る手法。

ちなみに浮動小数点加算、乗算は結合的ではないため適用されない。

またGCCは最適化レベル 3 以上で適用してくれるらしい。

// 通常のループ
for (int i = 0; i < 100; i++) {
    free(a[i]);
}

// 展開後
for (int i = 0; i < 100; i+=5){
    free(a[i]);
    free(a[i+1]);
    free(a[i+2]);   
    free(a[i+3]);
    free(a[i+4]);
}


条件付き移動

制御移動はコストがかかるので if-else を使わずに処理する。

void minmax(int a[], int b[], int n)
{
 // if 文で min-maxを代入するよりも効率が良くなる
    for (int i = 0; i < n; i++) {
        int min = a[i] < b[i] ? a[i] : b[i];
        int max = a[i] < b[i] ? b[i] : a[i];
        a[i] = min;
        b[i] = max;
    }
}


write/read依存

同じメモリ位置に対して読み書きを行うことで、依存が生まれ速度低下を引き起こす。

読み書きのメモリ･アドレスが一致する場合は、データのストア、ロードなどもクリティカルパスに関わってくる。


性能向上の4つのテクニック

  1. ハイ･レベルの設計 : 適切なアルゴリズムとデータ構造を選ぶ。

  2. 基本コーディング原則 :コンパイラが関数を効率的なコードを生成できるよう、最適化阻害要因を避ける。

  3. ロー･レベルの最適化 : ハードウェア能力を活用するようコードを構成すること(ループ･アンローリングや複数累積器などの利用)

  4. コードのプロファイル : GPROFなどを利用して情報を得る。


GPROF

GPROFを活用することで、2つの情報が得られる。

  1. 各関数がどの程度CPU時間を費やしているか。

  2. 各関数がどの関数にどの程度呼び出されたか。

gcc -Og -pg test.c
./a.out
gprof a.out # gprofを呼び出して解析する。


感想

これまでは最適化のオプションをつければ、どんなコードでもコンパイラが効率良く展開してくれると思っていました。
実際にはコードの内容がかなり最適化に影響するということが学べて良かったです。
今後は意識的に最適化をサポートするようなコードを書いていこうと思います。
これまでの章と比べ、普段からすぐ使えそうな内容だったので読んでいて特に面白かったです。