再帰関数と最適化

最大公約数を求める方法に再帰を用いるやりかたがありますが、
別にこれぐらいならwhileでループするやり方でもできるわけで、
関数を呼び出すオーバーヘッドを考えれば、whileのほうが早いんじゃないの？
と思って、コンパイルしてみたら、あんまり差がなかった。
どういうことなの・・・
原因は最適化オプションをつけていたことにあった。

実験用コード

#include <stdio.h>
#include <time.h>
#include <stdlib.h>

int gcd(int a,int b){return b?gcd(b,a%b):a;}
int gcd2(int a,int b){while(b){int t=a;a=b,b=t%b;}return a;}

#define RAND_TABLE 10000
#define LOOP 3000

int main(void){
	clock_t c1,c2;
	unsigned long seed = 0x12345678;
	int rand_table[RAND_TABLE];
	int result[RAND_TABLE-1];
	int i,loop;
	double tmp = 0;
	puts("start");
	puts("initialize table...");
	
	srand(time(NULL));
	for(i=0; i<RAND_TABLE; ++i){
		rand_table[i] = (int)(((rand() / ((double)RAND_MAX+1.0)) * 4294967295.0) - 2147483648.0);
	}
	
	puts("gcd...");
	srand(seed);
	c1=clock();
	for(loop=0; loop<LOOP; ++loop){
		for(i=1; i<RAND_TABLE; i++){
			result[i-1] = gcd(rand_table[i],rand_table[i+1]);
		}
		tmp += result[(int)((rand() / ((double)RAND_MAX+1.0)) * (RAND_TABLE-1))];
	}
	
	c2=clock();
	printf("gcd =>clock: %d, tmp: %f\n",c2-c1, tmp);
	tmp = 0;
	
	puts("gcd2...");
	srand(seed);
	c1=clock();
	for(loop=0; loop<LOOP; ++loop){
		for(i=1; i<RAND_TABLE; i++){
			result[i-1] = gcd2(rand_table[i],rand_table[i+1]);
		}
		tmp += result[(int)((rand() / ((double)RAND_MAX+1.0)) * (RAND_TABLE-1))];
	}
	
	c2=clock();
	printf("gcd2=>clock: %d, tmp: %f\n",c2-c1, tmp);
	tmp = 0;
	
	puts("end...");
	
	return 0;
}

randを使って乱数を10000個とっているのは、いろんな値に対して最大公約数を求めるため。
tmpは最適化されないためのダミー。
最適化するコンパイラは使われない変数を見つけると容赦なく切り捨ててくる。
いちいちprintfしてるのも、tmpを使うことで最適化の対象から逃れるため。
resultの配列の値を使ってtmpに加算することで、最適化によるresultの駆除を逃れている。
同じseed値で発生させた乱数を使うので、最大公約数を求める関数が同じように機能するのであればtmpの値はどちらも同じ結果になるはず。
ベンチマークのほかに、代替関数としてのテストも兼ねている、と。
もっときれいにならんかったのか。

最適化なし

start
initialize table...
gcd...
gcd =>clock: 5671, tmp: -662173943.000000
gcd2...
gcd2=>clock: 4829, tmp: -662173943.000000
end...

最適化あり(-O2)

start
initialize table...
gcd...
gcd =>clock: 3812, tmp: -549190513.000000
gcd2...
gcd2=>clock: 3813, tmp: -549190513.000000
end...

どうしてこうなった・・・

最適化ありの場合、ほとんど同じで、実行時の負荷による誤差ぐらいの差しかない。
最適化なしはwhileのほうが早く処理できている。

デバッガでコードを眺めてみる。
最適化なしは本当にソース通りのバイナリを作ってくれてるけど、
最適化ありは関数は最初の呼び出しだけで、内部で再帰呼び出ししてなかった。
最大公約数を求める関数をコンパイラが最適化した処理の結果は以下のコード。
開始は0x004014B8からで、EAXにはa, ECXにはbが入っている。
またbが0の場合は、0の除算を行うことになってしまうので、この処理は行われない。

004014B4  |> 89C8  ||MOV EAX,ECX             ; EAX=ECX
004014B6  |. 89D1  ||MOV ECX,EDX             ; ECX=EDX
004014B8  |> 99    ||CDQ                     ; EAXの符号ビットでEDXを埋める
004014B9  |. F7F9  ||IDIV ECX                ; eax/ecxの結果, EAXに商, EDXに余り
004014BB  |. 85D2  ||TEST EDX,EDX            ; TEST命令は論理積を取る。ゼロフラグを取るため。
004014BD  |.^75 F5 ||JNZ SHORT null.004014B4 ; ゼロフラグが立ってなかったら、0x004014B4にJump。

CDQ命令は、EAXの符号ビット(n<0=1, n>=0=0)でEDXのビットを全部埋めるらしい。
TEST命令の　TEST EDX,EDX は他にやりようがなかったんだろうか？
アセンブリ言語わかんないから他にどんな命令があるかわからんけども。
とりあえず、最適化なしで使われてた再帰処理が全くない（CALL命令がない）

再帰を用いてクイックソートした場合とかもこんな感じに再帰をせずにすむように最適化されるんだろうか。
それとも処理が単純の場合に限るのかな。今回の場合、関数呼び出したら即return文があるぐらいだし。