プログラムの高速化について

[マサキ]

いま授業で「プログラムの実行結果を変えずに処理を高速化する」ということを実験しています。
これは当たり前のことですが、自分としてはwhile文やfor文による無駄な繰り返しをなくしたりすれば処理が早くなるのではないかと思いました。
この他にはどのようにすれば処理速度が向上するのか全然わかりません。
例えば標準関数のfgetcやfscanfといったように用いる関数によって処理速度は変わってくるものなのでしょうか？
処理の高速化にはどのような事が関連しているのでしょうか？

一応授業で扱ったプログラムも添付しておきます。
これはあるppm形式の画像をラプラシアンフィルタにかけ、新たな画像を作成するといったプログラムです。
今回はこのプログラムの高速化を図るわけですが
①画像のためのメモリは動的に確保する　
②画像のサイズは変えない
③結果画像が変わらない
という三つの制約があります。

どんな些細な事でも構いません。何かアドバイスよろしくお願いします。

[toyo]

コンパイラのオプションで -O3 を指定する
というのは反則ですか

[たかぎ]

まずは処理系を明確にしてください。
次に、プログラム中のどの部分に一番時間がかかっているのかを調べてください（大体予想はつきますが）。
話はそれからです。

[マサキ]

＞toyoさん
コンパイル時に　－O2ならば使用しています。
説明不足でしたが、コンパイル＝＞実行の仕方は指定されていて

gcc -Wall -O2 ファイル名
time ./a.exe 処理を行いたい画像のファイル名　5.0

です


＞たかぎさん
すいません。説明不足ですよね.....
WINDOWS上でCygwinを用いて実行しています。
やはりグレースケール画像作成・ラプラシアン計算の部分が一番時間がかかっていると思うのですが...

[ibis]

普通は標準関数で言うとscanf、fscanf、printf、fprintfは遅いです。

コンパイラに最適化させる場合は、プログラマの手でソースを過剰に最適化してはいけません。
ループや定数の扱いなどは、コンパイラの最適化でも十分だったりしますので。
でも根本的にアルゴリズムを変えるような最適化(例えばprintfをputsに置き換えるとか)であれば、積極的にすべきですけど。
細かいところを自力で最適化したい場合は、アセンブラコードに変換してからですかね。

・・・というのは受け売りなんですがｗ

[たかぎ]

第一印象では、一番遅そうな箇所はwrite_ppm_csq_memでした。
fwriteは、内部で排他制御を行っているため、結構オーバーヘッドが大きいはずです。そのような関数を1バイト書き込むごとに呼び出すのはよくありません。
putc_unlockedに置き換えてもよいのですが、（POSIX準拠ではありますが）非標準関数になってしまうので、いったんメモリ上でデータを作ってから一気に書き込んだ方が高速になる可能性があります。

あとは、配列の添え字計算も時間がかかりそうです。
laplasian関数内のkernelは、[3][3]ではなく、無駄なようでも[3][4]にした方が若干高速になります（3だとと、添え字の計算に乗算が必要になるため）。
それ以外は、-Sオプションを付けてコンパイル結果を確認し、配列の処理がうまく最適化されていない場合は、手作業で修正してください。

[たかぎ]

コンパイル結果を調べてみましたが、配列の添え字に関しては十分最適化がかかっているようです。
改善の余地があるとすれば、回数の少ないループを開いてしまうことと、浮動小数点演算をなくすことぐらいです。

例えば、laplasianの

for(i=-1;i<=1;i++)
	for(j=-1;j<=1;j++)
	   val += gray[g+i][r+j]*kernel[i+1][j+1];

の部分は、ループの回数も固定なので、開いてしまえそうです。

また、make_gray_imageの

