YARV Maniacs 【第 9 回】 特化命令

初稿：2006-11-26

書いた人：ささだ

はじめに

YARV: Yet Another RubyVM を解説するこの連載。今回は、特化命令による処理の最適化手法についてご紹介します。命令セットの続きを解説しようと思ったのですが、簡単に解説できる内容が思いつかなかったので (すみません、今とても余裕がないのです)、親戚みたいな特化命令のお話です。

RubyConf 2006

毎年恒例の RubyConf 2006 が行われました。今年も枠をもらえたので、YARV: on Rails? というタイトルで発表をしてきました。内容は現在の YARV の内容と、実際に YARV どうなのよ、という内容でした。発表資料は http://www.atdot.net/yarv/rc2006_sasada_yarv_on_rails.pdf においておきます。

発表時に、なんとか Rails を動かすデモを行いたかったのですが、なかなか動かなくて困りました。日本人参加者を巻き込んだ徹夜のデバッグ作業で、なんとか発表の 3 時間くらい前に動くようになりました1。

デンバー合意

さて、RubyConf 2006 が終わった夜、日本人参加者が集まって今後の Ruby について語り合いました。そこで、1.8 の今後、そして 1.9 の今後について、色々と議論しました。その結果が デンバー合意という名前でまとめられています。

1.8 については ruby-dev で今議論していますが、1.9 (というか YARV) については、

  • 2006 年 11 月中には YARV をマージ
  • 今後 Ruby の開発は Subversion へ移行
  • 2007 年 12 月には 1.9.1 としてリリース (これは前から言っているか)

という内容になりました。

ちなみに、デンバー合意という名前は、国同士の戦争終結時に「なんとか合意」のような、敗戦国にとって不利な条件を勝戦国によってほぼ決められてしまう様をもじって、今回のように (まつもとさんとかささだとかが置いてけぼりで)、なんかどんどん決められてしまった様子を表しています。

というわけで、今 YARV のマージ作業を行っています。最新の Ruby への追従がだいたい終わったので、あとは YARV のソース整理ということになっています。

YARV ソースコード勉強会

B の葉桜さんによる、YARV ソースコード勉強会という記録がはてなダイアリーで週 1 回くらいのペースで執筆されています。実際に YARV のソースコードを読んで、それについて詳細な解説を述べていらっしゃいます。なんて素晴らしいんでしょう。

私が読んでも、ふんふん、なるほどなるほど、そうだったのか、と思うところしきり (要するに、自分が何を書いたのか、もうあんまり覚えていない) なので、YARV の細かい挙動に興味がある方は読んでみることをお奨めします。

しかし、今後やーまにはこの日記のリンクを貼るだけでいいような気がしてきたな。

2006 年度下期未踏ソフトウェア創造事業

なんというか、またか、って感じですが、2006年度下期未踏ソフトウェア創造事業に「Ruby 用仮想マシン YARV の完成度向上」という地味なタイトルで千葉滋プロジェクトマネージャに採択していただきました (ＩＰＡ：未踏ソフトウェア創造事業：2006 年下期未踏ソフト　公募結果)。

やることは、1.9.1 リリースに向けたもろもろです。これでまた逃げられなくなりました。いろいろ頑張ります。多分。

特化命令

Ruby プログラムで行われる操作は、たいていメソッド呼び出しによって実現されています。例えば「1 + 2」のように一見メソッド呼び出しに見えない操作も、実は内部では「1.+(2)」というメソッド呼び出しだと解釈されます。

Ruby では今までこれをそのままメソッド呼び出しとして実行しており、これが「Ruby は遅い」と言われる原因になってきました。とくに、よく評価に利用されるマイクロベンチマーク (つまり、すごーく単純な性能評価のためのプログラム) では、この「1 + 2」のような単純な計算のコストが実行時間全体に対して多くの比率を占めるので、ここが遅い Ruby は不利になっていました。これに対して、例えば JavaVM では 1 などの整数値を特別扱いすることで性能の向上をはかっています。

