スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

C/C++のプログラム高速化

CATEGORYc / c++

最近、c++ とか触ってないから、 なんかを見るとウズウズする。
yamablo » C/C++のプログラム高速化
C言語、C++言語のプログラム高速化について書いていこうかと思います。 C実践プログラミング、C++実践プログラミングの本(共に、O'REILLY出版)を読んで、その中に乗っていたことを主に書いていきます。

# 別にケチをつけたいわけじゃない >トラックバック先


昔、読んだ記憶はあるけど、もう忘れちゃったなあ >「C実践プログラミング」

一言で言うと「古い」。

小手先のテクニックは知っておくのに越したことは無いのだけれど、コードを読みにくくすることとトレードオフになるが多いので、速くするためにコードをいじるまえの手順が大事(本の趣旨から外れてることは百も承知)。

  1. 素直に正しく作る。それから高速化を考える
    関数呼び出しのコストなんか気にしない。関数にすべきところは関数にする。
    正しく動いた後に、処理を速くすることだけを考えて手を入れる。
    遅い原因は、正しく作られていないから、ということも多い。
    最近 (と言っても、ずいぶん前から) のコンパイラの最適化はかなり頭が良いので、最適化レベルを上げてみて、それで十分ということもよくある。

  2. 手をつける前に、目標を決めておく
    高速化はやってるときりがない。
    「できるだけ速くする」という要求もないわけじゃないけど、普通は、使えるレベルまで速くする、というところに落ち着くはず。
    目標によっては、高速化のやり方も変わってくる(最初から作り直す、という選択肢をとるかどうか)。

  3. むやみやたらと手をつけない
    「処理時間の 80% は、コードの 20% が占める」とよく言われる。
    よく使われるコードを速くすれば、少しの手間で全体を速くすることが出来る。
    そのためには、「よく使われるコードで遅いのはどこだろう」と調べることが肝要。

    ここで初めて、小手先のテクニックを駆使して頑張るのが正道。


というわけで、細かいところについて。

> その他(アルゴリズム・データ構造)

が大事なのは、その通り。勉強(や研究)目的以外で、並べ替えのコードなんか自分で書かない。


は、特に「今どきなあ...」という感じ。
  • 関数をマクロ化
  • 浮動小数点演算をできるだけ使わないように
  • 配列の初期化はポインタを利用
  • 2の累乗
  • register修飾子

もちろん、組込系のプログラムをするときなど通用する場面も無くは無いんだけど。


> 関数をマクロ化
マクロのパラメータを括弧でくくるのは、「マクロの副作用に注意せよ」ってことなんだけど、それをやってもだめなケースはある。例えば、

#define sqr(x) ((x)*(x))

int x, y;
x = 3;
y = sqr(++x);

マクロよりは、関数に inline を指定しておいて、コンパイラの最適化に任せるほうが良い。


> 浮動小数点演算をできるだけ使わないように
浮動小数点演算が、プロセッサで出来なくて、ソフトウェアのライブラリでやってる時代の話。
中途半端に整数演算で代替すると、overflow や underflow が怖い。
お手軽に出来る範囲だと、float は使わないようにする、かな。


> 配列の初期化はポインタを利用
これは、ループの終了判定を減らせば、ちょっと速くなる、ということなんだろうけど、

int mat[5][9];
for (int j = 0 ; j < 9 ; ++j) {
    for (int i = 0 ; i < 5 ; ++i) {
        mat[i][j] = 1;
    }
}
で、j < 9 と i < 5 の回数は、64 回 (あってるかな?)。

int mat[5][9];
int* p = &mat[0][0];
for (int i = 0 ; i < 5 * 9 ; ++i) {
    *p++ = 1;
}
だったら、46 回で済むじゃない、という話。

でも、全体の処理の中で、初期化が実行されるのは、ごく一部。素直に書くに越したことは無い。
整数を 0 や -1 で初期化するのだったら、memset() を使うのが一番速い。


> 2の累乗
こんなこと書いてあったっけ。メモリ配置を考えて、配列のサイズは 2 の累乗にしておけ、っていうことだろうか。
でも、
int data[16];
for (int i = 0 ; i < 10 ; ++i) {
    ...
}
なんてコードは書かないよね。
「2 の...」系だと、
j = i * 2;
よりは
j = i << 2;
の方が速い、というのもあるけど、これもコンパイラの最適化に任せるべきだな。


> register修飾子
これも、いつの時代やねん、って感じ。「通常のPCの場合...」も2個ってことは無いよ。
指定しなくても、コンパイラの最適化がやってくれる。
無駄に長いコードで変数がいっぱい出てくると、最適化が思った通りにいかない、というケースはあるかもしれないけど、正しく作っていれば、こういうコードはあまり出てこないはず。


> ライブラリ関数を使う
その通りなんだけど、アセンブラで書かれているから速いんじゃなくて、コードが練られている(過去の英知の結集)から。


> 読み書きするファイルをバイナリ化
scanf は、C の中でもお勧めできないライブラリ関数のトップを争うやつ。
でも、それは遅いからじゃなくて、エラー処理をきちんとやりにくいから。
動作条件を定義したり、計算結果を書き出すファイルはテキストにするのが普通。
バイナリだと、別のマシンに持ってったときに互換が無いことがある(エンディアンネスで調べて)。
動作中の一時的なデータをファイルに逃がすときはバイナリになるんだろうけど、高速化を気にするときには、バイナリかどうかよりもディスクアクセスを減らすことに気をつける。


> 複雑なループを内側へ
これも書いてあった記憶が無い。
ループのネストを入れ替えができるのであれば、複雑な処理は外側にもってけ(動く回数が少なくなるから)、じゃなくて?


> 要素の交換はポインタの付け替えで

ポイントは、「↑をしよう」じゃなくて↑をするために、「要素の交換をするような配列はポインタの配列にしよう」ってことでしょう。



ああ、久しぶりに頭の中が C になって、楽しかった :-)



「じゃあ、おまえはどうなんだ?」って思うよな、普通。 次回に続く(かもしれない)。
関連記事
スポンサーサイト

C 高速化

0 Comments

Leave a comment

1 Trackbacks

Click to send a trackback(FC2 User)
この記事へのトラックバック
  •  C/C++のプログラム高速化 (続き)
  • あんな記事でも、検索エンジン経由で迷い込んでくる人が、それなりに居るみたいなので、昔を思い出してちょっと書いてみる。 .code_block {display:...
  • 2009.02.25 (Wed) 03:22 | それって食えるのか?
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。