RubyをCに変換する話の予告編 あるいは隙あらば自分語り

言語実装 Advent Calendarの13日目のRubyをCに変換する話という記事を書く予定です。これは今作っているmrubyのJIT2(仮称)の説明なんですが、何を考えてこんなものを作ったのか理解に助かるだろうなという理由に見せかけて、自分語り欲求を満たすために、この10年強の間何を作って何を得て何を失ったか書いてみます。

yarv2llvm

時は2007年ころにさかのぼります。その頃、離婚して強制的に時間がいっぱいできたとか、ケーブルテレビで常時接続のインターネットが使えたりとプログラムを書くための環境がとても整ってきました。そんな中、llvmrbyというとても面白いものを知りました。llvmrubyはRubyからllvmを使うためのライブラリでこれを使うと、高速なプログラムがつくれます(簡単とは言っていない)。
これを使って正規表現エンジンとか作っていたのですが、やっぱりYARVのバイトコードを変換したいと思い、作成しました。そのころ、syoyoさんがpythonで型推論(型推定)の発表をされていてその方法を取り入れて静的に型を推定できるようにしました。具体的なアルゴリズムはここにあります。フィボナッチ級数のプログラムがRubyの40倍の速度だったり、SDLのバインディングを組み込んでグラフィックスも高速化出来たりいろいろ出来るようになりました。特筆すべき成果はao-benchのRuby版で、yarv2llvmの性能評価のために書いたのですが色々なところで使ってくれているようです。しかし、どうしてもbm_app_pentominoが型推定できなかったり、llvmrubyが保守されなくなって新しいLLVMでは動かなくなったり、なによりLLVMを使うのに疲れたので、このプロジェクトは無くなりました。

yarv2llvmの教訓

　このプロジェクトの教訓は一番大きいのはLLVMは辛いということです。何かあると何の説明もなくassertion errorって出るのも辛いですが、動的型付け言語には向かないという意味でも辛いです。
　また、このプロジェクトは紹介する3つのプロジェクトの中で一番完成度が低いも関わらず、githubのスターの数が一番多いのです。また、他のプロジェクトではない海外のサイトで紹介されていたりしますその1, その2
もちろん、小僧、自分の力で勝ったのではないぞ。そのLLVMとllvmrubyの名声のおかげだという事を忘れるな！　ってのは重々理解しているわけですが、OSSであっても必ずしも評価が技術を伴っているとは限らないってことを学習しました。
型推定の問題については同じメソッドに複数の型の引数が来ることがある多相性を扱うようにしないとRubyでは通用しないことが良くわかりました。

ytljit

次に作ったプログラムがytljitです。yarv2llvmで問題になったbm_app_pentominoが型推定出来ない問題、BIGNUMなどはLLVMでは効率よく実装できない問題を解決ることを考えました。型推定についてはメソッドの引数の型の組の条件付きで推定するようにしました。よくわからないと思いますので昔書いた記事を読むと分かるかもしれないし、分からないかもしれないです。BIGNUMとかを効率よく実装するためにはアセンブラしかないと判断し、Rubyでアセンブラを作りました。あまり話題になっていないのですが、そこそこ順調に進み、こんなドヤ顔のアナウンスをruby-listメーリングリストに流すまでになりました。アナウンスを見て分かる通り何でも貪欲に機能を取り入れています。こういう流れになると失敗するのは世の常です。
そして、プログラムが複雑になり過ぎてバグがどうしても直せなくなってそのまま嫌になってプロジェクトは終わってしまいました。あのドヤ顔メールを出してすぐのことです。

ytljitの教訓

　Simple is best

mrubyのJIT

ytljitがポシャってしばらくして、新しいおもちゃとしてうってつけなmrubyが発表されました。しばらく、インラインキャッシュを付けたりして遊んでいたのですが、そうあれは某小学校で下水工事をしていた時、これってTracing JITが組み込めるんじゃね?って気づきました。やってみるとうまく行きそうです。
ytljitの教訓から出来る限りシンプルに元のmrubyを出来る限り生かしてと心がけました。アセンブラを自作するなんてとんでもないということで、Xbyakを使わせてもらいました(これは大正解)。そうこうしているうちにmrubyのJITはとてもうまく行きました。
しかし、満足のいく性能が出ずだんだん汚いコード・早過ぎる最適化の誘惑に負け出してきました。プログラムはとても汚くなりましたが、なんとかデバッグは出来てmrubyの10倍くらいの速度が出るようになりました。でも、このアプローチではこれが限界。もっと速くするにはプログラム全体を見て、色々解析する必要があったのです。

mrubyのJITの教訓

速くするにはそれなりに土台がいる。そうしないと限界が訪れる

最後に

続きは13日に会いましょう