binary_treesはくわせもの
ふと、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は一見単純なプログラムですが、
- 配列の要素が色々な型のデータが入る
- 木構造なので、配列の構造が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
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でチェックしてもらうというスタンスです。
