From: EGUCHI Osamu <eguchi@...>
Date: 1997-09-26T17:40:40+09:00
Subject: [ruby-dev:546] Re: optimize (Re: Assigne to special variable)

えぐち です

----------
> 件名 : [ruby-dev:537] Re: optimize (Re: Assigne to special variable)
> 
> まつもと ゆきひろです

> |まったく別の場所では、Bignum の四則や比較といった重いところを、
> |「if 文の算術式化」などで、少しチューニング出来そうな気がします。
> 
> これ，具体的にはどんなのでしょう？

仮パッチつけました。

bigsub()
	+ ループの底の if を同義の演算に変形
	  パイプラインのストールを防ぐため
	+ 減数をひき切った後は純コピーループに移る
	  桁上がりの監視で簡単に判別可能です

bigadd()
	+ リザルトの０クリアを省略
	+ 全加算→桁上がのみ→純コピーの順に変形
	  桁数の比較で順序を整合できます

binmul()
	+ ループの底の if を同義の演算に変形
	+ 不要なメモリ（配列要素）への書き戻しの除去	

bigdivmod()
	+ 桁数一致時も最上位桁の比較で分子＜分母検知
	  これ以上深入りして比較するとコストアップ
	+ ループの底の if を同義の演算に変形
	+ 不要なメモリ（配列要素）への書き戻しの除去	

sample/pi.rb の外周の while TRUE を for i in 1..1000
とかにすると、約倍速になったことがわかります。
演算の比率や数値の大きさにより効果が異なると思います。

あと、Bignum の sizeof(*digits) を２から４にすると
倍以上速くなるのはわかっているのですが、
	影響で動かなくなるコードが多い
ので見送った方がいいです。

＃
昔々アセンブラやマイクロコードでライブラリかいてたときに
こんな事ばっかりしてたです。
いまの RISC や Pentium って剥き出しのパイプラインを
意識するとむちゃむちゃ速くなる事があるんです。
＃うぅん、、思いっきり低水準だ！

まだ、テストが完全ぢゃないのでマージしないでください。
＃この手のテストってやっかいですよね。

＃新旧両方の演算ルーチンをもって ruby を作って比較しながら
＃走らせるとか、、比較が腐ってたりして、、

以下、そのパッチです。

--- ../ruby-1.0-970919/bignum.c	Tue Jun  3 15:27:01 1997
+++ bignum.c	Thu Sep 25 11:41:41 1997
@@ -9,6 +9,7 @@
 ************************************************/
 
 #include "ruby.h"
+#include <stdio.h>
 #include <ctype.h>
 #include <math.h>
 
@@ -503,35 +504,20 @@ bigsub(x, y)
     z = (struct RBignum*)bignew(x->len, (z == 0)?1:0);
     zds = BDIGITS(z);
 
-    i = x->len;
-    while (i--) zds[i] = BDIGITS(x)[i];
-
-    i = 0; num = 0;
-    do {
-	num += (long)zds[i] - BDIGITS(y)[i];
-	if (num < 0) {
-	    zds[i] = num + BIGRAD;
-	    num = -1;
-	}
-	else {
-	    zds[i] = BIGLO(num);
-	    num = 0;
-	}
-    } while (++i < y->len);
-    if (num) {
-	while (num && i < x->len) {
-	    num += zds[i];
-	    if (num < 0) {
-		zds[i++] = num + BIGRAD;
-		num = -1;
-	    }
-	    else {
-		zds[i++] = BIGLO(num);
-		num = 0;
-	    }
-	}
+    for (i = 0, num = 0; i < y->len; i++) { 
+	num += (long)BDIGITS(x)[i] - BDIGITS(y)[i];
+	zds[i] = BIGLO(num);
+	num = BIGDN(num);
+    } 
+    while (num && i < x->len) {
+	num += BDIGITS(x)[i];
+	zds[i++] = BIGLO(num);
+	num = BIGDN(num);
     }
-
+    while (i < x->len) {
+	zds[i++] = BDIGITS(x)[i];
+    }
+    
     return bignorm(z);
 }
 
