プログラミングテクニックについて（C言語）．

質問

こんにちは．私は，大学でアプリケーションソフトをつくる作業を研究の一環としてやっています．C言語でコードを書いているのですが，計算処理の高速化を
実現したいと切に願っております．

例えば，以下のように2つの関数main とTest,があるとします．
そのとき,Testは計算結果を返さないとします．

#define MAX 100

void Test(i,j data);

int main(void)
{
double data[MAX][3]
for (i = 0; i <= MAX; i++ ){
for (j = 0; j <= MAX; j++){
//
Test(i,j data);
}
}
return 0;
}

この場合，毎回Test関数を呼ぶたびにdata配列を指すポインタを
渡し，さらにTest()関数内に定義されているローカル変数用のメモリ領域も
確保されます．

ということは，処理を高速化するためには
なるべくTest関数内の変数を
できるだけへらせばいいのでしょうか？

みなさんがプログラムを組むときに留意されているテクニックを
教えて頂きたいです．
できればVC++ver6.0でのデバックツールをどのように
つかってバグフィクスしておられるのかうかがいたいです．
以上、よろしく御願い致します．

回答No.5

terra5 · ベストアンサー

>この適材適所ともいうべき能力を身につけるには，
>やはり「経験」でしょうか？

アルゴリズム的なところは、計算量の問題ですから、
きちんと理詰めでいけば計算できるとは思いますし、
知識でもカバーできるとは思いますが。
何度もやっていれば、いちいち調べないでも
すぐに頭に浮かぶのが経験ですしょうか。

>大きいサイズの場合，グローバル変数として確保した方がよい
>ときいたことがあるのですが，これもなんともいえませんか？

言えないと思います。
おそらくスタック上に取られるauto変数だと、スタックサイズの制限により、
あまりに大きなエリアは取れれない可能性はありますが。

その場合でも、メモリをグローバルにするか、malloc()を使うか、また、場合によっては共有メモリを使うかとか、
場合によると思います。
もっとも、高速化より目的にあった・・の意味合いが強いとは思います。

>実際，関数を呼ぶときには，その呼ばれた関数内の変数も呼ばれる，
>すなわち，スタックの繰り返しですよね？
>ということは，あまり大きいサイズをつまないようにした方が
>いいと知識がない私は考えてしまうのですが…

初期化が必要がない変数なら,まとめて取れますから、
速度的には数は影響しないでしょう。
また、popも関数の戻りにスタックポインタを復元すれば
いいだけですから、通常は一命令でしょう。
たとえば、
f() { int a,b,c,d,e;
...
}
g() { int a;
...
}
では、手間は同一です。
って、実際はコンパイラ、CPUによるんでしょうが。

関数呼び出しの場合だと,手間がかかるのは
呼び出す前のレジスタの保存の方でしょう。

これはある程度,コンパイラの生成するコードと、
それを実行するCPUのアセンブラレベルの知識か、
それを調べることが必要でしょう。

ですが、やはりあまりすすめられないですね。
通常、それ以前の一般的な部分,アルゴリズムでの
高速化に及ばないですし。
処理の高速化は通常はアルゴリズムの改良です。
もし、処理にAPIやシステムコールが使われるなら,
重いAPIは極力使わないとかの工夫も含みます。

ところで、ダイアログの応答5秒とありますが、
本当に時間がかかる処理なら通常はマルチプロセスやマルチスレッドにすると思いますが。

ところで、配列をポインタにすることで高速化するという
話が出てますが,
その程度のことは割と以前からコンパイラの最適化ではやっていると聞いてます。
最適化のレベルにもよると思いますが、Cコンパイラの最適化としてはかなり初歩的な部分でしょう。

お礼

terra5 様，度重なるアドバイスありがとうございます．
＞その場合でも、メモリをグローバルにするか、malloc()を使うか、また、場合に
＞よっては共有メモリを使うかとか、
＞場合によると思います。
＞もっとも、高速化より目的にあった・・の意味合いが強いとは思います。

