スピードアップ

プログラムを書いてて、気になるのは実行速度。ひとつの問題を解決するとき、答えが同じであるなら、より速い解答方法が好まれる。そこでプログラムのコーディングの仕方で、どう実行速度が変わってくるのかを検証します。ただし、ここに書かれてあることが常に真実とは限りません。CPUによっては「遅い」と書いた方が速いこともありえます。ですので、ここにあるプログラムをご自身の環境で実際に動かされることをお勧めします。鵜呑みにはしないことが大切です。

その１〜基本編〜

まず、実行速度をあげたいのなら無駄な処理を省くことです。これは何も故意に無駄な処理を入れたつもりがなくても起こります。実際の例として、次のコードを示します

 1 : #include <stdio.h>
 2 : #define W 8
 3 : 
 4 : int main(void)
 5 : {
 6 :   int i;
 7 :   int amount = 0;
 8 : 
 9 :   for (i = 0; i < 1000; i++) {
10 :     amount += i * W;
11 :   }
12 : 
13 :   printf("合計：%d\n", amount);
14 : 
15 :   return 0;
16 : }
17 : 

このプログラムは「iが0から999までのi*W」のシグマを求めて表示しているだけです。しかし、これ無駄があります。たとえば自分で手計算する場合を思い出してみてください。毎回毎回「i*W」をせずに「iのシグマをとった後で」最後にWをかけても一緒のはずです。単にWをくくり出すだけです。プログラムで書くと

 1 : #include <stdio.h>
 2 : #define W 8
 3 : 
 4 : int main(void)
 5 : {
 6 :   int i;
 7 :   int amount = 0;
 8 : 
 9 :   for (i = 0; i < 1000; i++) {
10 :     amount += i;
11 :   }
12 :   amount *= W;
13 : 
14 :   printf("合計：%d\n", amount);
15 : 
16 :   return 0;
17 : }
18 : 

となります。前者のコードでは、乗算が合計で1000回行われていますが、後者では１回で済んでいます。計算結果はまったく同じです（計算誤差がなければ）。基本的に乗算や除算は、他の演算に比べて計算コストが高い、つまり計算に時間をくいますので、計算を省けるなら省いたほうが明らかに早くなります。

さて、これは基本中の基本です。誰もが守るべきでしょう。ただ、あまりにもコードの可読性が下がってしまうような場合は考え物です。可読性をとるか実行速度をとるかはケースバイケースかと思います。

蛇足ですが、こんなプログラムは普通書きません。このプログラムでは何回動かしても同じ3996000という結果が得られます。それだったら、わざわざ実行毎に書くのではなく、3996000という値自体を覚えておけばいいだけの話です。ま、そんなプログラム書く人はいないでしょうが・・。

だからといって、たとえば「sin関数」の返り値をすべて記憶するなんてことは実質的に不可能ですし、余計に遅くなってしまうかと思います（ただし、範囲が絞れていたりする場合は効果覿面）。メモリの無駄にもなりますし。やはりケースバイケースなのでしょう。

その２〜多重ループ〜

これもやはり基本的なことですが、多次元配列を多重ループでまわす場合

 1 : #include <stdio.h>
 2 : #define W 100
 3 : #define H 200
 4 : 
 5 : int main(void)
 6 : {
 7 :   int x, y;
 8 :   int array[W][H];
 9 :   for (x = 0; x < W; x++) {
10 :     for (y = 0; y < H; y++) {
11 :       array[x][y] = 0;
12 :     }
13 :   }
14 : 
15 :   return 0;
16 : }
17 : 

８行目のように二次元配列を宣言して、９〜１３行目のようにfor文をまわした場合と、

 1 : #include <stdio.h>
 2 : #define W 100
 3 : #define H 200
 4 : 
 5 : int main(void)
 6 : {
 7 :   int x, y;
 8 :   int array[W][H];
 9 :   for (y = 0; y < H; y++) {
10 :     for (x = 0; x < W; x++) {
11 :       array[x][y] = 0;
12 :     }
13 :   }
14 : 
15 :   return 0;
16 : }
17 : 

というふうにfor文をまわした場合、どちらが速いでしょうか？　結果から言うと、（たいていの環境では）前者のコードの方が速く処理が終わります。これは配列がどういう形でメモリ上に確保されているかを考える必要があります。

