フルRubyのビルドに対応しました
今まではminirubyのみだったのですが、今回、フルのRubyのビルドに対応しました(Windowsの32bit版のみ)。
ベースとなるRubyのバージョンは2.1.0です。LLVMはバージョン3.4を使っています。ビルドにはVisual Studio 10以降が必要です。
ビルド手順は、以下の通りです。
- LLVM公式サイトにあるGetting Started with the LLVM System using Microsoft Visual Studio — LLVM 3.4 documentationの指示に従って、LLVMをインストールします。
- githubからソースコードを入手します。
git clone https://github.com/msumimz/ruby/tree/rbjit - 「Visual Studioコマンド・プロンプト」を起動します。以後は、このコマンドプロンプトから作業します。
- 2.で入手したソースファイルのあるディレクトリに移動します。
- LLVMの場所を指定するため、win32\configure.batに「--llvm-prefix」というオプションを追加しています。1.でインストールしたLLVMライブラリの場所を、--llvm-prefixの引数に指定してwin32\configure.batを実行します。
- あとは通常のビルドと同じようにnmakeします。
- 必要に応じてnmake testなりnmake installなりしてください。テストにすべてパスすることを確認しています(もちろんインタープリタとしての動作です)。
コマンド入力は以下のようになるでしょう。
$git clone https://github.com/msumimz/ruby/tree/rbjit $cd ruby $win32\configure.bat --llvm-prefix=c:\llvm\llvm-3.4 $nmake $nmake test $nmake install
このようにしてビルドした実行ファイルには、-vで表示されるバージョン文字列の最後に"rbjit"がつきます。
$ruby -v ruby 2.1.0p0 (2013-12-25 revision 44417) [i386-mswin32_100] rbjit
今のところ、precompileで明示的にJITコンパイルを行わない限り、自動でのコンパイルはしませんので、このようにしてビルドしたRubyは、通常のRubyコマンドとして使えます。
今後の方針
ところで、前回の記事で、今後は言語機能の実装をする予定だと書いたのですが、ふと思い立ちまして、まずは以下の作業を行うことにします。
- フルRubyのビルド(今回の記事です)。
- インターフェイス周りを整理して、使いやすいものにします。今までは未対応の言語機能をコンパイルしようとするとabortしていましたが、ちゃんとエラーを返すようにします。
- メソッドや定数の再定義などのガードの実装。
- ビルド・インストールと使い方のドキュメント作成。
- Linux対応。
要は、普通の人が使えるように、パッケージングを整えようということです。まだ実用的に使うには機能不足ですが、まずは形を整えてから、少しずつ機能拡充していこうという方針です。
もともと、普通のRubyとしても動くのがメリットですので、実用性が増すにすれて、使ってみてくれる人も出てくると期待しています。
最初の最適化:型解析とメソッドのインライン化
前回の投稿から期間が空いてしまいました。実装にはいろいろ不十分なところも多いのですが、きりがないので記事にすることにします。
前回のベンチマークでは、JITを実装したものの、単純なJITコンパイラではMRIのインタープリタによる実行速度に勝てないという結果でした。これに対する対処として、基本的な型解析とメソッドのインライン化の最適化を導入したというのが今回の話題です。
https://github.com/msumimz/ruby/tree/rbjit
まずは、ベンチマークの結果から。
$vc10/Release/miniruby examples/perf_while.rb user system total real interprited 12.012000 0.000000 12.012000 ( 12.010687) JIT compiled 1.186000 0.000000 1.186000 ( 1.181068)
最適化の結果、インタープリタに比べて約10.1倍の実行速度になりました。
ベンチマークのソースコードは以下の通りです。timesの繰り返し回数を増やしたほかは前回のベンチマークと実質的に同じです。
# minirubyは$LOAD_PATHが空なので設定する $LOAD_PATH << File.expand_path("../../lib", File.dirname(__FILE__)) require "benchmark" # ベンチマークのメソッド def m1 i = 1 sum = 0 while i <= 10000 sum += i i += 1 end sum end # インタープリタで実行 puts "\t\t" + Benchmark::CAPTION print "interprited\t" puts Benchmark.measure { 30000.times { m1 } } # 後で解説します load File.expand_path("../lib/fixnum.rb", File.dirname(__FILE__)) # JITコンパイル precompile Object, :m1 # JITコンパイルされたコードを実行 print "JIT compiled\t" puts Benchmark.measure { 30000.times { m1 } }
最適化の内容解説
それでは、最適化の内容を説明しましょう。ベンチマークのコードは説明にはやや複雑なので、以下の単純なコードを例にします。
def m(a) 1 + a + 2 end
その1: コントロールフローグラフの構築
最適化の前提として、Rubyのソースコードから、コントロールフローグラフ(Control Flow Graph、CFG)というものを作成します。これは、プログラムの制御フローを有向グラフとして表現したものです(そのまんますぎる)。今回の例の場合、制御フローというほどの構造はないので、CFGは以下のように単純なものになります。
図の読み方ですが、ボックスがそれぞれ制御の単位を表します。今回は、entryというボックスと、exitというボックスの2つだけです。ボックス内の各行が実行すべき命令を表します。各行の最初の2つの十六進数が、それぞれ、命令アドレスと、命令の結果が代入される変数を表し、次に命令のオペコード、さらにそれに対する引数が続きます。変数欄が空の行は、命令の結果が保存されないことを表します。
xxxxxxxx xxxxxxxx CALL xxxxxxxx (x) xxxxxxxx xxxxxxxx アドレス 変数 オペコード 引数
現在の実装では、以下の命令があります。
命令 | 意味 |
---|---|
IMM value | 即値value左辺の変数に代入する。値はMRIの実装に従います。例えばFixnumの値の場合、それが表わす整数を2倍して1を足したものになります。その他、trueなら2、falseなら0、nilなら4などになります。 |
COPY w | 変数wを左辺の変数に代入する。 |
LOOKUP w name | レシーバwから名前nameを持つメソッドを検索する。 |
CALL m (n) arg1 arg2 ... argn | メソッドmをn個の引数arg1...argnで呼び出す。arg1はレシーバです。メソッドmはLOOKUP命令で検索したものを用います。 |
EXIT | CFGの終了。 |
ENV | メソッドの実行環境を表す。今回は詳細省略。 |
ほかにもいくつかありますが、なんとなく雰囲気はわかっていただけると思います。
元のソースコードでは、メソッド内では変数を定義せずに1行で書いていますが、CFGに変換されると、各メソッド呼び出しの結果に対してそれぞれ変数が定義されます。例えば以下のような、より説明的なソースコードをコンパイルしても、生成されるCFGは同じになります。
def m(a) b = 1 + a c = b + 2 return c end
その2: SSA形式への変換
このJIT実装では、CFGの形式としてSSA形式というものを利用しています。そのため、まずこの形式に変換します。
とはいっても、今回の例では、すでにSSA形式になっているため何もする必要がないのでした。
その3: 型解析
CFGの各命令の左辺の変数に対して、型を解析します。基本的な考え方は、即値(IMM)ならその値の型になり、代入(COPY)なら右辺の値になる、というように、「明らかに型がわかる変数から波及させて、順に型を推定していく」というものになります。
メソッド呼び出しの場合は、
という手順になります。
「メソッドが返し得る型」をどうやって取得するのかが問題になりますが、Rubyで書かれたメソッドであれば、そのメソッドを同様に型解析してやればわかります。C言語で書かれたメソッドの場合は、予め定義してやります。
例えば、Bignum#+については、setup.cppに、以下のように定義しています。
CMethodInfo::construct( mri::Class::bignumClass(), "+", false, TypeSelection::create(TypeExactClass::create(mri::Class::fixnumClass()), TypeExactClass::create(mri::Class::bignumClass())));
最後の引数であるTypeSelection::...が戻り値の型です。細かい説明は割愛しますが、FixnumまたはBignumを返すと定義されているな、となんとなく感じていただければよいと思います。
なお、解析の結果、唯一の型が決まるとは限らず、「複数の型のうちのどれか」「ある型またはその継承型のどれか」などの結果もあり得ます。そのため、以下では解析の結果のことを型制約と呼ぶことにします。「型に関する制約条件」くらいの意味です。
具体的なアルゴリズムとしては、定数伝播のアルゴリズムを変形して使っています。*1
さて、今回の例では、CFGの上から順に、以下のように変数の型制約が推定できます(結果に無関係な命令は省略)。
アドレス | 左辺変数 | 命令 | 型制約 |
---|---|---|---|
149aefe0 | 14aa7efe0 | IMM 3 | 3はFixnumなので、左辺の型制約はFixnum。 |
14becfd8 | 14beefe0 | LOOKUP 14a7efe0 '+' | レシーバーである変数14a7efe0はFixnumクラスのインスタンスであり、このオブジェクトから名前'+'で呼び出されるメソッドはFixnum#+のみなので、メソッドFixnum#+が型制約となる。 |
148e4fd8 | 14beafe0 | CALL 14beefe0 (2) ... | メソッドFixnum#+の返し得る値はFixnumまたはBignumなので、これらのいずれかが左辺の型制約となる。 |
14ad4fe0 | 14ad6fe0 | IMM 5 | 5はFixnumなので、左辺の型制約はFixnum。 |
14bdcfd8 | 14bf4fe0 | LOOKUP 14beafe0 '+' | レシーバーである変数14beafe0はFixnumクラスまたはBignumであると推定されており、これから名前'+'で呼び出されるメソッドはFixnum#+またはBignum#+であるため、これらのいずれかが型制約となる。 |
13fb3fd8 | 14978fe0 | CALL 14bf7fe0 (2) ... | メソッドFixnum#+の返し得る値はFixnumまたはBignumであり、Bignum#+の返し得る値も同じ。したがって、これらが左辺の型制約となる。 |
14156fe0 | 14a5efe0 | COPY 14978fe0 | 代入命令の左辺の型制約は、右辺と同じになる。したがって、FixnumまたはBignum。 |
最後の変数14a5efe0がこのメソッドの戻り値となりますので、メソッドの戻り値の型制約はFixnumまたはBignumです。
その4: プリミティブを利用したメソッド定義
さて、このようにして、CFGの変数の型と、実行時に呼び出されるメソッドを推定することができました。しかし、MRIの実装では、Fixnum#+もBignum#+もC言語で定義されているため、これ以上の最適化はできません。そこで、少なくともFinxum#+についてRubyで定義し直し、メソッドのインライン化を実現しましょう。
事前準備として、プリミティブというものを導入します。プリミティブは、Rubyスクリプト内で、関数形式で(レシーバを指定せずに)呼び出され、インライン化されて低レベルな命令として実行される特殊な関数です。JITコンパイルされないと使えず、インタープリタで実行するとメソッド未定義エラーになります。
実際に利用例を見てみましょう。以下は、プリミティブを使用してRubyスクリプトとして定義されたFixnum#+です。
class Fixnum alias :generic_add :+ def +(other) if rbjit__is_fixnum(other) && rbjit__test_not(rbjit__bitwise_add_overflow(self, rbjit__bitwise_sub(other, 0))) sum = rbjit__bitwise_add(self, rbjit__bitwise_sub(other, 0)) rbjit__typecast_fixnum(sum) else rbjit__typecast_fixnum_bignum(self.generic_add(other)) end end end
プリミティブは"rbjit__"で始まります。以下のプリミティブが使われています。
名前 | 機能 |
---|---|
rbjit__is_fixnum(obj) | objがFixnumならtrue、そうでなければfalseを返す。 |
rbjit__test_not(obj) | objの真偽値を判定し、真ならfalse、偽ならtrueを返す。Rubyの'!'演算子と同じ意味ですが、'!'演算子は再定義可能なメソッドなので、プリミティブを用意しています。 |
rbjit__bitwise_add_overflow(a, b) | aとbを整数として加算し、オーバーフローまたはアンダーフローが発生すればtrueを、発生しなければfalseを返す。 |
rbjit__bitwise_add(a, b) | aとbを整数として加算し、結果を返す。 |
rbjit__bitwise_sub(a, b) | aとbを整数として減算し、結果を返す。 |
rbjit__typecast_fixnum(obj) | objがFixnum型であることを型解析器に伝える(最適化のヒント)。 |
rbjit__typecast_fixnum_bignum(obj) | objがFixnum型またはBignum型であることを型解析器に伝える(最適化のヒント)。 |
上記のFixnum#+の定義で行っていることは、「otherがFixnumであり、かつ、selfとotherを(otherのLSBをクリアして)加算してもオーバーフローが発生しないなら、otherのLSBをクリアした上で整数として加算して結果を戻り値とする。そうでなければ、通常のFixnum#+を呼び出して結果を戻り値とする」となります。
ここで、Fixnumオブジェクトは、それが表す整数値を1ビット左シフトして、LSBを立てたもので表現されることを思い出してください。例えば、rbjit__bitwise_sub(other, 0)というプリミティブ呼び出しは、FixnumであるotherオブジェクトのLSBをクリアする意味になります。Fixnumの値0をビット列で表すと0b0000_0000_0000_0001だからです。
各プリミティブは、LLVMのビットコードとして、primitives/primitives.llで定義されています。例えばrbjit__is_fixnumの定義は以下の通りです。
define %VALUE @rbjit__is_fixnum(%VALUE %v) nounwind readnone alwaysinline { %v1 = and %VALUE %v, 1 %cmp = icmp eq %VALUE %v1, 1 %ret = select i1 %cmp, %VALUE 2, %VALUE 0 ret %VALUE %ret }
rbjit__bitwise_addの定義は以下の通りです。
define %VALUE @rbjit__bitwise_add(%VALUE %v1, %VALUE %v2) nounwind readnone alwaysinline { %ret = add %VALUE %v1, %v2 ret %VALUE %ret }
これらは、CFGにおいてはプリミティブとして特別扱いされます。LLVMによるJITコンパイル時にはインライン化され、他のIRと合わせて最適化されます。
上記で定義されたFixnum#+を、単独でCFGに変換すると、以下のようになります。命令PRIMがプリミティブを表します。なんとなく理解できるでしょうか。
これをx86のマシン語にコンパイルすると、以下のコードになります。Rubyコードでは冗長に見えますが、それぞれのプリミティブは低レベルなので、LLVMの最適化が効果的に機能します。そのため、コンパイル結果はシンプルで、otherがFixnumである場合は高速に実行されます。
0A1B0010 push ebx 0A1B0011 sub esp,10h 0A1B0014 int 3 0A1B0015 mov eax,dword ptr [esp+1Ch] 0A1B0019 lea ebx,[eax+eax] 0A1B001C xor edx,edx 0A1B001E mov ecx,dword ptr [esp+18h] 0A1B0022 test bl,2 0A1B0025 je 0A1B0038 0A1B002B lea edx,[eax-1] 0A1B002E add edx,ecx 0A1B0030 setno dl 0A1B0033 movzx edx,dl 0A1B0036 add edx,edx 0A1B0038 test edx,edx 0A1B003A je 0A1B0049 0A1B0040 lea eax,[ecx+eax-1] 0A1B0044 jmp 0A1B0065 0A1B0049 mov dword ptr [esp+0Ch],eax 0A1B004D mov dword ptr [esp+8],ecx 0A1B0051 mov dword ptr [esp+4],1 0A1B0059 mov dword ptr [esp],13028FE0h 0A1B0060 call rbjit::rbjit_callMethod (0405DA8h) 0A1B0065 add esp,10h 0A1B0068 pop ebx 0A1B0069 ret
とはいえ、かなり無駄なコードもありますね…。まあ、おいおい改良していきましょう。
なおベンチマークのソースコードにある以下の1行は、上記のような再定義されたFixnumのメソッドを読み込むためのものです。
load File.expand_path("../lib/fixnum.rb", File.dirname(__FILE__))
その5: Fixnum#+のインライン化
さて、これでFixnum#+がRubyスクリプトとして定義できました。最初の例に戻って、メソッド内の'+'メソッド呼び出しをインライン化してみましょう。
例のCFGのアドレス148e4fd8にある最初のメソッド呼び出しは、レシーバがFixnum型であり、呼び出されるメソッドはFixnum#+であることが推定されていますので、CALL命令を、単純に上記のFixnum#+のCFGに置き換えることができます。
アドレス13fb3fd8にある2番目のメソッド呼び出しは、レシーバがFixnum型またはBignum型のいずれかであり、したがってメソッドもFixum#+かBignum#+のいずれかであると推定されています。そのため、まずレシーバの型をテストして、Fixnumであると判定されたときのみインライン化するようにします。Fixnumでない場合はBignum#+を呼び出します。
インライン化された結果は以下のようになります。長いですが、Fixnum#+を2回インライン化しているだけです。変数の値がFixnumの範囲を超えない限り、メソッド呼び出しが発生しませんので高速です。
レシーバの型が推定できない場合
例として示したメソッドの定義が、以下のような内容だったらどうでしょうか。
def m(a) a + 1 + 2 end
この場合、最初の'+'メソッドのレシーバは変数aですが、この変数の型は不明ですので、呼び出されるメソッドが特定できず、インライン化もできないことになります。
これに対応するには、2つの方法があります。
- メソッド名が'+'や'-'などの場合は、レシーバはFixnumの可能性が高いと仮定して最適化してしまう。
- JITコンパイル前に、インタープリタで何度か実行してみることで実行時プロファイルを取得し、レシーバとして利用される型に関する情報を収集する。
1はすでに実装されています。そのため、実際には上記のメソッド定義でもFixnum#+はインライン化されます。レシーバがFixnumであるかどうかのテストが実行されますので、その分がオーバーヘッドになりますが、通常のメソッド検索・呼び出しのシーケンスに比べれば軽量です。
ただし、このような決めうちが通用するのは、Fixnumくらいしかありませんので、一般性はありません。とはいえ、四則演算のようなメソッドに対しては有効です。MRIでも同様の最適化が実装されています。
2は、実行時にレシーバが特定の型であるケースが多いと判明したなら、その型のメソッド呼び出しを特別扱いする方法です。
一般性のある方法は2番目になります。これを行うには、MRIの実行エンジンに手を入れて、プロファイリング用コードを埋め込む必要があります。現実のコードでは型解析がうまく行くとは限らないので、必要な機能ですが、実装はたいへんそうで、今から気が重いです。
よくある質問と答え(脳内妄想版)
Fixnumに特化した最適化に見えますが、現実のプログラムに対して効果があるでしょうか。
メソッド内部でFixnumが利用されるケースは多くあります。例えばArray#eachは、Rubyで実装すれば以下のようになるでしょう。
class Array def each i = 0 len = self.length while i < len yield self[i] i += 1 end end end
Fixnumの計算が高速に実行されることで、Array#eachも効率化されます。
さらに、クロージャもCFGになってしまえばメソッドと大差ありませんので、同じようにインライン化できます(未実装ですが、将来的にはということです)。
このようにして、Array#eachメソッド自体、使われているFixnumのメソッド、クロージャがそれぞれインライン化されれば、Array#eachによるループを、メソッド呼び出しのない、C言語のfor/while文に近いコードで実現できることになります。これにより、かなりの性能向上が望めるでしょう。
効率的なJITコンパイルのために、C言語で実装されたメソッドをRubyで実装しなおす必要があるのですか。
そうです。Rubiniusと同じです。Rubiniusに対して「Smalltalkの影響を受けて、Ruby自身でRubyを記述している」云々の紹介がされることがありますが、Rubiniusが特別のことをしているというより、JITコンパイラを備えた言語では、普通のことだと思います。
とはいえ、すべてのメソッド定義を書き直すのは現実的ではなく、FixnumやArrayなどの、一部の主要なクラスが対象となるでしょう。
ちなみに、この点、インタープリタであるMRIとは最適化の方向性が反対になります。MRIでは、メソッド定義はCで書いた方が高速だからです(この辺り、なかなか悩ましいところです)。
JITコンパイルにかかる時間はどのくらいですか。
ベンチマークの最後の行を以下のように変更して実行してみました。
puts Benchmark.measure { precompile Object, :m1; 30000.times { m1 } }
結果は次の通りです。さすがに1秒かかるようなタスクであれば、コンパイルにかかる時間は大きな影響がないようです(メソッドの大きさの割に呼び出し回数が多く、あまり参考になりません)。
user system total real interprited 11.965000 0.000000 11.965000 ( 11.980685) compiled 1.201000 0.000000 1.201000 ( 1.203068)
また、MRIはCPUのコアを一つしか使いません。これを利用して、JITコンパイルを別スレッドで実行することで、実行時の性能コストなしでコンパイルを行うように実装することも可能と思います。
インライン化されたメソッドに対する例外のコールスタックはどうなりますか? また、Rubyの実行トレース機能は使えますか?
コンパイルされたコードのアドレスとソースコードの各行を対応付けることでき、さらに実行時にコールスタックの履歴を遡ることができれば、例外が発生しない限りコストがかからない方法で、例外のコールスタックを実行時に構築できます。が、このあたりはLLVM次第のところが大きく、あまりきちんと調べていません。MCJITならばDWARFオブジェクトを出力できるそうなので、おそらく方法はあるかと思います。
Rubyのトレース機能も、上記の情報が入手できれば、部分的には実現できなくはないです(デバッガが実現している方法)。といっても現実的には難しいので、JITコンパイルを行う場合はトレースは無効になるという制限を設けざるを得ないと思います。
インライン化されたメソッドが再定義される場合は?
当然考慮しなくてはなりません。これに関する議論も複雑です。いずれ説明したいと思います。
まとめ
proof of conceptとしては、こんなものかと思います。ベンチマークとして数字が出ると、いろいろと最適化して速度を向上させたくなりますが、早すぎる最適化はなんとやらなので、最適化はいったん区切りをつけ、言語機能の実装を再開したいと思います。
LLVMのJITサポートの現状
前回の続きで、せっかくなので、LLVMのJITサポートの現状をまとめておきます。
現行のLLVM 3.4のJITコンパイラサポートは、古くから存在するシンプルな仕組み(old JITと呼ばれます)と、MCJITと呼ばれる新しい仕組みの2種類が併存しています。今後は、old JITのサポートはやめ、MCJITに一本化する方針です。
old JITは、関数を都度コンパイルするだけのシンプルな仕組みです。未コンパイル関数の呼び出しがある場合は、スタブを生成して、呼び出し時に自動的に遅延コンパイルするようになっています。
一方MCJITは、モジュール単位でJITコンパイルを行い、コンパイル結果として完全なELFオブジェクトを生成するという重量級のアーキテクチャです。old JITにあったような遅延コンパイルの機能はないため、関数定義はモジュール内で完結するか、外部リンクにしなければなりません。また、一度コンパイルしたモジュールを再コンパイルすることもできません。そのため、実用上は、メソッドをコンパイルするたびに、そのためのモジュールを作成することになるという、動的言語のJITコンパイラのインフラとして、いささか疑問を抱かせる設計になっています。
メリットとしては、コンパイル結果のキャッシュが可能になるほか、デバッガサポートが改善するとされています。これはELFオブジェクトを生成する成果ですが、JITコンパイラに必須の機能とはいいがたいものです。
MCJITの設計については公式のドキュメントがあります。
MCJIT Design and Implementation
http://llvm.org/docs/MCJITDesignAndImplementation.html
また、LLVMの公式ブログの一連の投稿で、old JITとのパフォーマンス比較がされています。
Using MCJIT with the Kaleidoscope Tutorial
http://blog.llvm.org/2013/07/using-mcjit-with-kaleidoscope-tutorial.html
Kaleidoscope Performance with MCJIT
http://blog.llvm.org/2013/07/kaleidoscope-performance-with-mcjit.html
Object Caching with the Kaleidoscope Example Program
http://blog.llvm.org/2013/08/object-caching-with-kaleidoscope.html
投稿記事では、コンパイル時間の増大はコンパイル結果のキャッシュにより補填されると主張しています。しかし、実用的なJITコンパイラは実行時プロファイリングに基づいてspecializeされたメソッドをコンパイルするでしょうから、キャッシュが有効に機能するか疑わしいように思います。キャッシュを行わない場合、コンパイルの所要時間はold JITより増大します。また、コメント欄で指摘されているように、メモリ消費量も増加しているはずですが、比較がありません。
実際にコードを書く立場から見ても、メソッドをコンパイルする都度モジュールを生成しなければならないため、単純に手間がかかります。old JITのように、事前にヘルパ関数を定義しておくこともできません(モジュールをまたいだ外部リンクなら可能ですが、関数の宣言自体は毎回挿入しなければなりませんし、性能上も好ましくありません)。
じゃあold JITを使い続ければよいじゃないかと思われるかもしれませんが、今後、新機能はMCJITのみに実装されることになっており、それには、stack map/patch pointと呼ばれる、onstack replacementの実装に必要な機能も含まれています。old JITの開発が停止することも考えると、MCJITへの移行は避けられなさそうです。
とはいえ、移行したところでよほど効果的なキャッシュを導入しない限り性能が落ちるのがわかっていますし、前回の記事にあったように、今後アーキテクチャの変更も入りそうな情勢で、あまり気がすすみません。しばらくは悩ましい時間が続きそうです。
まあ、現在の進捗状況では、old JITで困るような段階に達してもいないわけで、悩んでる時間にコード書けよって話ではあるのでした。
LLVMの今後
5月25日のInfoQに、こんな記事が載っていました。
AppleがLLVM JITを使用してWebKitのJSエンジンをスピードアップ
http://www.infoq.com/jp/news/2014/05/safari-webkit-javascript-llvm
記事の内容自体はLLVMの活用事例ということで結構な話なのですが、気になる記載がありました。
動的言語のプロファイル指示型(profile-directed)コンパイルにLLVMが使用されたのは今回が初めてであり,LLVMの深部にまで変更が必要だった,とFilip Pizlo氏は述べている。
よく知られている通り、LLVMの開発にはAppleが深くかかわっており、主開発者もAppleに在籍しています。そのため、WebKitに合わせてLLVMも変更してしまったようです。もともとLLVMは、必要とあれば後方互換性は気にせずにAPIを変更する、と宣言しているプロジェクトであり、実際に過去にちょいちょいAPIが変更されています。今回のWebKit対応で、どのような変更がされたのか、またそれが正式リリースに反映されるのがいつなのか、気になるところです。
メソッド引数とselfを実装しました
久しぶりの更新になります。
遅々として進みませんが、開発が行き詰まっているわけではなく、仕事が多忙であまり時間がとれないためです。*1
さて、前回はベンチマークを取り、その結果、単純にJITコンパイルしただけで高速に実行されるわけではないことが判明しました。そこで最適化を実装することにしたのが前回までのあらすじになります。内部ではいろいろ実装中で、githubのコミットもそれなりに進んでいるのですが、外から見た変化はまだほとんどありません。
今回は、最適化とは別に、言語機能の追加として、メソッド引数を実装したのでご紹介します。こんなコードが動くようになりました。
# 2つの引数をとるメソッド def m(a, b) a + b end precompile Object, :m m(10, 20) # => 30
ついでに、selfも呼び出し可能になりました。selfは「隠し引数」として実装されるので、メソッド引数のついでに追加しています。
class Fixnum def add(a) self + a end end precompile Fixnum, :add 10.add(20) # => 30
今のところはinstance_evalなどのselfを変更するメソッドには未対応です。
当たり前すぎる機能で感動もないですね。以上、進捗報告でした。
先ほどのベンチマークのコードがどのようにコンパイルされたか
参考までに、先ほどのコードがどのようにコンパイルされたか見てみましょう。
元のメソッドは下記のとおりです。
def m1 i = 1 sum = 0 while i <= 10000 sum += i i += 1 end sum end
03450016 mov edi,3 ; i = 1(3は整数1のFixnum表現) 0345001B mov esi,1 ; sum = 0(1は整数0のFixnum表現) 03450020 jmp 0345007D ; 条件式にジャンプする 03450025 mov dword ptr [esp],esi 03450028 mov dword ptr [esp+4],2Bh ; 28h = '+'を表すID 03450030 call rbjit::rbjit_lookupMethod (1F51FAh) 03450035 mov dword ptr [esp+0Ch],edi 03450039 mov dword ptr [esp+4],esi 0345003D mov dword ptr [esp],eax 03450040 mov dword ptr [esp+8],1 03450048 call rbjit::rbjit_callMethod (1F4AF7h) 0345004D mov esi,eax 0345004F mov dword ptr [esp],edi 03450052 mov dword ptr [esp+4],2Bh ; 28h = '+'を表すID 0345005A call rbjit::rbjit_lookupMethod (1F51FAh) 0345005F mov dword ptr [esp+4],edi 03450063 mov dword ptr [esp],eax 03450066 mov dword ptr [esp+0Ch],3 0345006E mov dword ptr [esp+8],1 03450076 call rbjit::rbjit_callMethod (1F4AF7h) 0345007B mov edi,eax 0345007D mov dword ptr [esp],edi 03450080 mov dword ptr [esp+4],89h ; 89h = '<='を表すID 03450088 call rbjit::rbjit_lookupMethod (1F51FAh) 0345008D mov dword ptr [esp+4],edi 03450091 mov dword ptr [esp],eax 03450094 mov dword ptr [esp+0Ch],4E21h ; 4E21hは整数10000のFixnum表現 0345009C mov dword ptr [esp+8],1 034500A4 call rbjit::rbjit_callMethod (1F4AF7h) 034500A9 test eax,0FFFFFFFBh ; 真偽判定(RTEST) 034500AF jne 03450025 034500B5 mov eax,esi 034500B7 add esp,10h 034500BA pop esi 034500BB pop edi 034500BC ret
ここで、rbjit::rbjit_lookupMethodとrbjit::rbjit_callMethodは、それぞれメソッド検索及び呼び出しのためのヘルパ関数です。内部では、MRIの対応する関数に転送しています。
ローカル変数をレジスタに割り当ててたり、ジャンプ命令を1回減らすために条件式を後ろに置いたり、LLVMが頑張って最適化してくれていますが、結局はメソッド呼び出しが実行時間の大半を占めることを、なんとなく感じ取っていただけるのではないかと思います。
*1:Visual Studioのデバッガ画面からコピーしました。はてなのアセンブラ表記は大文字の16進数を正しく認識できないようで、ところどころ色がおかしいですが、気にしないでください。