そこで YARV では「1 + 2」のような単純な計算を高速に実行する工夫をしています。それが特化命令です。

すでに述べたように「1 + 2」のようなプログラムは Ruby では「1.+(2)」と解釈されますが、コンパイル時にチェックして、

  • 呼び出すメソッドが “+”
  • 引数の数が 1 つ
  • ブロックなどは付かない

という場合には汎用の “send” 命令ではなく、”opt_plus” 命令にコンパイルします (compile.c の iseq_specialized_instruction() によってチェック、変換を行っています)。

実際に試してみましょう。以下に Ruby プログラムと、その YARV 命令列へのコンパイル結果を示します。

# Ruby プログラム (1)
p(1 + 2)
# Ruby プログラム (1) のコンパイル結果
0000 putself                                                          (   1)
0001 putobject        1
0003 putobject        2
0005 opt_plus
0006 send             :p, 1, nil, 4, <ic>
0012 leave

p メソッド呼び出し時には send 命令を使っていますが、+ メソッド呼び出しには opt_plus 命令を使っているのがわかるかと思います。

opt_plus 命令の中身

さて、では opt_plus 命令は何をしているのでしょうか。とても簡単にしたコードを書いてみます。「1 + 2」、つまり「1.+(2)」では、1 がレシーバ (recv)、2 が引数 (val) となることを踏まえて見てください。

if (recv と val は Fixnum？) {
    if (Fixnum#+ は再定義されていない？) {
        return fix_plus(recv, val);
    }
}
return send(:+, recv, val);

まず最初に recv と val が Fixnum クラスであるかどうかチェックします。もしそうであれば、次に Fixnum#+ が再定義されていないかチェックします。Ruby のメソッドはたいてい再定義可能なので (再定義できないのは freeze された module か class のメソッド)、このチェックを行わないと再定義された挙動に追従することができなくなります。Fixnum#+ なんて、再定義する人はいないとは思うのですが……。

このチェックを通ったあと、Fixnum 同士の足し算の処理に移ります。Fixnum 同士の足し算はオーバフローを起こしたら Bignum へ変換するなどの処理が必要なので、少し長めの処理になります。

どちらかのチェックでひっかかったら、通常のメソッド呼び出しの処理へ移行します。

この命令を導入することで、「1 + 2」のような単純な操作を、メソッド呼び出し処理 (メソッドフレームの準備、破棄など) を行わなずに実現できるようになりました。実際、結構速くなります。

他のクラス、他のメソッド

さて、先ほどの例で高速化できるのは、レシーバと引数が Fixnum で、オペレータ (メソッド名) が + のときだけでした。しかしもちろん同じような考えかたは他のクラス、他のメソッドにも応用できます。

他のクラスへの対応

先ほどの例では、レシーバ、引数が Fixnum クラス限定でしたが、たとえば両方とも Float だった場合にも同じような高速化が可能です。この場合、opt_plus の処理は次のようになるでしょう。

if (recv と val は Fixnum？) {
    if (Fixnum#+ は再定義されていない？) {
        return fix_plus(recv, val);
    }
}
else if (recv と val は Float？) {
    if (Float#+ は再定義されていない？) {
        return float_plus(recv, val);
    }
}
return send(:+, recv, val);

こんな感じでチェックを追加していけば、いろんな型 (クラス) に対する「+」メソッド呼び出しを高速化できます。実際、opt_plus 命令は今現在、「Fixnum + Fixnum」と「Float + Float」以外に、「String + String」、「Array + 任意の型」2 という型に対応しています。

ただし、対応する型を増やせばいいというものではありません。たしかに「Fixnum + Fixnum」のような処理は高速になりますが、他のメソッド呼び出し、たとえば独自に定義したクラスの Foo#+ メソッドを呼び出すためのプログラム「foo + 任意の値」は、上記型チェックを行ったあと (当然、どのチェックにもひっかからない)、通常のメソッド呼び出し処理を行うので、チェックの分だけオーバヘッドがかかります。

