miura1729の日記

binary_treesはくわせもの

21:58 |

ふと、MagLevとyarv2llvmはどっちが速いんだろう？って思い調べてみました。

http://antoniocangiano.com/tag/maglev/

に、MagLevのbinary_treesの実行速度がRuby 1.8.6の結果とともに載っているのでこれと比べればいいやと考えました。

結果は、MagLevはRuby1.8.6の60.1秒に対して、7.7秒で約7.81倍です。

ところで、binary_treesは一見単純なプログラムですが、

1. 配列の要素が色々な型のデータが入る
2. 木構造なので、配列の構造がCでいう自己参照型構造体の形になっている

と、yarv2llvmに厳しいプログラムです。

木のノードを表す配列には、数字,配列,nilが入ります。こういう場合、型推論は行わず(正確には型推論の結果を無視して)、型をVALUEとして扱うように変更しました。しかし、型をVALUEとして扱うと型変換のオーバーヘッドが入るのでエラーにするかVALUEとして扱うかオプションで選べるようにしました。

自己参照型構造体の形になっている配列は型を表示しようとすると、Array of Array of Array of ...と止まらなくなってしまいます。これは、この前のうさぎと亀の循環検知アルゴリズム(http://d.hatena.ne.jp/miura1729/20081130)で対応しました。

yarv2llvm, Ruby 1.8.7, Ruby 1.9.0で実行してみました。

yarv2llvm

stretch tree of depth 17	 check: -1
131072	 trees of depth 4	 check: -131072
32768	 trees of depth 6	 check: -32768
8192	 trees of depth 8	 check: -8192
2048	 trees of depth 10	 check: -2048
512	 trees of depth 12	 check: -512
128	 trees of depth 14	 check: -128
32	 trees of depth 16	 check: -32
long lived tree of depth 16	 check: -1

real	0m11.086s
user	0m10.513s
sys	0m0.592s

Ruby 1.8.7

stretch tree of depth 17	 check: -1
131072	 trees of depth 4	 check: -131072
32768	 trees of depth 6	 check: -32768
8192	 trees of depth 8	 check: -8192
2048	 trees of depth 10	 check: -2048
512	 trees of depth 12	 check: -512
128	 trees of depth 14	 check: -128
32	 trees of depth 16	 check: -32
long lived tree of depth 16	 check: -1

real	1m53.655s
user	1m53.405s
sys	0m0.077s

Ruby 1.9.0

stretch tree of depth 17	 check: -1
131072	 trees of depth 4	 check: -131072
32768	 trees of depth 6	 check: -32768
8192	 trees of depth 8	 check: -8192
2048	 trees of depth 10	 check: -2048
512	 trees of depth 12	 check: -512
128	 trees of depth 14	 check: -128
32	 trees of depth 16	 check: -32
long lived tree of depth 16	 check: -1

real	0m35.207s
user	0m30.655s
sys	0m0.155s

これから、Ruby 1.8.7の10倍、Ruby 1.9.0の3倍くらいであることがわかります。でも、このyarv2llvmはずるをしていて、VALUE型のデータはチェックせずFixnumであると決め付けています。何もチェックしないでいきなり右シフトしています。そういうことで、多分、binary_treeに関してはMegLevと同じくらいといえるかと思います。

...、とここまでやった後MagLevの詳しいベンチマーク結果がありました。...思ったより速くない様な気がする・・・。複雑な機能をつけて速度が落ちていったのだろうか？明日はわが身です。

http://antoniocangiano.com/2008/12/09/the-great-ruby-shootout-december-2008/

追記

型衝突を起した場合、どの型で衝突が起きたか記録するようにしました。そうすることで、例えばVALUE型の足し算において、足し算に関係する型がFixnum(Int32Ty)だけだと判れば型チェックを省いていきなりシフト命令を出しても安全であることが(例えば、実はFloat型のデータが渡ってきてるとかそういうことは無いことが)、保障できます。

Rubyでも例外が出るような型エラー(nil + 1とか)はコアはいちゃいますが、そういうのはRubyでチェックしてもらうというスタンスです。