The Ruby VM Episode V

横浜も暑いです。仕事する気にはなれないので気分転換に。

以前、新しい Ruby VM に移行する大きな理由の一つは最適化に関する新しいオプションを提供することだ、と仰っていましたね。新しい Ruby VM に追加された最適化に関して、またそれらによってどのくらい、またどの操作がより早くなるのでしょうか?

ささだ さん(以下 ko1):

いいですよ。はじめに、YARV 実効命令の基礎について書きましょう。YARV は 2種類の実効命令をもっています。一つはプリミティブな実効命令です。Ruby のコードはこれらのプリミティブな実効命令で表現することができます。もう一つは最適化のための実効命令です。Ruby スクリプトを記述するためには必要ないものですが、最適化のために追加されました。プリミティブな実効命令は(putobject のように)名前に _ を含みまず、最適化実効命令は(opt_plus のように) _ を含みます。VM の実効命令を参照したい場合、このポリシーは役に立つことでしょう。先ずはプリミティブ実効命令を読む必要があります。

最も簡単かつ効果的な最適化は特化実効命令です。この最適化は、例えば Fixnum#+opt_plus にするように、メソッド呼び出しを別の VM 実効命令に置き換えるものです。現在の Ruby数値計算が遅いのは全ての操作がメソッド呼び出しだからです。例えば 1 + 21.+(2) となります。しかし数値計算Ruby のメソッド起動よりも軽量ですから、メソッド呼び出しだけが数値計算のオーバヘッドなのです。

しかし私たちはコンパイル時に式が数値操作かそうでないかを知ることができません。例えば次のコードは実行時に Fixnum か Array か、が決まります。

a = c ? 1 : [:elem]

ですから、私たちは + 式を数値操作実効命令に置き換えることはできません。特化実効命令、例えば + メソッド起動を置き換える opt_plus は次のようなコードになります:

    def opt_plus(recv, val) # simple version
       if recv.class == Fixnum && val.class == Fixnum
         if Fixnum#+ is not redefined
           return calculate "recv + val" without method call
         end
       end
       # normal method invocation
       recv.+(val)
    end

レシーバと値が Fixnum かどうか、また Fixnum#+ が再定義されていないかどうか、をチェックします。これらのチェックの後、メソッド起動無しに計算します。実際、Float#+ もまたチェックされます。他にも特化実効命令があります。

YARVVM ジェネレータを用いてこのような実効命令の実装を容易にします。スタック操作のような厄介なコードを書く必要はありません。opt_plus のような VM 実効命令を単純な VM DSL で書けば、VM ジェネレータはそれを C コードに変換します。

特化実効命令は非常にシンプルですが、fib()tak()、また境界計算プログラムなどのシンプルなベンチマークには非常に効果的です。


あなたの回答を読んでいる間に生じた質問が一つあります。 Ruby スクリプトは、もし望むなら、これらの VM 実効命令にアクセスすることができるようになるのでしょうか?

ko1:

端的に答えるならば、可能です。

YARV では、バイトコードとその他の情報は VM::InstructionSequence クラスとして表現されます。このクラスを指す場合、私は "ISeq" という名前をしばしば使います。ISeq オブジェクトは一つのバイトコードのシーケンス、(例外と、ブレークのような他のグローバルエスケープを取得するための)一つのキャッチテーブル、一つのローカル変数名称テーブルとその他のものを含んでいます。

ISeq オブジェクトは Array のような Ruby のプリミティブオブジェクトにダンプすることができます。同様に、ISeq はプリミティブオブジェクトなどのデータを用いて構築することができます。これはつまり、YARV コンパイラ無しで YARV バイトコードを構築できるということです。勿論、この機能は ruby スクリプトの難読化(Java クラスファイルのようなもの)といったほかの目的にも使用することができます。

(ところで、私はこの機能を Ruby2C コンパイラ上で使っています。Ruby プログラムを C プログラムに直接翻訳するのは困難ですが、YARV 実効命令からなら翻訳は容易です。作業が終わったら、これを Ruby にバンドルしたいと考えています。)