上記の意味は，リスト構造のような可変のデータをとりあつかうときは，
malloc()を使うといったところでしょうか？
しかし，「目的」に応じて，メモリーをグローバルにとる，または，
共有メモリにするといったアプローチは，私にとってちょっと
難しいところです．一例を指し示して頂けると分かりやすいのですが…

＞通常、それ以前の一般的な部分,アルゴリズムでの
＞高速化に及ばないですし。
＞処理の高速化は通常はアルゴリズムの改良です。

アルゴリズムの改良ですか…うーーん，がんばって改良してみます．
といっても，ここの関数の処理ルーチンについて再検討から始めたいと思います．

＞ところで、配列をポインタにすることで高速化するという
＞話が出てますが,
＞その程度のことは割と以前からコンパイラの最適化では
＞やっていると聞いてます。
＞最適化のレベルにもよると思いますが、
＞Cコンパイラの最適化としてはかなり初歩
＞的な部分でしょう。

このようなコンパイラに関する知識も乏しいので，勉強ですね．

terra5様はじめ，さまざまな方から意見を賜り，息詰まっていたキモチに
モチベーションが戻りました．ここで改めてお礼を述べたいと思います．
有り難う御座いました．なにかまた不明瞭な点があったらこの掲示板を
利用させて頂くのでそのときは，どうか宜しく御願い致します．
では．

回答No.4

ranx

terra5さんが百点満点の回答をして下さったので、後は蛇足と知りつつ、付け加えさせていただきます。
大学の研究の一環ということですので、長時間かけて解を出すようなプログラムもあるのでしょうね。
例えば60分で答を出すプログラムがあったとします。データをスタックに置くかヒープに置くか、
配列のアドレス計算や関数呼び出しのオーバーヘッドをどうやって減らすか、といったようなことを
一所懸命に考えてプログラムを修正したとします。そうした高速化では、55分くらいで処理が終わる
ようにできれば、ある意味で大成功だと思うのです。が、aki2001さんはそれで満足できますか？

それよりも、もっと根本的に処理を見直すことです。例えば、ご質問のプログラムではMAX×MAX=10000回
Test関数が呼び出されています。もし、ある条件の時にはTest関数を呼ぶ必要は無いということを見つけ
られれば、処理時間はぐっと短縮できる可能性があります。
例えば、jがiより大きい場合だけで良かったんだということになれば、
　for(i=0;i<=MAX;i++){
　 for(j=0;j<=MAX;j++){
　 if(i<j){
　 Test(i.j,data);
　 }
　 }
　}
で良いわけです。Test関数の呼び出しは半分近くに減ります。
　for(i=0;i<MAX;i++){
　 for(j=i+1;j<=MAX;j++){
　 Test(i,j,data)
　 }
　}
とすれば、もう少し速くなります。
terra5さんの「適切なアルゴリズム」の一つの例と考えて頂いて良いと思います。
（もちろん、適切かどうかは実際の状況によります。）

あと、前の回答で余計なことを書いてしまったかなと反省しているのですが、
double (*pdata)[3]; はdouble三つの要素から成る配列へのポインタです。
あとは int *p; とした場合に *p と p[0] が同じデータを示すということから類推して下さい。
くれぐれも見ずらいコーディングにならないように。

補足

ranx様，ご返事ありがとうございます．

＞aki2001さんはそれで満足できますか？
すみません，やはり処理の高速化にこだわりたいです．
人間はダイアログのＯＫなどを押して5秒以上たつと
おそいと感じるようなのです．
実際自分のアプリはintractiveなスピードではないです（泣）．
私の研究は処理の高速化に大きく関わっています．
ある人にいわせると「クソプログラム」といわれます．
従って，どうしてもそのスタック、ヒープの効率的な使用法、
または、関数のオーバーヘッド等について御教示して頂きたいのです．
もちろん自分でも勉強しますが，ネットサーフィンなどで
情報の取捨選択に時間を費やすよりも
できればranx氏が参考にしている適切なＵＲＬ等を
教えて頂ければと思っているのですが…．
「楽してるんじゃないか！」といわれそうですけれど…

