読者です 読者をやめる 読者になる 読者になる

Rubyでフィボナッチ数列の演算が遅い問題についてのその後の考察。@Ruby編

問題解決には至らず。
以前の記事
各言語でのフィボナッチ数列に関する3つのアルゴリズムでの速度比較 - CanI’s Diary
からの続編です。
rubyさんが残念だった理由を検証してみました。
※本当は、RubyPythonの両方の多倍長演算のソースの解説をして、似てるけど速度違うね、おかしいね。って流れにしようと思っていたのですが、Rubyの解説だけで、かなりの長さになってしまった(&疲れた(ぁ)ので、Pythonの多倍長演算のソースは、後日@Python編として解説します。
というわけで、今回は、Rubyでの多倍長演算の実装についての解説です。


今回は、特に差が顕著だった処理、fib_linerについて見てみました。
該当ソースは以下ですね。


RubyPython

def fib_linear(n)
  a, b = 0, 1
  n.times do
    a, b = b, a+b
  end
  return a
end

def fib_linear(n) :
  a, b = 0, 1
  for i in range(n) :
    a, b = b, a+b
  return a

行ってる処理は、アバウトに考えると

  1. 変数a, bを定義し、0, 1をunpack代入
  2. n回反復
    • a, bにb, a+bをunpack代入
      • a+bを演算
  3. aをreturn

って感じですかね。


そこで、この段階を踏んでそれぞれの処理時間を計測してみました。
すると、以下の表のような感じでPython処理速度の差が現れました。

単位 : secs Loop Unpack Calc Total
20000 0.003000145 0.005999907 0.039000109 0.046
40000 0.010000145 0.007999886 0.093 0.125
60000 0.011999813 0.015000103 0.186000036 0.227
80000 0.018000124 0.015999916 0.240999893 0.411
100000 0.020999958 0.022999989 0.521000092 0.604

グラフにすると、各処理が占める割合はこんな感じ


演算で時間食ってますね。pythonより。


はっきり言って、System.Int32.MaxValue以下はほとんど差がつかないので、多倍長演算の実装部が速度差の原因だと思います。
Rubyの加算の演算は以下のように定義されています。

Ruby

bignum.c
line : 1484

VALUE
rb_big_plus(VALUE x, VALUE y)
{
    switch (TYPE(y)) {
      case T_FIXNUM:
	y = rb_int2big(FIX2LONG(y));
	/* fall through */
      case T_BIGNUM:
	return bignorm(bigadd(x, y, 1));

      case T_FLOAT:
	return DBL2NUM(rb_big2dbl(x) + RFLOAT_VALUE(y));

      default:
	return rb_num_coerce_bin(x, y, '+');
    }
}

今回は、整数を扱うので、VALUE yの型としては、T_FIXNUMか、T_BIGNUMしかありえません。
実際は、rb_int2bigで、多倍長整数にしてからfall throughしてるようですね。
bignormとかはとりあえず無視して、bigaddを参照してみましょう。

bigadd

line : 1434

static VALUE
bigadd(VALUE x, VALUE y, int sign)
{
    VALUE z;
    BDIGIT_DBL num;
    long i, len;

    sign = (sign == RBIGNUM_SIGN(y));
    if (RBIGNUM_SIGN(x) != sign) {
	if (sign) return bigsub(y, x);
	return bigsub(x, y);
    }

    if (RBIGNUM_LEN(x) > RBIGNUM_LEN(y)) {
	len = RBIGNUM_LEN(x) + 1;
	z = x; x = y; y = z;
    }
    else {
	len = RBIGNUM_LEN(y) + 1;
    }
    z = bignew(len, sign);

    len = RBIGNUM_LEN(x);
    for (i = 0, num = 0; i < len; i++) {
	num += (BDIGIT_DBL)BDIGITS(x)[i] + BDIGITS(y)[i];
	BDIGITS(z)[i] = BIGLO(num);
	num = BIGDN(num);
    }
    len = RBIGNUM_LEN(y);
    while (num && i < len) {
	num += BDIGITS(y)[i];
	BDIGITS(z)[i++] = BIGLO(num);
	num = BIGDN(num);
    }
    while (i < len) {
	BDIGITS(z)[i] = BDIGITS(y)[i];
	i++;
    }
    BDIGITS(z)[i] = (BDIGIT)num;

    return z;
}

軽く全体を眺めてみましょう。
みた感じ、いわゆる筆算方式のようです。(キャリー伝搬型とでも言うのかな?)
signは符号処理のようですが、今回は負とかになり得ないので関係なさそうですね。


処理の流れを、例として分りやすくFIXNUMの543+9876を用いて考えてみます。
BIGNUMでも桁数が増えるだけでやってることは変わりません。
まず、bigaddが呼び出されると、
line : 1484

    VALUE z;
    BDIGIT_DBL num;
    long i, len;

が定義されます。
VALUE zは、加算の結果の値。
BDIGIT_DBL numは、繰り上がりを保持したり、各桁の加算の結果を保持したりと色々使われます。BDIGIT_DBLは、defines.hで定義され、処理系によって異なりますが、大体、unsigned longとか、unsigned long longとかになると思ってもらえれば差し支えないです。
long i, lenは、for文で使ったり、多倍長整数のlengthを保持したりします。


signは今回、関係ないので飛ばして、
次に、
line : 1458

    if (RBIGNUM_LEN(x) > RBIGNUM_LEN(y)) {
	len = RBIGNUM_LEN(x) + 1;
	z = x; x = y; y = z;
    }
    else {
	len = RBIGNUM_LEN(y) + 1;
    }
    z = bignew(len, sign);

です。
ここでは、xとyの桁数を比べて、より大きい方が、yに来るように調整されてます。
RBIGNUM_LENは、多倍長整数のlengthを求めるマクロです。ruby.hとかに定義されてます。
で、y(より大きい数)の桁数+1の桁数の多倍長整数を生成し、zに代入しています。
少し考えるとわかりますが、y>xが成り立つとき、xとyがいかに大きかろうと、y*10>x+yは必ず成り立ちますね。ここで桁あふれを防いでいるわけです。


次にこの処理。
line : 1467

    len = RBIGNUM_LEN(x);
    for (i = 0, num = 0; i < len; i++) {
	num += (BDIGIT_DBL)BDIGITS(x)[i] + BDIGITS(y)[i];
	BDIGITS(z)[i] = BIGLO(num);
	num = BIGDN(num);
    }


ここでは、このような感じで、xの桁数までのx,y各桁の和を計算しています。
xとyのi桁目の和をnumに足して、zのi桁目とします。
繰り上がりがある場合は、numに保持して、次周に持ちこします。
BIGLOとか、BIGDNとかはマクロで、ビット演算をして、それぞれ、1の位と10の位の値を求めます。
BDIGITSもマクロで、ruby.hに定義されています。これは、要するに、多倍長整数の各桁の数を要素とした配列を返します。
次は、ここ。
line : 1473

    len = RBIGNUM_LEN(y);
    while (num && i < len) {
	num += BDIGITS(y)[i];
	BDIGITS(z)[i++] = BIGLO(num);
	num = BIGDN(num);
    }


ここで、繰り上がりがあり、かつ、yの桁数がxの桁数より多い場合の残りの桁について計算されてます。
yの桁がない桁(ここでは、5桁目)への繰り上がりは、次の処理で解消されます。
(i < lenがfalseだからね。)



line : 1479

    while (i < len) {
	BDIGITS(z)[i] = BDIGITS(y)[i];
	i++;
    }
    BDIGITS(z)[i] = (BDIGIT)num;

    return z;


最後に、繰り上がりがなくてそのまま流れてきた場合(num == 0)はそのまま代入、繰り上がりの処理後、i < lenがfalseになって流れてきた場合は繰り上がりを代入して、計算を終了します。
最後に、計算結果である、VALUE zを返してbigaddの処理は終了です。



bignorm

bigaddで演算が終わると、bignormの引数に渡されます。
bignormが何をやってるかと言うと、要するに、確保した多倍長整数の最上位の桁が0になってしまった場合の0の処理です。
時間がかかりそうな処理とかしてなさそうなので割愛したいと思います。

まとめ

  • Ruby多倍長整数の加算処理
    • rb_big_plus
      • FIXNUMは、BIGNUMに変換する。
      • bignorm
        • bigadd
          • 筆算方式(キャリー伝搬型?)にて値を計算
      • 結果をreturn


こんな感じですかね。
特に無駄そうな処理とか見つかんなかったですけど…
次回、@Python編に続きます!
Pythonさんも、筆算方式なんだよね…