それゆえ ISeq ダンプデータを書くのは困難です。そこで私は YARV アセンブラとして "lib/yasm.rb" を準備しました(が、これは current trunk にコミットされていません)。YASM を使えば、Ruby プログラム上で YARV バイトコードシーケンスを記述することができます。ただし YARV/ISeq ローダはバイトコード検証器を持っていませんので、不正なバイトコードシーケンスがロードされると、YARV/Ruby はコアダンプするでしょう。

lib/yasm.rb をコミットしたら、使い方のチュートリアルを書く予定です。


新しい Ruby VMtail 再帰メソッドを最適化しますか? もししないのであれば、この最適化を追加する計画はありますか?

ko1:

YARVtail 再帰の最適化をサポートしませんが、tail 呼び出しの最適化をサポートします。

次のプログラムを見てください:

    class C
       def foo
         foo # (A) tail recursive call
       end
    end

    class D < C
       def foo
         super
       end
    end

    D.new.foo

goto を (A) で置き換えられますか? (A) は D#foo を呼び出さなければならないため、私たちは tail メソッド呼び出しを削除します。ええ、私たちは以下のトリックを用いてこの最適化を実装することができます。

    class C
       def foo
         if search_method(:foo) == C#foo
           goto first_of_foo
         else
           foo
         end
       end
    end

しかし tail 再帰最適化を実装する際、私たちは内部ブロック tail 再帰などを考えなくてはなりません。

ところで、YARVtail 呼び出し最適化をサポートし、呼び出しのスタックフレームを削除します。schema 言語のように VM スタックを消費することなく、tail 位置のメソッドを呼び出すことができます。よって何かをループさせるためのメソッド呼び出しを使うことができます。メソッドコールを用いて状態遷移を作ることができます。

なお tail 呼び出し最適化には幾つかの注意が必要です。第一に、バックトレースが削除されるため、バックトレースを用いて tail メソッドの呼び出し元メソッドを見ることができません。第二に、この最適化はメソッド呼び出しの速度を改善するものではありません。tail 呼び出し処理は通常のメソッド呼び出しの処理とほぼ同じです。通常のメソッド呼び出し処理の最後に、tail 呼び出しかどうかをチェックします。メソッド呼び出しが tail の場合、新しいスタックフレームにプッシュする代わりに現在のメソッドフレームを使用します。

現在の Ruby 1.9(trunk)ではこのオプションは有効化されていません。試してみたい場合は "vm_opts.h" 内のオプション(OPT_TAILCALL_OPTIMIZATION)を書き直して、再コンパイルしてください。Ruby 1.9 のリリースバージョンではこの最適化を有効にするつもりです。更なるコメントが必要です。もし何か致命的な問題を見つけた際には教えてください。


近い将来に新しい Ruby VM に追加したい何らかの最適化について話していただけますか?

ko1:

近々、AOT(Ruby から C へのコンパイラ)をリリースする予定です。この翻訳器は全ての Ruby の仕様をサポートしているため、性能に関する『銀の弾丸』ではありません。

全ての Ruby の仕様を維持することは、"高性能を実現することはできない"ことを意味します。もし幾つかの仕様を無視すれば、更にドラスティックな最適化を実現することができるでしょう。ですから Ruby スクリプトから翻訳した C コードは遅くなるでしょう(といっても、勿論、通常の解釈よりは早いですよ)。

Ruby の仕様はコンパイラVM 開発者にとっては敵ですね。そのため、私はプログラマの知識を追加するための "プラグマ"構文 を追加したいのです。例えば "eval はこのファイル中にはありません" とか "Fixnum メソッドの再定義はありません" とか。こういった情報はコンパイラがより効果的に最適化を行う手助けになることでしょう。

また、ブロックインラインの実装も計画しています。これは Ruby には非常に効果的だと思います。実験的で不完全なバージョンは作ってありますが、これを実現するためにはもっと調査をする必要があります。

ところで私は JIT コンパイルには触れないでしょう。実装コストに見合うだけの理由が無いからです。皆さん "JIT" という単語が好きですが、私は Ruby の仕様を考えると効果が無いと思います。

The Ruby VM Episode V