****************************************************************
Test関数が呼び出されています。もし、ある条件の時にはTest関数を呼ぶ必要は無いということを見つけ
られれば、処理時間はぐっと短縮できる可能性があります。
例えば、jがiより大きい場合だけで良かったんだということになれば、
　for(i=0;i<=MAX;i++){
　 for(j=0;j<=MAX;j++){
　 if(i<j){
　 Test(i.j,data);
　 }
　 }
　}
で良いわけです。Test関数の呼び出しは半分近くに減ります。
　for(i=0;i<MAX;i++){
　 for(j=i+1;j<=MAX;j++){
　 Test(i,j,data)
　 }
　}
とすれば、もう少し速くなります。
terra5さんの「適切なアルゴリズム」の一つの例と考えて頂いて良いと思います。
（もちろん、適切かどうかは実際の状況によります。）
****************************************************************
たしかに上記考え方は，重要であると思います．
アルゴリズムとデータ構造をどのように構築するかとなやんでばかりで
ソースコードをかく手がとまってしまう．といった日々が私の場合多いです．
また，やっと考えたデータ構造でも処理がおそくふんだりけったりです．

****************************************************************
あと、前の回答で余計なことを書いてしまったかなと反省しているのですが、
double (*pdata)[3]; はdouble三つの要素から成る配列へのポインタです。
あとは int *p; とした場合に *p と p[0] が同じデータを示すということから類推して下さい。
****************************************************************
わかりました．ポインタ重要なのでこの際きちんとまなび直します．

御手数をお掛けしますが，御叱咤でもかまいません，アドバイスを
よろしく御願い致します．

回答No.3

papataku

高速化するには、まず今やりたい処理を再検討することです。
現在：データ個数分ループ－＞関数で１データ処理
ここで問題なのは、１データ処理単位ずつで関数呼び出しが存在することです。関数呼び出しのオーバーヘッドがありますので、高速化のためには、「複数データ高速一括処理」ルーチンの作成の必要があります（引数は、配列のポインタ？）。さらにデータを配列から持ってくる場合にabc[i]のような引っぱり方をすると遅くなる（ｉからデータ列の存在するアドレス計算を内部的にやっている為）ので最初からポインタ計算型でコーディングするといいでしょう（ranxさんの（２）のようなかんじ）。
＜さらに＞
本当に限りなく高速化したいのなら、ＶＣでアセンブラ表示に変更してＣ－＞アセンブラ（マシン語）へどう落ちるかのチェックが必要です。ＣＰＵのマニュアルには、そのマシン語がどのくらいの時間で実行されるか記述してあるので、これから逆算できます。

補足

papataku 様，お返事ありがとうございます．

＞関数呼び出しのオーバーヘッドがありますので、
＞高速化のためには、「複数データ高速一括処理」ルーチンの作成の必要があります

関数呼び出しのオーバーヘッドとは具体的には，PC内部でどのようなことが
起きるのでしょうか？
上記のように，i,jのfor文内があればTest（）関数は，メモリ上では，pushするpopを繰り返すことで
呼ばれ，処理の遅延を招くのでしょうか？？

また，「複数データ高速一括処理」というのをもう少し具体的に例を挙げて御教示して頂けませんでしょうか？

＞（引数は、配列のポインタ？）。
はい，そうです．
2次元配列 data[MAX][3] の先頭アドレスを指すポインタをTest関数に渡しています．

＞さらにデータを配列から持ってくる場合にabc[i]のような引っぱり方をすると遅くなる（ｉからデータ列の存在するアドレス計算を内部的＞にやっている為）ので最初からポインタ計算型でコーディングするといいでしょう（ranxさんの（２）のようなかんじ）。

うーーん，ここがちょっと私の技量では，分からなくて頭をひねってしまうところなのです．
もう少し勉強してみます．

＞本当に限りなく高速化したいのなら、ＶＣでアセンブラ表示に変更して
Ｃ－＞アセンブラ（マシン語）へどう落ちるかのチェックが必要です．

papatakuさんがおっしゃるアセンブリ表示とは，
VCでデバックツールをメニューから選択すると表示される16進数表示のメモリダンプですか？

