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

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

Programming Ruby

@Python編?何それおいしいの?(ぁ
ついに解決!
ずっと、ここ一連のエントリで、Rubyの多倍長演算の遅さについて嘆いてきたわけですが、何度かささださんからアドバイスをいただきつつも、ついにボトルネックを発見し、解消することができました。

ボトルネックの正体。

過去のエントリでは、Pythonとほとんど同じ処理だよ?おかしいね?とか言ってたわけですが、かなり煮詰まってきて、静的にコードを眺めてるだけじゃどうにもいかなくなったので、実行時のプロファイルをとってみることにしました。


使用したプロファイラはgprofです。
Ubuntu 9.04で、

make CFLAGS=-pg

とかして、(cygwinでは-pgオプションつけるとmake通らなかった><)
適当に、スクリプトを実行、

./ruby hoge.rb

その後、

gprof ruby gmon.out

とかしてあげると、Cレベルでのプロファイリングが可能です。


1.8.7と、1.9.1でのfib_linerの結果はこんな感じでした。

Ruby 1.8.7

Flat profile:

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls   s/call   s/call  name    
 91.59      2.07     2.07   299780     0.00     0.00  bigadd
  2.65      2.13     0.06   300011     0.00     0.00  rb_eval
  2.65      2.19     0.06   300005     0.00     0.00  rb_yield_0
  0.44      2.20     0.01   903630     0.00     0.00  rb_newobj
  0.44      2.21     0.01   599838     0.00     0.00  obj_free
  0.44      2.22     0.01   599561     0.00     0.00  rb_type
  0.44      2.23     0.01   300017     0.00     0.00  ary_new
  0.44      2.24     0.01   300005     0.00     0.00  massign
  0.44      2.25     0.01        1     0.01     0.01  rb_gc_call_finalizer_at_exit
  0.44      2.26     0.01                             rb_yield_values
..................................................................................

Ruby 1.9.1

Flat profile:

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls   s/call   s/call  name    
 92.90      3.40     3.40   299778     0.00     0.00  bigadd
  1.09      3.44     0.04   300072     0.00     0.00  vm_exec_core
  0.55      3.46     0.02   900218     0.00     0.00  vm_push_frame
  0.55      3.48     0.02   610226     0.00     0.00  rb_sourceline
  0.55      3.50     0.02   300000     0.00     0.00  invoke_block_from_c
  0.27      3.51     0.01   610580     0.00     0.00  rb_safe_level
  0.27      3.52     0.01   610225     0.00     0.00  rb_sourcefile
  0.27      3.53     0.01   603467     0.00     0.00  rb_vm_get_sourceline
  0.27      3.54     0.01   599312     0.00     0.00  rb_big_resize
  0.27      3.55     0.01   308984     0.00     0.00  vm_xmalloc
..........................................................................

※詳細なログは、以下。


bigaddが、1.8.7では、2.07secsだったのに対し、
1.9.1では、3.40secsとかなり遅くなってますね。
そこで、DFを使い、その二つの差分をみていくこことします。

bignum.c


左が、1.9.1、右が1.8.7のものです。
これを、見ると基本的に変更されているのは、RBIGNUM_LEN等のマクロだと分ります。
それらのマクロが定義されているのは、ruby.hです。

ruby.h


なんか、右は、一面の灰色で、左はいちめんのなのはなですね(ぁ


ここ辺りの変更は、調べてみるとどうやらメモリの節約のためのようです。
[ruby-dev:31689] optimize small bignum space - Tanaka Akira - org.ruby-lang.ruby-dev - MarkMail


が、ここの辺気になりませんか?
line : 751

#define RBIGNUM_LEN(b) \
    ((RBASIC(b)->flags & RBIGNUM_EMBED_FLAG) ? \
     (long)((RBASIC(b)->flags >> RBIGNUM_EMBED_LEN_SHIFT) & \
            (RBIGNUM_EMBED_LEN_MASK >> RBIGNUM_EMBED_LEN_SHIFT)) : \
     RBIGNUM(b)->as.heap.len)
/* LSB:RBIGNUM_DIGITS(b)[0], MSB:RBIGNUM_DIGITS(b)[RBIGNUM_LEN(b)-1] */
#define RBIGNUM_DIGITS(b) \
    ((RBASIC(b)->flags & RBIGNUM_EMBED_FLAG) ? \
     RBIGNUM(b)->as.ary : \
     RBIGNUM(b)->as.heap.digits)

三項演算子を使っています。今までは、ただ単に、RBIGNUM(b)->lenとかを参照してたので、ほんの僅かですが、確かに処理は増えているようです。


そこで!gprofとかでプロファイリングするために、bigaddで使われているマクロを全て、それぞれ個別関数化しました!


もうログとかは割愛しますが、最大のボトルネックは、BDIGITSでした。(calls 717256350とかなので、塵も積もれば山となるですね。)

bignum.c

line : 27

#define BDIGITS(x) (RBIGNUM_DIGITS(x))

ruby.c

line : 757

#define RBIGNUM_DIGITS(b) \
    ((RBASIC(b)->flags & RBIGNUM_EMBED_FLAG) ? \
     RBIGNUM(b)->as.ary : \
     RBIGNUM(b)->as.heap.digits)

見事に三項演算子のところです。
bigadd中でも、複数回参照され、桁数が増えるにつれ線形的に、参照回数が増加します。


でも、仮に、bが、constantな定数の場合(一回も変更されないの意)、(RBASIC(b)->flags & RBIGNUM_EMBED_FLAG)の値は、一意に決定されるはずです。
そして、bigadd中のx, yは、bigadd内においては、途中から定数になる(一回も変更されない)のです!
(※途中からというのは、仮にxの桁数がyの桁数より多い場合は、xとyは反転するから。)


そこで、x, yが定数になった時点で、x_digits, y_digitsを宣言し、以後はそれを使うこととしました。
改良版のbigaddのソースは以下。

bigadd++

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);

    /*xとyの各桁の数字が保持されている配列へのポインタを直接保持*/
    BDIGIT *x_digits = BDIGITS(x), *y_digits = BDIGITS(y);

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

    return z;
}

ベンチマーク

例のfib.rbを使ってbigaddとbigadd++を比べてみたいと思います。

実行環境

  • OS : Windows Vista Ultimate 32bit
  • CPU : Core 2 Duo P8600@2.4GHz
  • Mem : 4GB (OS認識 : 3.12GB程度)
  • Ruby
  • on Cygwin(makeも./configureも遅くてイライラしました(ぁ)

結果

単位 : secs ruby 1.9.1-p273 ruby 1.9.1-p273++
fib_liner(20000) 0.068 0.053
fib_liner(40000) 0.225 0.161
fib_liner(60000) 0.473 0.324
fib_liner(80000) 0.813 0.537
fib_liner(100000) 1.241 0.831


確実に早くなってますね!
こういうグラフとかにすると、より違いが明確かな?
今回は、bigaddにしか適応してませんが、他のBDIGITSとかも、文脈をみながら適宜、ポインタを保持してやると性能改善が見込めるかと思います。