C言語でテーブル引きしたら速度が遅くなった

プログラムに悩んでいるものです．

とある画像処理のプログラムを組んでいるのですが，処理が遅くテーブル引きを組んでいます．
この前もこの場を借りて質問しｓｑｒｔ()のテーブル引きは実現したのですが，処理速度が遅くなってしまい原因が分からないので質問させていただきました．
前の質問URL：http://oshiete.goo.ne.jp/qa/7103550.html
前回から修正した現在のプログラムの一部を示します．
ーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーー
void filter(unsigned char* d, short *dx, short *dy, int w, int h)
{
///// テーブル生成 /////
static int c_size = 0;// static 値を保持
static double c_sqrt[1020][1020];
if(c_size != 1020){// 初回呼び出しのみ実行
c_size = 1020;
for(int i=0; i<c_size; i++){// 有りえるすべての値を生成
for(int j=0; j<c_size; j++){
c_sqrt[i][j] = sqrt( (double)(i*i + j*j) );
}
}
}

///// d = sqrt(dx^2 + dy^2) /////
for(int y = 1; y < h-1; ++y){
for(int x = 1; x < w-1; ++x){
double u = (double)dx[y*w+x];
double v = (double)dy[y*w+x];
if(u<0) u=-u;
if(v<0) v=-v;
int val = (int)c_sqrt[(int)u][(int)v] /4;
if(val>255) val=255;
d[y*w+x] = val;
}
}

｝
ーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーー
テーブル引きをしない場合(プログラム省略)はこの関数の処理時間が約9[ms]だったのに対し，上記のプログラムは約15[ms]となってしまいました．
どういう風に修正すれば，テーブル引きの効果が出せるでしょうか?

長い文章を最後までお読みいただきありがとうございます．
ご回答，よろしくお願い致します．

No.5 ベストアンサー 回答者： kmee 回答日時： 2011/11/05 13:11

・添字に使うだけのu,vをわざわざdoubleにする必要はありません。

・値の範囲が0～1020とわかっているなら、 u<0,v<0の処理も必要ありません。
・sqrtだけテーブルにするのではなく、計算結果そのものをテーブルにしてしまえば、ループ内で計算する必要がなくなります。


あと、あくまで予想なのですが

テーブル引きは「いちいち計算するより、計算結果を取ってくるだけの方が速い」という理屈で使うものです。

ところが、最近のCPUなら、浮動小数計算用の回路が付いているので、sqrtくらいだったら相当速く計算できます。
それに対して、メインメモリは、いまや「CPUにとっては遅い」記憶装置となってしまっています。キャッシュに入れば多少高速になりますが、今回のテーブルは1020*1020*sizeof(double)≒8MB、高機能なCPUでもギリギリサイズです。

最初に挙げた対策をしてもそれでも時間がかかるようなら、あなたの実行環境では、メモリアクセスの方が時間がかかるのでテーブル引きには不適切、ということなのでしょう。

この回答へのお礼

ご回答ありがとうございます．
ハードウェア的な知見からのアドバイスは勉強になりました．

お礼日時：2011/12/03 08:36

No.4 回答者： wormhole 回答日時： 2011/11/04 03:09

＞1020*1020回以下ならテーブル引きじゃない方が早いですよ。

上記は「c_sqrtの参照回数の合計が1020*1020回以下なら」ですね・・・

No.3 回答者： Yune-Kichi 回答日時： 2011/11/04 03:01

表を全て埋める必要はあるのですか。

実際にc_sqrtの配列中で値が使われるのはどのくらいの割合でしょうか。
例えば，(h - 1) * (w - 1)が1020 * 1020よりも明らかに小さい場合，
非常に大きな回数だけfilter関数を呼び出さないと初期化のコストを回収できません。

u != 0 && v != 0において，
・c_sqrt[u][v]が0.0であれば計算してc_sqrt[u][v]に代入し，その値をvalとする
・そうでなければc_sqrt[u][v]の値をvalとする
とした方が速くなるかもしれません。
また，この時にu <= vなどの条件付けでsqrtの回数を減らせます。


究極の手段は，別途計算ですが……。
ソースコード中に1020 * 1020の計算結果を貼り付けておけば，
実行時のコストが一気に削減できます。
# 今回の場合，そもそもc_sqrtはdoubleではなくunsigned charでいい気がします。

この回答へのお礼

ご回答ありがとうございました．
参考になりました．

お礼日時：2011/12/03 08:34

No.2 回答者： wormhole 回答日時： 2011/11/04 02:53

#1の方もいわれてますがfilterは実際何回よばれてるのでしょうか？

実行時c_sqrt初期化するのにsqrt()が1020*1020回呼ばれるのですから
1020*1020回以下ならテーブル引きじゃない方が早いですよ。

c_sqrtの内容自体は固定のようですし実行時じゃなく
ソース中に初期値書かれた方がよいのではないでしょうか。

他にも直せるとこは
・u, v, c_sqrtはdoubleの必要がなくintで十分、c_sqrtにいたってはunsigned charで十分
・valを求めるのに必ず4で割るのならc_sqrtには4で割った値を入れとく
じゃないでしょうか。

私なら以下のようにしてc_sqrtのソースを作っておいて、

printf("unsigned char c_sqrt[][] = {");
for (int i = 0; i < 1020; i++) {
printf("{ ");
for (int j = 0; j < 1020; j++) {
int val = (int)(sqrt(i * i + j * j)) / 4;
if (val > 255)
val = 255;
printf("%d,", val);
}
printf("}, ");
}
printf("};\n");

使うときには

d[y*w+x] = c_sqrt[u][v];

で済ますかな。

No.1 回答者： Tacosan 回答日時： 2011/11/04 01:55

呼び出す側の情報がなければ考えられない, ってのは理解できますか?

この関数をどのくらい呼び出しているのですか? どのような引数で呼び出しているのですか?

この回答への補足

ご回答ありがとうございます．
呼び出す側(main文)はWhileループになってます．
呼び出す側で画像の画素データを読み込んで，この関数に渡してます．
この関数は100回くらい呼び出します(画像が100枚)．
呼び出す側では
filter(img.pixel, dx, dy, img.w, img.h);
と宣言してます．
引数に関してですが，img.pixelが関数で出力する画像画素輝度データ，dx，dyがとあるフィルタをX，Ｙ方向にかけた結果画素輝度，img.wとhが画像の幅(=640)，高さ(=480)です．pixelは0~255の値をとり1*307200(=640*480)行列，dx,dyは0~1020の値をとり1*307200行列です．この関数はX,Y方向のフィルタ結果をベクトル積にするものです．
呼び出し回数についてですが，最終的にはカメラ画像を呼び出す形になるので無限回に呼び出すと考えていただけると助かります．
よろしくお願い致します．

補足日時：2011/11/04 02:49