gray[g][[/url]=(UCHAR)(tmp/3.0+0.5); /* 平均値を四捨五入 */

の部分は、

gray[g][[/url]=(UCHAR)((tmp*10/3 + 5)/10); /* 平均値を四捨五入 */

の方がよいかもしれません。

[マサキ]

返事が遅くなって申し訳ありませんでした。
＞ibisさん
やはりscanf、fscanf、printf、fprintfなど、遅い関数は存在するんですね。
ありがとうございました。

＞ たかぎさん
なるほど。アドバイスありがとうございます。
それではさっそくこれらを参考にプログラムの修正に入っていこうと思います。
新たなプログラムができましたら一応添付しておきます。

[マサキ]

とりあえず修正版のプログラムが完成したので添付しておきます。
今回の主な改善点は以下のようなものです。
①関数を直接入力する（関数呼び出しをなくす）
②ループ処理の内容を開いた形で記述
③ループ処理を行う場合はなるべくダウンカウンタで行う
④浮動小数点演算をなくす

のようなものです。
たしかに、たかぎさんの言ったようにプログラムを修正したら処理が早くなりました。ありがとうございました。
また、元のプログラムで作成した画像と修正後のプログラムで作成した画像をcmpコマンドを使って確かめたため、処理後の画像が変わってしまっている事はないと思います。

ここで更なる疑問なのですが、
#defineを使うよりも、直接入力した方が多少なりとも高速化が図れるのでしょうか？
なぜアップカウンタよりもダウンカウンタの方が処理が早くなるのでしょうか？
[3][3]ではなく[3][4]にした方がよいとありましたが、「３だと添え字の計算に乗算が必要になる」とはどういう意味でしょうか？
今回の場合画像のサイズが960×1280と決まっていたので、画像コピーなどのループ処理は少なくとも960*1280回以上行うということになります。そこで大げさな話ですが、やはりこのような場合でもfor文やwhile文による処理を行うよりも一つ一つの場合（960*1280個以上のパターン）を延々と書いた方が処理は早くなるのでしょうか？

質問ばかりですみません。

[マサキ]

先ほど貼り忘れました。

[ibis]

defineマクロはコンパイル時に展開されるので、実行時の速度には影響は無いです。

CPUの特性上、「x==y」「x!=y」よりも「x==0」「x!=0」の方が速いです。
アップカウンタは前者で、ダウンカウンタは後者ですから。

多次元配列のアドレスは乗算によって求められます。
ただし、整数どうしの乗算で「x*pow(2,y)」は「x<<y」に最適化できますから、乗算せずに済む場合もあります。
どちらの計算も同じ結果になりますが、後者の方が速いです。
「x*4」は「x*pow(2,2)」と等しいので「x<<2」に変換できますが、「x*3」ではそうはいきません。
それが3と4の違いです。

[たかぎ]

> ①関数を直接入力する（関数呼び出しをなくす）

これはちょっとやりすぎですね。
せめてインライン関数にする程度にとどめておきましょう。

> ④浮動小数点演算をなくす

bairituが5.0だと決まっているのであれば、これも整数にできそうです。
汎用性と効率はトレードオフですので、高速化のために汎用性を捨てるのはやむを得ません。

> そこで大げさな話ですが、やはりこのような場合でもfor文やwhile文による処理を行うよりも一つ一つの場合> （960*1280個以上のパターン）を延々と書いた方が処理は早くなるのでしょうか？

これもやりすぎです。
長いループを開いてしまうと、キャッシュのヒット率が低下するなどの理由でかえって遅くなります。

[マサキ]

＞ibis さん
なるほど。だからダウンカウンタの方が速いんですね。
つまり終了条件のチェックがダウンカウンタの方が速いということですよね。
ありがとうございました。

＞たかぎ
float型をint型に直したらけっこう時間速くなりました。
ありがとうございます。

インライン関数なんてものが存在したんですね？w
恥ずかしい事ながらこの存在を始めて知りました。
やはりまだまだ未熟者ですね。これからも頑張っていきたいと思うので、また何か躓いたと時は是非よろしくお願いします。