というわけで、このチェックを入れても十分に利益があるような「よく呼ばれる」、「メソッド呼び出しのオーバヘッドが実際の処理に比べて十分大きい」場合に導入するようにしなければなりません。

他のメソッドの対応

さて、例として opt_plus、つまり「recv + val」の最適化について紹介しましたが、似たような最適化を他のメソッドでも行っています。以下にその一覧を示します。

特化命令名 最適化するメソッド
opt_plus +
opt_minus -
opt_mult *
opt_div /
opt_mod %
opt_eq ==
opt_lt <
opt_le <=
opt_ltlt <<
opt_aref []
opt_aset []=
opt_length length
opt_succ succ

ほとんどは数値計算に関するメソッドですが、[] や succ なんてメソッドも最適化するようにしています。

特化命令によって対応する型が違いますので、詳しくは YARV ソースコードの insns.def をご覧ください。

特化命令が対象とするメソッドの再定義チェック

さて、特化命令が対象とするメソッド (以下、基本メソッド) の再定義のチェックですが、メソッド定義をまとめている eval_method.h の rb_add_method() 関数内でチェックしています。もしそのメソッド追加が再定義を意味している場合、vm.c で定義している yarv_check_redefinition_opt_method() 関数によって再定義フラグを設定します。

現在、再定義フラグは Fixnum#+ や Float#+ のように、各メソッドごとに用意するのではなく、+ メソッドのどれかが再定義されているか、というフラグになっているため、Float#+ を再定義すると Fixnum#+ も再定義されたと思うような実装になっています。まぁ、ほとんど基本メソッドの再定義なんかしないだろう、という予測の元で、こういう仕様にしています。

定数畳み込み最適化は？

ところで、「1 + 2」のような式は、C 言語などではコンパイル時に「3」に変換してしまいます。この最適化を定数畳み込みといいます。Ruby (YARV) では定数畳み込みをしていないのですが、それはなぜでしょうか。

これはもちろんメソッドの再定義、この場合は Fixnum#+ の再定義に対応するためです。再定義はいつ、どの時点で起こるかコンパイル時にはわからないので、再定義にきちんと対応するには、定数を畳み込むわけにはいかないのです。

Ruby で定数畳み込みを実行するには、基本メソッドが再定義された時点でコンパイルしなおす、などの手法が考えられますが、これを実現するには他の問題 (on stack replacement が必要だったり) があるので、なかなか難しいです。

ただ、書きながら思いついたのですが、基本メソッド全てが再定義されていない場合は定数畳み込みをした値を push してプログラムカウンタを進めるような処理を書いておくのはいいかもしれませんね。ちょっと考えてみよう。

  # もし再定義されていなければ 3 を push して lend へジャンプ
  opt_putobject_without_redefinition 3, lend
  putobject 1
  putobject 2
  send :+, 1
lend:

こんな感じ。

おわりに

今回は特化命令について解説しました。とても簡単な最適化でしたが、YARV のベンチマークが高速になるのは、この特化命令による最適化の効果が大変大きいです。また、この命令によって、Ruby が苦手としてきた数値処理の分野でも、Ruby を利用できる可能性が広がったのではないかと思います。

ところで、特化命令については以前 ruby-core:05591 で触れたとおり、もっと他の実装方法もあると思っています。色々なトレードオフがあるとは思うのですが、少し落ち着いたら、考えてみたい問題です。

次回はいつやるか、何をやるかまったく検討が付かないのですが、多分やると思いますので気長にお待ちください。

著者について

ささだこういち。非学生。最近、いろんな余裕がなくなってきた感じ。まぁ、いいか。

バックナンバー

  1. このあたりの個人的な感想文は自分の日記に書きました (DA 10/26 (Thu)) ↩

  2. ここでは rb_ary_plus() という API を直接呼び出しているが、引数の型はその API 中でチェックするので、opt_plus 命令がチェックする必要は無い ↩