Rubyでフィボナッチ数列の演算が遅い問題についてのその後の考察。diaryこの広告は、90日以上更新していないブログに表示しています。2009-08-07Rubyでフィボナッチ数列の演算が遅い問題についてのその後の考察。Ruby@Python編?何それおいしいの?(ぁついに解決!ずっと、ここ一連のエントリで、Rubyの多倍長演算の遅さについて嘆いてきたわけですが、何度かささださんからアドバイスをいただきつつも、ついにボトルネックを発見し、解消することができました。過去のエントリでは、Pythonとほとんど同じ処理だよ?おかしいね?とか言ってたわけですが、かなり煮詰まってきて、静的にコードを眺めてるだけじゃどうにもいかなくなったので、実行時のプロファイルをとってみることにしました。使用したプロファイラはgprofです。gmon.outとかしてあげると、Cレベルでのプロファイリングが可能です。1.8.7と、1.9.1でのfib_linerの結果はこんな感じでした。vm_xmalloc..........................................................................※詳細なログは、以下。1.8.71.9.1bigaddが、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なんか、右は、一面の灰色で、左はいちめんのなのはなですね(ぁここ辺りの変更は、調べてみるとどうやらメモリの節約のためのようです。RBIGNUM(b)->as.heap.digits)三項演算子を使っています。今までは、ただ単に、RBIGNUM(b)->lenとかを参照してたので、ほんの僅かですが、確かに処理は増えているようです。そこで!gprofとかでプロファイリングするために、bigaddで使われているマクロを全て、それぞれ個別関数化しました!もうログとかは割愛しますが、最大のボトルネックは、BDIGITSでした。717256350とかなので、塵も積もれば山となるですね。RBIGNUM(b)->as.heap.digits)見事に三項演算子のところです。bigadd中でも、複数回参照され、桁数が増えるにつれ線形的に、参照回数が増加します。RBIGNUM_EMBED_FLAG)の値は、一意に決定されるはずです。yは、bigadd内においては、途中から定数になる(一回も変更されない)のです!(※途中からというのは、仮にxの桁数がyの桁数より多い場合は、xとyは反転するから。y_digitsを宣言し、以後はそれを使うこととしました。改良版のbigaddのソースは以下。z;}ベンチマーク例のfib.rbを使ってbigaddとbigadd++を比べてみたいと思います。0.831確実に早くなってますね!こういうグラフとかにすると、より違いが明確かな?今回は、bigaddにしか適応してませんが、他のBDIGITSとかも、文脈をみながら適宜、ポインタを保持してやると性能改善が見込めるかと思います。00:04Rubyでフィボナッチ数列の演算が遅い問題についてのその後の考察。7u51)気ままに更新再開します。2011世界大会、Showcaseインタビューまとめ高校生レポーターとしてNY行ってきたよ!月別アーカイブ参加グループプログラミングはてなブログをはじめよう!CanIさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。