@@ -541,10 +527,8 @@ bigadd(x, y, sign)
     char sign;
 {
     struct RBignum *z;
-    USHORT *zds;
     long num;
     UINT i, len;
-
     if (x->sign == (y->sign ^ sign)) {
 	if (y->sign == sign) return bigsub(y, x);
 	return bigsub(x, y);
@@ -557,27 +541,24 @@ bigadd(x, y, sign)
 	len = y->len + 1;
     }
     z = (struct RBignum*)bignew(len, sign==y->sign);
-    zds = BDIGITS(z);
-
-    i = len;
-    while (i--) zds[i] = 0;
-    i = y->len;
-    while (i--) zds[i] = BDIGITS(y)[i];
 
-    i = 0; num = 0;
-    do {
-	num += (long)zds[i] + BDIGITS(x)[i];
-	zds[i++] = BIGLO(num);
-	    num = BIGDN(num);
-    } while (i < x->len);
-    if (num) {
-	while (i < y->len) {
-	    num += zds[i];
-	    zds[i++] = BIGLO(num);
-	    num = BIGDN(num);
-	}
-	BDIGITS(z)[i] = num;
+    if (x->len > y->len) {
+        struct RBignum* t = x; x = y; y = t;
+    }
+    for (i = 0, num = 0; i < x->len; i++) {
+	num += (long)(BDIGITS(x)[i]) + BDIGITS(y)[i];
+	BDIGITS(z)[i] = BIGLO(num);
+	num = BIGDN(num);
+    }
+    while (num && i < y->len) {
+	num += BDIGITS(y)[i];
+	BDIGITS(z)[i++] = BIGLO(num);
+	num = BIGDN(num);
+    }
+    while (i < y->len) {
+	BDIGITS(z)[i++] = BDIGITS(y)[i];
     }
+    BDIGITS(z)[i] = num;
 
     return bignorm(z);
 }
@@ -649,20 +630,20 @@ big_mul(x, y)
     z = bignew(j, x->sign==y->sign);
     zds = BDIGITS(z);
     while (j--) zds[j] = 0;
-    do {
-	j = 0;
-	if (BDIGITS(x)[i]) {
-	    do {
-		n += zds[i + j] + ((unsigned long)BDIGITS(x)[i]*BDIGITS(y)[j]);
-		zds[i + j++] = BIGLO(n);
-		n = BIGDN(n);
-	    } while (j < y->len);
-	    if (n) {
-		zds[i + j] = n;
-		n = 0;
-	    }
+    for (i = 0; i < x->len; i++) {
+	unsigned long dd = BDIGITS(x)[i]; 
+	if (dd == 0) continue;
+	n = 0;
+	for (j = 0; j < y->len; j++) {
+	    int ee = n + dd * BDIGITS(y)[j];
+	    n = zds[i + j] + ee;
+	    if (ee) zds[i + j] = BIGLO(n);
+	    n = BIGDN(n);
 	}
-    } while (++i < x->len);
+	if (n) {
+	    zds[i + j] = n;
+	}
+    }
 
     return bignorm(z);
 }
@@ -681,7 +662,7 @@ bigdivmod(x, y, div, mod)
 
     yds = BDIGITS(y);
     if (ny == 0 && yds[0] == 0) num_zerodiv();
-    if (nx < ny) {
+    if (nx < ny	|| nx == ny && BDIGITS(x)[nx - 1] < BDIGITS(y)[ny - 1]) {
 	if (div) *div = INT2FIX(0);
 	if (mod) *mod = bignorm(x);
 	return;
@@ -692,7 +673,7 @@ bigdivmod(x, y, div, mod)
 	z = big_clone(x);
 	zds = BDIGITS(z);
 	t2 = 0; i = nx;
-	while(i--) {
+	while (i--) {
 	    t2 = BIGUP(t2) + zds[i];
 	    zds[i] = t2 / dd;
 	    t2 %= dd;
@@ -740,24 +721,21 @@ bigdivmod(x, y, div, mod)
 	if (q) {
 	    i = 0; num = 0; t2 = 0;
 	    do {			/* multiply and subtract */
+		int ee;
 		t2 += (unsigned long)yds[i] * q;
-		num += zds[j - ny + i] - BIGLO(t2);
-		if (num < 0) {
-		    zds[j - ny + i] = num + BIGRAD;
-		    num = -1;
-		}
-		else {
-		    zds[j - ny + i] = num;
-		    num = 0;
-		}
+		ee = num - BIGLO(t2);
+		num = zds[j - ny + i] + ee;
+		if (ee) zds[j - ny + i] = BIGLO(num);
+		num = BIGDN(num);
 		t2 = BIGDN(t2);
 	    } while (++i < ny);
 	    num += zds[j - ny + i] - t2; /* borrow from high digit; don't update
*/
 	    while (num) {		/* "add back" required */
 		i = 0; num = 0; q--;
 		do {
-		    num += (long) zds[j - ny + i] + yds[i];
-		    zds[j - ny + i] = BIGLO(num);
+		    int ee = num + yds[i];
+		    num = (long) zds[j - ny + i] + ee;
+		    if (ee) zds[j - ny + i] = BIGLO(num);
 		    num = BIGDN(num);
 		} while (++i < ny);
 		num--;