その３〜関数型プログラミング〜

次のふたつのプログラムは同じ結果を出力します。

 1 : #include <stdio.h>
 2 : 
 3 : int main(void)
 4 : {
 5 :   int i, amount = 0;
 6 :   for (i = 1; i <= 1000; i++) {
 7 :     amount += i;
 8 :   }
 9 :   printf("%d\n", amount);
10 : 
11 :   return 0;
12 : }
13 : 

 1 : #include <stdio.h>
 2 : 
 3 : int sigma(int n)
 4 : {
 5 :   if (n == 1) return 1;
 6 :   return ( sigma(n-1) + n );
 7 : }
 8 : 
 9 : int main(void)
10 : {
11 :   int amount = 0;
12 :   amount = sigma(1000);
13 :   printf("%d\n", amount);
14 : 
15 :   return 0;
16 : }
17 : 

前者のプログラムは、見慣れた書き方かと思います。後者は「関数型プログラミング」といわれるパラダイムで書かれたものです（勘違いしてるかも）。この関数型プログラミングでは、関数内部で変数の書き換えを一切行いません（場合にもよると思うが）。ですので、3〜7行目のsigma関数内部では、変数の値を比較することはあっても代入するようなことをしていません。

この関数型プログラミングの効用は、一度初期化した変数の値は一切変化することはないので、バグつぶしが容易になり、コンパイラによる最適化が容易に行えるなどがありますが、ここでは省きます。

しかし、処理速度の点ではどうなのでしょうか？　一般的に言って、関数呼び出しはコストが高いです。たとえば引数をスタックに積んだり、関数から帰るときのアドレスを覚えていなければならないからです（実際はメモリシーク、つまりJMP命令のコストが高い）。結果、関数型プログラミングは実行速度の面では、遅くなってしまいます。同様に再帰的な処理を関数でやるのも実行速度の面では遅くなります（単にwhileなんかでループするほうが早い）。

その４〜不可逆〜

音声画像データの圧縮には大きく２つの方法が存在しています。ひとつは、圧縮した音声画像データが、ふたたび元通りに戻る・・という可逆圧縮。もうひとつが、圧縮した音声画像データが元通りにはならない、不可逆圧縮という方法です。元通りに戻らないなら意味がないように思えますが、音声や画像データの中には人間には聞き取れない音域や色などが存在している場合が多く、それらを削ることで圧縮率を高めています。

さて、これと同じでプログラムの実行速度も可逆だけでなく不可逆の最適化が行えるのではないかと（個人的に）思っています。たとえば、倍精度浮動小数点数（double値）と単精度浮動小数点数（float値）の演算を行うとすると、多くの場合、単精度の方が実行速度は速いです。音声や画像の場合と同じく、精度を犠牲にしているわけです。

また、何も浮動小数点を使うだけでそもそも計算速度は遅いのです。そこで固定小数点演算というものが考えられます。ようは、小数点の位置を固定してしまうというやり方です。固定さえしてしまえば、整数演算と何ら変わりないので演算が飛躍的にアップするというものです。これは現在C標準委員会で言語拡張およびライブラリ拡張が行われている最中です（詳細はOpen Standardsをご覧ください）が、現状でも、整数型を固定小数点だと思って演算をすることは不可能ではないですが、処理的には固定小数点を使っていないので結局、処理速度は変わらないかと思います。

結局のところ、処理速度は環境に依存していることがわかってもらえたかと思います（ほんとに？）。こういった最適化というものは本来、プログラマの仕事であって、プログラマの仕事ではないと思います（意味不明）。コンパイラなどを作成するプログラマの仕事であると同時に、そこに関わらないプログラマの仕事ではないからです。たとえば大規模プロジェクトでは可読性を一番に気にするべきですが、どうしても処理速度やメモリ効率を気にしてしまいます。だからといって過度に処理速度を気にしたプログラムを書くと一気に可読性が失われてしまいます。
　そういう意味では、今回のこの「ひとりよがり」記事は意味がありません。知っておいて特になるかならないかは、まさしく環境依存なわけです。長々と書いてしまったので、これで終わり。

Comments are welcome! We can be reached at whoinside_reshia@hotmail.co.jp
2005/05/06 03:05:14 UTC