August 07(Fri), 2009
Rubyでフィボナッチ数列の演算が遅い問題についてのその後の考察。@解決編
@Python編？何それおいしいの？(ぁ
ついに解決！
ずっと、ここ一連のエントリで、Rubyの多倍長演算の遅さについて嘆いてきたわけですが、何度かささださんからアドバイスをいただきつつも、ついにボトルネックを発見し、解消することができました。
ボトルネックの正体。
過去のエントリでは、Pythonとほとんど同じ処理だよ？おかしいね？とか言ってたわけですが、かなり煮詰まってきて、静的にコードを眺めてるだけじゃどうにもいかなくなったので、実行時のプロファイルをとってみることにしました。
使用したプロファイラはgprofです。
Ubuntu 9.04で、
make CFLAGS=-pg
とかして、(cygwinでは-pgオプションつけるとmake通らなかった＞＜)
適当に、スクリプトを実行、
その後、
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-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とかも、文脈をみながら適宜、ポインタを保持してやると性能改善が見込めるかと思います。
Permalink | コメント(4) | トラックバック(7) | 00:04 
