C/C++のプログラム高速化 (続き)

CATEGORYc / c++

あんな記事 でも、検索エンジン経由で迷い込んでくる人が、それなりに居るみたいなので、昔を思い出してちょっと書いてみる。


前にも書いたけど、パフォーマンス改善にいたるまでの手順がとても大事。
  1. 素性正しく作る
  2. デバッグをきちんとやる
  3. パフォーマンスを改善する (必要なら)

    ある程度パフォーマンスを稼がなきゃいけないプログラムを書くなら、妙な Tips を頼るのではなく、正しい設計をするのが、一番大事なこと。
    後で改善するときにも、修正する箇所が少なくてすむことになるので、改善するのもとても楽。

    また、パフォーマンス改善は、コードが汚くなりがちだけど、それは、汚いコードが速い、ということではない
    仕事で、ぐちゃぐちゃのコードを渡されて、とても手を入れる気にならなくて、書き直してみたら速くなった、という経験をした人も多いはずだ ( ゚-゚) トオイメ


    デバッグをした後にパフォーマンス改善をする、というのも大事なこと。
    パフォーマンス改善をするということは、コードに手を入れるわけだから、そのせいできちんと動かなくなることはありがち。
    ソース管理をしているなら、パフォーマンス改善直前のものにタグを付けておいて、いつでも改善前の状態に戻れるようにしておく。


    で、あらためて、パフォーマンスを改善するときの手順。
    1. 最適化レベルを最大にしてリコンパイルする
      ここで満足できたら終了。

    2. 改善の目標値を決める
      仕事でやってるなら必須。趣味でやってるならできる限り、というのもアリかも。

    3. どこが遅いか調べる
      プロファイラを使うか、自分で時間を計ってボトルネックとなるところを絞り込んでいく。

    4. ソースを直す
      やみくもに手を入れるのではなく、ボトルネックとして大きいところから順に手を付けてゆく。

    5. 時間を計る
      目標を満たしてたら終了。満たしてなければ 3. へ。


    改善の仕方は、大きく分けてふたつ、かなあ。

    • 小手先で直す
    • 根本的に直す

    以下、昔を思い出しながら、できるだけ具体的に書いてみる。


    ■小手先で直す

    あまり頭を使わない系。試してみて、効果がなければ元に戻す。
    試してみる対象は、プロファイラの結果を見て、呼び出されている回数が多いところから。
    • inline を使う (c/c++)
    • 引数は参照で渡す (c++)
    • alloca() を使う (c)
    • ファイルアクセスのバッファを増やしてみる (c/c++)
    • float を使わない (c/c++)
    • スコープを考えて、自動変数を使う (c++)
    • STL を使う (c++)
    • 番兵 (c/c++)

    いくつか補足。

    引数は参照で (c++)

    引数で渡すインスタンスの状態が変わるかもしれないので、const を適切に指定する必要がある。
    引数に const をつけるということは、そのクラスのメソッドも const にする必要がある。
    何も考えずに作ってると、結構大変かもしれない。

    alloca() を使う (c)

    動的に配列のサイズを指定したいがために malloc() を使っている場合、もし、寿命が短いなら試してみる価値がある。
    malloc() とペアになっている free() も消していかなければいけないので、malloc() と free() が同じ階層に位置してないような変態なつくりだと、結構大変かも。

    ファイルアクセスのバッファを増やしてみる (c/c++)

    stream 系の関数を使っているなら、setvbuf() で大きな領域を割り当ててあげる。
    c++ なら、fstream.setbuf() 。

    float を使わない (c/c++)

    特殊な場合を除いて、4byte をケチる意味はほとんどない。
    データを保存する領域を節約するために float を採用する場合でも、中間の演算では double を使う。

    スコープを考えて、自動変数を使う (c++)

    やたらめったら new しない。
    java'er にありがち。
    スコープが決まっているものは auto な寿命にする。

    STL を使う (c++)

    STL 全体を把握するのは大変だけど、コンテナ系と iterator は積極的に使ってみる。
    配列のループをポインタのシフトに変えると速くなるんだ、というのは昔から言われているのだけれど、やっぱり可読性が低くなる感があるので、あまり好きじゃない。

    (a) 普通に配列
    
    int v[10];
    for (int i = 0 ; i < 10 ; ++i) {
    	v[i] = 5;
    }
    
    
    
    
    (b) ポインタでずらす
    
    int v[10];
    int* p = &v[0];
    int* end = &v[10];
    while (p != end) {
    	*(p++) = 5;
    }
    
    
    (c) iterator を使う
    
    vector<int> v(10);
    vector<int>::iterator i = v.first();
    while (i != v.end()) {
    	*i = 5;
    }
    
    
    (d) iterator を隠蔽した関数を使う
    
    vector<int> v(10);
    fill(v.first(), v.end(), 5);
    
    
    
    
    

    番兵 (c/c++)

    領域を一つ多めに取って、最後に必ず「真」になる条件を埋め込んでおくと、ループの終了判定を省ける。

    int v[N + 1];
    v[N] = data;
    for (i = 0 ; v[i] != data ; ++i) {
        // NOP
    }
    
    
    if (i == N) {
        ...    // NOT FOUND
    }
    
    ×
    int v[N + 1];
    
    for (i = 0 ; i < N ; ++i) {
        if (v[i] != data)
            break;
    }
    if (i == N) {
        ...    // NOT FOUND
    }
    

    でも、ちょっと時代遅れかも。
    適切にハッシュ関数を作って、データをハッシュ構造で持っておくほうが良い。
    ただ、こういう手があるということは知っておいて損は無い。


    ■根本的に直す


    影響範囲が大きいので、手を付ける前にじっくり考える必要があるもの。

    • 自分でロジックを発明しない (c/c++)
    • ポリモーフィズムを使う (c++)
    • dynamic_cast を使わない (c++)
    • try - catch を狭く使わない (c++)
    • 使ってるメモリサイズを削減する (c/c++)
    • 判定の回数を減らす (c/c++)
    • ループの回数を減らす (c/c++)
    • 結果をキャッシュする (c/c++)
    • replacement new を使う (c++)
    • 条件判定をビット演算で行う (c/c++)


    いくつか補足。

    自分でロジックを発明しない (c/c++)

    ロジックを発明すること自体が目的ではないなら、ライブラリや実績があるコードを利用する。
    例えば、ソート。
    関数のポインタが分からないから、といって qsort() を使わず、自分で組んじゃうのはありがち。
    で、大量のデータを挿入ソートでやっちゃうとか。

    ポリモーフィズムを使う (c++)

    正しくクラス設計ができていれば、同じ判定があちこちに出てくることが少なくなる。
    呼び出し回数が多いメソッドにある if があるなら、クラスを分けることを考える。
    NullObject パターンについても知っておく。

    c の場合には、関数のポインタで同じようなことができるが、関数の inline 化を妨げる場合があるので、常に速くなるとは限らない。

    c++ でも vtable で実装しているわけだから、同じことが言えるが、「素性正しく作る」のが第一なので、クラス設計をゆがめてまで導入するメリットは無い。

    try - catch を狭く使わない (c++)

    try ブロックを抜けるときに、ブロック内の auto なスコープのインスタンスを破棄するための手続きが埋め込まれる。
    これは意外と馬鹿にならないコストなので、細かく try - catch を入れるのではなく、大きな範囲をくくるようにする。
    try - catch を大きな範囲でくくれるようにするには、例外をやたらに送出するようなつくりにしない。
    あくまでも、処理を続行させることが不可能な例外的な場合だけにとどめる。
    細かい条件は、判定するためのメソッドを作って、それを使う。

    try {
    	for (...) {
    		C c = ...
    		c.execute(...);
    		if (c.invalid()) {
    			...
    		}
    	}
    } catch (...) {
    	...
    }
    
    ×
    for (...) {
    	try {
    		C c = ...
    		c.execute(...);
    	} catch (...) {
    		...
    	}
    }
    
    
    
    


    判定の回数を減らす (c/c++)

    最適化オプションでまかなえる部分はあるはずだが、呼び出し回数に応じて試してみる。

    if (x < 0) {	// ループに依存しない判定
    	for (...) {
    			...
    	}
    } else {
    	for (...) {
    		...
    	}
    }
    
    ×
    for (...) {
    	if (x < 0) {	// ループに依存しない判定
    		...
    	} else {
    		...
    	}
    }
    
    
    

    ループ内の処理が短くないと、極端に可読性/保守性が低下することに注意。
    c++ については、ポリモーフィズムを使う、と同意。

    ループの回数を減らす (c/c++)

    二重以上のループがある場合、データ構造を見直すことで、ループの内側にある処理を呼び出す回数を削減できる可能性がある。
    ループの内側にある処理がボトルネックになっている、かつ、ボトルネックの処理の内容自体を見直すことが難しい場合に考えてみる。

    結果をキャッシュする (c/c++)

    実数演算やI/Oアクセスを伴う処理がボトルネックになっている場合に考える。
    全体的な構造を見直すと、二次的な障害を生みやすい。
    c++ で、Proxy パターンを使える場合には、全体への影響を抑えて改善できる余地がある。

    replacement new を使う (c++)

    デストラクタの呼び出しなど、考慮する点がいろいろ多いため、あまり汎用性は無いと思う。
    メモリ割り当てがボトルネックになっている場合に一考の余地あり。

    条件判定をビット演算で行う (c/c++)

    小手先の割には、見直す場合の影響範囲が大きいので、こっちに分類。

    #define MODE_A1    0x01
    #define MODE_A2    0x02
    #define MODE_A3    0x04
    #define MODE_B     0x10
    #define MODE_A3_B  (MODE_A3 | MODE_B)
    
    int mode;
    
    if (mode & MODE_A1) {
    	...
    } else if (mode & MODE_A2) {
    	...
    } else if ((mode & MODE_A3_B) == MODE_A3_B)) {
    	...
    }
    
    
    mode = MODE_A3;
    mode |= MODE_B;         // 同時に指定する
    
    ×
    
    
    
    
    
    
    int a, b;
    
    if (a == 1) {
    	...
    } else if (a == 2) {
    	...
    } else if (b == 1 && a == 3) {
    	...
    }
    
    
    
    
    




    ■別の側面


    そういえば、プロファイラだけでは、ボトルネックの検出はできないのだった。

    • CPU を食ってる
    • CPU を食ってないのに遅い

    後者の場合には、I/O の待ちで遅くなっているので、

    • ファイルアクセスのバッファを増やしてみる (c/c++)
    • 使ってるメモリサイズを削減する (c/c++)
    • 判定の回数を減らす (c/c++)
    • ループの回数を減らす (c/c++)
    • 結果をキャッシュする (c/c++)

    といった辺りを気にしながらボトルネックを探さなければいけない。
    単純に呼び出す回数が多いだけではなく、I/O を伴うコードを気にする。


    書くのに時間をかけた割には、あまり具体的なコードを出せなかったかな。
    最近は、c/c++ を触る機会があまり無く (java がほとんど) て、小手先系はもっとあったような気もするんだが。

    何かの助けになれば幸い >検索エンジンでたどり着いた方




    以下、あまり参考にならないことをいくつか。

    マクロはあまり使わない

    マクロの副作用は何度もはまったことがあるし、何度も経験している割には気がつくのに時間がかかる。
    関数呼び出しのオーバヘッドは無視できないこともあるのだけれど、inline による最適化と、呼び出し回数を削減することでカバーできるので、値置き換え以外のマクロはほとんど使わない。

    アセンブラまで読まない

    こんな短いコードの、どこを最適化すれば良いんだ、と詰まってしまった場合、アセンブラを読んで、手を入れたコードをインラインアセンブラにする、と言う手もある。
    でも、可搬性は落ちるし、可読性も落ちる。

    思い出せない...

    パフォーマンス改善で、代入演算子とコピーコンストラクタを一生懸命作った記憶があるのだけれど、どんな問題があって、どのように効果があったのか思い出せない。
    インスタンスの生成回数にまつわることだったような記憶はあるのだけれど。


    2009-3-10 追記。
    「番兵」と「判定をビット演算で」を追加。

    2009-4-8
    SyntaxHighlighter を使ってみた。
    関連記事
    スポンサーサイト

C c++ 高速化

0 Comments

Leave a comment