＞ＣＰＵのマニュアルには、そのマシン語がどのくらいの時間で実行されるか記述してあるので、これから逆算できます。

できれば逆算の仕方がのっているURLを教えて頂きたいのですが…

長々と，書いてすみません．また，こんなタコ(タコよりひどいかも…)に
適切なしかも丁寧な解説ありがとうございます．
まだわからない消化しきれていない箇所が多々ありますので
どうか宜しく御願い致します．

回答No.2

terra5

ケースによりますが、小手先の高速化は
不要と思います。
最近のコンパイラの最適化はかなり優秀らしいのと、
CPUの速度の速いこともあって、下手な細工は
プログラムの可読性の低下を招くだけですし、
最適化のさまたげになるようなコーディングなら、
却って悪化します。

まずVC++6.0を使うような環境なら、そのレベルの
心配はまず不要でしょう。

>ということは，処理を高速化するためには
>なるべくTest関数内の変数を
>できるだけへらせばいいのでしょうか？

一概には言えません。
例えば、ローカル変数はまとめて確保しますから、
手間としてはよほど大きいサイズをとらないと
変化しません。
逆に、変数が局所的であるほど最適化が有効に
働きますから、変数の使い方によっては
かえって高速の場合もあります。

高速化はまず適切なアルゴリズムとデータ構造です。
これが悪いとその程度のことは無意味です。

バグを無くすにはまず読みやすいプログラミングです。

お礼

terra5様，お返事ありがとうございます．

>一概には言えません。
>例えば、ローカル変数はまとめて確保しますから、
>手間としてはよほど大きいサイズをとらないと
>変化しません。
>逆に、変数が局所的であるほど最適化が有効に
>働きますから、変数の使い方によっては
>かえって高速の場合もあります。

この適材適所ともいうべき能力を身につけるには，
やはり「経験」でしょうか？

>高速化はまず適切なアルゴリズムとデータ構造です。
>これが悪いとその程度のことは無意味です。

大きいサイズの場合，グローバル変数として確保した方がよい
ときいたことがあるのですが，これもなんともいえませんか？

実際，関数を呼ぶときには，その呼ばれた関数内の変数も呼ばれる，
すなわち，スタックの繰り返しですよね？
ということは，あまり大きいサイズをつまないようにした方が
いいと知識がない私は考えてしまうのですが…

>バグを無くすにはまず読みやすいプログラミングです。
うーーん，↑非常に大切ですよね．
それと，最低限のコメント文の併記ですよね．ついつい忘れがちです．

なにかと丁重なアドバイスを頂きありがとうございました．
今後とも宜しく御願い致します．
では．

回答No.1

ranx

ケースバイケースで何とも言えないと思いますけどね。
（高速化より構造化・プログラム見易さが重要な場合もあるし。）
とりあえず、お尋ねのプログラムについて言えば、
(1)　Test()をマクロ化する。
　　関数呼び出しのオーバーヘッドを減らせます。ただし、Test()の内容によっては
　できない場合もあるでしょうし、コーディングに気をつけないとバグの元になる
　場合もあります。
(2)　i,j のいずれかがdata配列の引数として使われるのなら、
　　double (*pdata)[3], (*plast)[3];
　　のような変数を作って
　　for(pdata=data[0],plast=pdata+MAX;pdata<=plast;pdata++){
　　 for (j=0;j<=MAX;j++){
　　 Test(pdata, j);
　　 }
　　}
　　のようにする。
いずれにしても、Test()内の処理で時間を食っているなら、そちらの高速化の方が
重要になりますね。

お礼

さっそくのアドバイスありがとうございます．
＞高速化より構造化・プログラム見易さが重要な場合もあるし
そうですね，コーディングが見やすいとの指摘も最もですね．
double (*pdata)[3], (*plast)[3];
ところで↑は，double型の配列のポインタ配列ですか！？？？
記述して頂いたコードを見る限り私が書いたコードは
2次元を扱っていますが，ranx様の場合，data[0]としておりますが…．
すみません、もう少し御指導御願い致します．