msumimz's diary

RubyにJITコンパイラを実装する個人プロジェクトの情報発信ブログです。

フルRubyのビルドに対応しました

今まではminirubyのみだったのですが、今回、フルのRubyのビルドに対応しました(Windowsの32bit版のみ)。

ベースとなるRubyのバージョンは2.1.0です。LLVMはバージョン3.4を使っています。ビルドにはVisual Studio 10以降が必要です。

ビルド手順は、以下の通りです。

  1. LLVM公式サイトにあるGetting Started with the LLVM System using Microsoft Visual Studio — LLVM 3.4 documentationの指示に従って、LLVMをインストールします。
  2. githubからソースコードを入手します。
    git clone https://github.com/msumimz/ruby/tree/rbjit
  3. Visual Studioコマンド・プロンプト」を起動します。以後は、このコマンドプロンプトから作業します。
  4. 2.で入手したソースファイルのあるディレクトリに移動します。
  5. LLVMの場所を指定するため、win32\configure.batに「--llvm-prefix」というオプションを追加しています。1.でインストールしたLLVMライブラリの場所を、--llvm-prefixの引数に指定してwin32\configure.batを実行します。
  6. あとは通常のビルドと同じようにnmakeします。
  7. 必要に応じて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は以下のように単純なものになります。

f:id:msumimz:20140701221044p:plain

図の読み方ですが、ボックスがそれぞれ制御の単位を表します。今回は、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)なら右辺の値になる、というように、「明らかに型がわかる変数から波及させて、順に型を推定していく」というものになります。

メソッド呼び出しの場合は、

  1. レシーバの型を推定する。
  2. レシーバの型とメソッド名から、呼び出され得るメソッドを検索する。
  3. そのメソッドが返し得る型の和集合を左辺値の型とする。

という手順になります。

メソッドが返し得る型」をどうやって取得するのかが問題になりますが、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がプリミティブを表します。なんとなく理解できるでしょうか。

f:id:msumimz:20140701220236p:plain

これを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の範囲を超えない限り、メソッド呼び出しが発生しませんので高速です。

f:id:msumimz:20140701221050p:plain

レシーバの型が推定できない場合

例として示したメソッドの定義が、以下のような内容だったらどうでしょうか。

def m(a)
  a + 1 + 2
end

この場合、最初の'+'メソッドのレシーバは変数aですが、この変数の型は不明ですので、呼び出されるメソッドが特定できず、インライン化もできないことになります。

これに対応するには、2つの方法があります。

  1. メソッド名が'+'や'-'などの場合は、レシーバはFixnumの可能性が高いと仮定して最適化してしまう。
  2. 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としては、こんなものかと思います。ベンチマークとして数字が出ると、いろいろと最適化して速度を向上させたくなりますが、早すぎる最適化はなんとやらなので、最適化はいったん区切りをつけ、言語機能の実装を再開したいと思います。

*1:田中育男「コンパイラの構成と最適化 第2版」(浅倉書店、2009)pp.367--369。ただし、型推論にこのアルゴリズムを適用すると、停止性(進行性)が保証されない気がします。そのうち検討します。

LLVMのJITサポートの現状

前回の続きで、せっかくなので、LLVMJITサポートの現状をまとめておきます。

現行の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に、こんな記事が載っていました。

AppleLLVM 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対応で、どのような変更がされたのか、またそれが正式リリースに反映されるのがいつなのか、気になるところです。

復帰報告

ようやく仕事の繁忙期が終わりまして余裕ができましたので、JITコンパイラの開発を再開したいと思います。

その前に、リハビリてがら小さなツールをつくったりしました。

Autocompo
https://github.com/msumimz/autocompo

ちょっとした画像合成ツールです。写真が趣味の人は興味があるかもしれません。

メソッド引数と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を変更するメソッドには未対応です。

当たり前すぎる機能で感動もないですね。以上、進捗報告でした。

*1:あと、いまだにSkyrimとかやっているためです。

先ほどのベンチマークのコードがどのようにコンパイルされたか

参考までに、先ほどのコードがどのようにコンパイルされたか見てみましょう。

元のメソッドは下記のとおりです。

def m1
  i = 1
  sum = 0
  while i <= 10000
    sum += i
    i += 1
  end
  sum
end

JITコンパイルされた結果は以下の通りです。*1

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進数を正しく認識できないようで、ところどころ色がおかしいですが、気にしないでください。