RubyKaigi 2019: Write a Ruby interpreter in Ruby for Ruby 3

技術部の笹田です。フルタイム Ruby コミッタとして働いているので、明日から始まる RubyKaigi 2019 は仕事で行きます。あまり日のあたることが少ない我々の晴れの舞台です。

宣伝もかねて、RubyKaigi 中に自分がどんな仕事があるか並べてみました（クックパッド全般の話は、「クックパッド一同は、RubyKaigi 2019でみなさんにお会いできることを楽しみにしています！」 をご覧下さい）。

• 毎朝、クックパッドブースで「Cookpad Daily Ruby Puzzles」を紙で配付しますので、興味がある方はお持ち下さい。
• 1日目
  • 11:20-「Ruby 3 Progress Report」まつもとさんの keynote 後、Ruby 3 の進捗みたいなことをご紹介します。
  • 14:20-「Write a Ruby interpreter in Ruby for Ruby 3」私の accept された発表です。
  • 15:00- 休憩時間、クックパッドのブースにおりますので、ご質問がある方はお運びいただければ幸いです。
• 3日目
  • 10:00- 「Ruby Committers vs the World」恒例のコミッタを壇上に並べる出し物です。Q&A になるかと思います。https://forms.gle/f7zZt1pKCA5HTABe9 から、まつもとさんやコミッタに質問をお寄せ下さい。
  • 15:00- 休憩時間、クックパッドのブースにて、「Cookpad Daily Ruby Puzzles」の解説が遠藤さんからあるのを眺める予定です。
  • 終了後、RubyKaigi 子供会という、子供連れが集まる宴会を企画しています（保護者会だったかもしれない）。

あれ意外と少ない。京都でやったときは、一日中並列化の議論をしていた気がする。開催の前日に Developer's meeting と、翌日に after hackathon があるので、まぁやはり大変かも知れません。

さて、本稿では、私の発表、「Write a Ruby interpreter in Ruby for Ruby 3」についてご紹介します。下手な英語で発表する予定なので、こちらでは日本語で記事として残しとこうという意図になっています。

この発表は？

title_image

発表タイトルを直訳すると、「Ruby 3 にむけて、Ruby でインタプリタを書いていこうぜ」という感じになるでしょうか。

今、MRI (Matz Ruby Interpreter) は、ほぼすべて C で書かれています。タイトルを読むと、これを Ruby に全部置き換えよう、と見えるかも知れませんが、意図としては、「Ruby で書いた方がよいところは Ruby で書けるようにしよう」というものです。Ruby で Ruby をすべて self-host しよう、みたいな RubyでつくるRuby のような話ではありません。

現実的に、良い感じの仕組みを導入して、Ruby 3 をよりよくしましょう、という提案になります。

発表資料は http://www.atdot.net/~ko1/activities/2019_rubykaigi2019.pdf からダウンロード頂けます（修正等、随時更新が入ります）。

背景：現状と問題点

MRI での組込クラス・メソッドの定義の方法

現在、Ruby の組込クラス・メソッドのほとんどは、C で記述されています。String だとこんな感じ。

void
Init_String(void)
{
    rb_cString  = rb_define_class("String", rb_cObject);
    ...
    rb_define_method(rb_cString, "<=>", rb_str_cmp_m, 1);
    rb_define_method(rb_cString, "==", rb_str_equal, 1);
    rb_define_method(rb_cString, "===", rb_str_equal, 1);
    rb_define_method(rb_cString, "eql?", rb_str_eql, 1);
    ...
    rb_define_method(rb_cString, "length", rb_str_length, 0);
    rb_define_method(rb_cString, "size", rb_str_length, 0);
    ...
}

基本的に、rb_define_class というクラスでクラスを定義して、そのクラスに rb_define_method でメソッドを追加していく、というものです。rb_define_method では、名前と実装している関数、それから arity （引数の数）を指定します。String#lengthの場合は、rb_str_length という関数で実装されているようです。

VALUE
rb_str_length(VALUE str)
{
    return LONG2NUM(str_strlen(str, NULL));
}

こんな感じで、C で Ruby のメソッドが記述できます。この場合、String#length メソッドが呼ばれると、最終的には rb_str_length() が呼ばれる、というものです。C プログラマなら、見ればわかるような構造になっていて、わかりやすいです。

（実は、prelude.rb という、Ruby で定義を書く方法もあったりしますが、あまり使われていません）

なお、このように C で定義されたメソッドを C メソッド、Ruby で定義されたメソッドを Ruby メソッドと呼ぶことにしましょう。

現状の問題点

さて、このわかりやすい構造ですが、現在はいくつか問題があります。4つにまとめてみました。

• (1) アノテーション（メタデータ）の問題
• (2) 性能の問題
• (3) 生産性の問題
• (4) API に context を追加したい問題

これらの問題を解説します。

(1) アノテーション（メタデータ）の問題

C メソッドには、いくつかの意味で情報が足りていません。

(a) Ruby メソッドに比べて情報が足りません。

例えば、Method#parameters という、パラメータ名を取得刷るメソッドを利用すると、

def hello(msg) puts "Hello #{msg}"; end
p method(:hello).parameters
#=> [[:req, :msg]]

このように、Ruby メソッドの引数の名前 msg を取得することができます。他にも、バックトレース情報など、こんな感じで Ruby メソッドに比べて情報が落ちているところがあります（時々聞く、stack-prof で C メソッドが出てこなくて困る、というのは、これが理由です）。

これらは、Ruby で定義すれば、持っていたはずの情報になります。

(b) 最適化のために必要な情報が足りません。

とくに、メソッドをまたぐ最適化を行おうとすると、あるメソッドがどのような性質を持つか、例えば「副作用を持つ・持たない」という情報はとても重要になります。しかし、C で実装されたメソッドの性質を調べようとすれば、C のソースコードの解析が必要になり、現実的ではありません。

たとば、str.gsub("goodby", "hello") というプログラムでは gsub に渡した引数を弄るかも知れないので、呼び出す度に2つの文字列を生成します。しかし、gsub は引数を弄らないので、本来であれば、frozen な文字列を（毎回生成せずに）渡すだけで良いはずです。frozen-string-literal pragma を使えば、プログラマがそのように指定することができますが、煩雑です。gsub がこのようなメソッドである、という情報を付加できれば、MRI が自動的に判断できそうです（がんばれば）。

これらは、MRI 開発者ががんばって付けていく情報になります。

(c) どれくらいメソッドが定義されるか、事前にわかりません。

rb_define_method で定義すると、起動が終わらないと、あるクラスに、どれくらいのメソッドが定義されるかわかりません。わかっていれば、先にメソッドテーブルをそのサイズで確保する、みたいなことができます。が、現在そういうのができません。

定義が事前に解析出来る形で書いてあれば、得られる情報です。

(2) 性能の問題

多くの場面で、C は Ruby よりも速いです。いろんな理由がありますが（最近、なぜrubyは他の言語と比べて遅いのでしょうか？ という Quora の質問にこたえてみましたので、よかったら参考にして下さい）、まぁ適材適所、向いてる言語を使うべきでしょう。Ruby の主要部分を C で書くのは、そこそこ妥当だと思います（現代では、Rust などのより安全な言語を視野にいれるべきだとは思います）。

ですが、いくつかの場面で、実は Ruby は C で書くよりも速いことがあります。典型的な例は、キーワード引数の処理です。

# Ruby
def dummy_func_kw(k1: 1, k2: 2)
  dummy_func2(k1, k2)
end

こういう処理を C で書こうとすると、結構面倒ですがこんな感じになります。

static VALUE
tdummy_func_kw(int argc, VALUE *argv, VALUE self)
{
    VALUE h;
    ID ids[2] = {rb_intern("k1"), rb_intern("k2")};
    VALUE vals[2];

    rb_scan_args(argc, argv, "0:", &h);
    rb_get_kwargs(h, ids, 0, 2, vals);
    return tdummy_func2(self,
                        vals[0] == Qundef ? INT2FIX(1) : vals[0],
                        vals[1] == Qundef ? INT2FIX(2) : vals[1]);
}

これらのメソッドの速度を比較してみましょう。

キーワード引数のあるメソッドの呼び出しの速度比較

キーワード引数がないときは、C の方が速いです。というのも、Ruby での dummy_func2() 呼び出しは、C での tdummy_func2)() 関数呼び出しよりも圧倒的に遅いからです。

しかし、キーワードを与えると、圧倒的に Ruby で書いた方が速いです。というのも、キーワード引数のあるメソッドに、Ruby でキーワード引数を渡すときは、ハッシュオブジェクトを生成しない、特別な最適化が施されているからです。

例外処理も、同じような理由で Ruby で書いた方が速いです。

# in Ruby
def em_dummy_func_rescue
  nil
rescue
  nil
end

static VALUE
dummy_body(VALUE self)
{
    return Qnil;
}
static VALUE
dummy_rescue(VALUE self)
{
    return Qnil;
}
static VALUE
tdummy_func_rescue(VALUE self)
{
    return rb_rescue(dummy_body, self,
　　　　　　　　　　　　 dummy_rescue, self);
}

例外処理の速度比較

このように、たまにある「Ruby で書いた方がいい場合も、C で書いちゃう」という問題があります。

(3) 生産性の問題

(2) で例を出したように、Ruby だと数行のものが、C で書くと何十行、複数関数にまたがる、みたいなことがよく起きます。 C で表現するためにしょうがない部分なんですが、大変です。

例外処理やイテレータ、キーワード引数の処理なんかが該当しそうです。

また、あまり呼ばれないメソッドの場合、ささっと Ruby で定義しちゃってもいいかもしれませんね。今だと gem でやれって言われるかもしれませんが...。

余談ですが、私は C でキーワード引数の処理を書きたくなさ過ぎて、prelude.rb で Ruby 2.6 で導入した TracePoint#enable(target:) を実装しました。楽だったー。

(4) API に context を追加したい問題

rb_deifne_method() で登録する関数の引数は、基本的に self とパラメータ情報になります。しかし、我々が進めている並列処理機構である Guild では、現在の「コンテキスト」情報を渡す必要があります。mruby における mrb_state * です。

# mruby String#length
static mrb_value
mrb_str_size(mrb_state *mrb, mrb_value self)
{
  mrb_int len = RSTRING_CHAR_LEN(self);
  return mrb_fixnum_value(len);
}

Thread-local-storage (TLS) に保存する、と言う方法もありますが、とくに shared library 経由で利用すると、とても遅いことが知られています（詳細は、笹田等:Ruby 用マルチ仮想マシンによる並列処理の実現 (2012)）。そこで、第一引数に、mruby みたいに情報を引き渡したすために API の変更が必要です。

問題の最後 (4) に持ってきましたが、個人的にはこれが一番なんとかしたい問題です。ただ単に API を変更しても、なかなか追従してもらえないんですが、いろんな特典がついたほうが移行しやすいよね、という戦略です。

問題のまとめ

4つの問題をまとめました。

• (1) アノテーション（メタデータ）の問題　-> DSL が必要
• (2) 性能の問題 -> 時々 Ruby のほうが速い
• (3) 生産性の問題 -> Ruby で十分のときがある
• (4) API に context を追加したい問題

(1) は、新たにメソッド定義のための DSL があれば解決しそうです。あれ、そういえば、DSL を構築しやすい言語に心当たりがあったような？

解決案：Ruby をつかおう！

問題を解決するために、Ruby で定義もしくは宣言を行うことを考えました。すべてを Ruby で置き換えるわけではなく、C で書いた方がよいところは C で書いて、Ruby の定義から簡単に呼び出せるようにすれば（FFIの導入）、既存の資産も有効活用でき、C の圧倒的な性能も利用できて良さそうです。

Ruby で書いておけば、後から解析することで、いろいろなことがわかります。また、内部DSL的にメソッドにアノテーションを付けることも可能でしょう。

問題点はこのように解決できます。

• (1) アノテーション（メタデータ）の問題　-> Ruby で DSL を書いて解決
• (2) 性能の問題 -> 素直に Ruby が得意なところで Ruby を書けば解決
• (3) 生産性の問題 -> Ruby で簡単に済むところは Ruby で済ますことで解決
• (4) API に context を追加したい問題 -> FFI で context を渡すようにすれば解決

新しい書き方

では、具体的にどんなふうに書いていくでしょうか。

文字列のメソッドを定義する string.rb を新設し、length メソッドを定義することを考えます。

# string.rb
class String
  def length
    __ATTR__.pure
    __C__.str_length    
  end
end

# String#length impl. with new FFI
static VALUE
str_length(rb_ec_t *ec, VALUE str)
{
    return LONG2NUM(
      str_strlen(str, NULL));
}

こんな感じで、__C__.str_length と書くと、str_length() が呼ばれる、という仕組みです。

なお、__C__ は適当です。多分、変わると思います。また、特別な実行モードでのみ利用可能になると思います。普段はローカル変数（もしくはメソッド名）ですね。

__ATTR__.pure も適当にでっちあげてるだけですが、こんな感じで、String#length の属性を人間が書けるようにしていければなと思っています。

これを使うと、プログラマはこんな感じになると思います。

• Ruby の機能を使うことで、簡単に書けるところは簡単に書けるようになる。
• C の関数を簡単に呼べるので、性能を落とさずにちゃんと書けるようになる。
• いくつかの点に気を付けなければならない
  • GVL リリースや、GC タイミングなどが変わるので、気にする人はきにしないといけません。
  • 従来通りにしたければ、単に C の関数を呼び出す、というようになります。

疑問

さて、どうでしょうか。書きやすく、良さそうな感じがしないでしょうか。

ただ、きっと、パフォーマンスについて気にする人（私とか）は、次の点が気にならないでしょうか。

• ランタイムオーバヘッド：FFI で C 関数呼び出しって遅いんじゃないの？
• スタートアップ時間：Ruby スクリプトを読み込むから、スタートアップ時間が長くなってしまうんじゃないの？

この二つの疑問に答えるために、本発表では、次の二つの技術的成果についてご紹介します。

• 高速な FFI を実現するための VM 命令の追加
• ロード時間削減のためのコンパイルバイナリフォーマットの改善

ざっくり結論を申しますと、この二つの技術的成果を用いることで、C で全部書くよりは、若干遅いけど、でも十分速くなるので、多分問題ないんじゃないかな？　という感じです。

ここまできて、やっと本題にたどり着きました。

高速な FFI を実現するための VM 命令の追加

長くなったので、手短に行きます。

__C__.func(a, b) のように関数を呼び出せるようにするために、invokecfunc という命令を VM に追加しました。fiddle などのミドルウェアを用いずに C の関数を呼び出すので高速です。

# string.rb
class String
  def length
    __C__.str_length    
  end
end

こういうプログラムは、

== disasm: #<ISeq:[email protected]:10>
0000 invokecfunc                     
0002 leave

こんな感じでコンパイルされます。

ただ、invokecfunc を用いる関数呼び出しは、従来の C メソッドよりもオーバヘッドがあります。

• (1) 引数を VM スタックに push するので遅い
• (2) leave 命令でフレームを抜けるので、1命令実行が余分にかかり遅い

そこで、(1) の問題のために、__C__.func(a, b) に渡す実引数が、そのメソッドの仮引数 def foo(a, b) とまったく等しいとき、VM スタックにプッシュするのではなく、関数の引数にメソッドの引数をそのまま利用する invokecfuncwparam 命令を追加することにしました。

def dummy_func2 a, b
  __C__.dummy_func2(a, b)
end

0000 invokecfuncwparam<dummy_func2/2>
0002 leave

これで、「(1) 引数を VM スタックに push するので遅い」の問題が解決します。組み込み関数は、だいたい C で書いてある関数をそのまま呼ぶことになるんじゃないかと思うので（つまり、C 関数への delegator のような実装になるんじゃないかと思うので）、この命令を作る価値はあるのではないかと判断しました。

そして、leave をわざわざ次命令でやるのは無駄じゃないかと言うことで、invokecfuncwparam 命令の次の命令が leave の場合、その命令内でフレームを終了させる invokecfuncwparamandleave 命令を用意しました。

つまり、上記 dummy_func2 関数は、次のようにコンパイルされます。

0000 invokecfuncwparamandleave …
0002 leave

TracePoint の return イベントに対応するために、leave イベントは残す必要がありますが、基本的には invokecfuncwparamandleave 命令のみ実行するメソッドになります。

評価

さて、結果はどうなったでしょうか。

def dummy_func0
  __C__.dummy_func0
end
def dummy_func1 a
  __C__.dummy_func1(a)
end
def dummy_func2 a, b
  __C__.dummy_func2(a, b)
end

このように定義したメソッドと、これに対応する C メソッドの実装の実行時間を比べてみたのが次のグラフです。

FFIの高速化の評価結果

invokecfunc を用いるのみが baseline ですが、それだと C メソッドよりも遅かったのが、最適化を組み合わせることで、Cメソッドよりも高速に実行できることがわかります。

発表資料には、もう少しいろいろな評価があるので、そちらもご参照下さい。

まとめと今後の課題

まとめると、「FFI を用いると、ランタイムオーバヘッドは高いのでは？」という疑念に対し、「なんでもやる強い気持ちをもって最適化を行うと、問題ない（ことが多い）よ」ということです。性能を気にせず、Ruby で書けそうです。

今後の課題として、オプショナル引数などはまだ遅いので、オーバーローディングの仕組みを入れるなどして、典型的な例は速い、みたいなことを目指せればと思っています。引数の数によってメソッド実装を選ぶようなことを想定していますが、インラインキャッシュが使えるので、そこそこ feasible なのではないかと思っています。

関連研究に、私が10年前にやっていた「Ricsin: RubyにCを埋め込むシステム (2009.3)」という研究があります。これは、Ruby の中に、直接 C のプログラム片を埋め込めるようにする、という研究です。

# Writing C in Ruby code
def open_fd(path)
  fd = __C__(%q{ // passing string literals to __C__ methods
    /* C implementation */
    return INT2FIX(open(RSTRING_PTR(path), O_RDONLY));
  })
  raise 'open error' if fd == -1
  yield fd
ensure
  raise 'close error' if -1 == __C__(%q{
    /* C implmentation */
    return INT2FIX(close(FIX2INT(fd)));
  })
end

C の中から、Ruby の変数にアクセスできるのがキモ面白いところだと思っています。将来的には、こういう拡張ができるようにしても面白いかも知れないと思っています。

なお、本稿では、FFI の実装に必要になる関数テーブルの作成部分は、ちょっと面倒なので省略しました。正直、ここがブートストラップで一番難しいところなんですよね。

ロード時間削減のためのコンパイルバイナリフォーマットの改善

ランタイムオーバヘッドの懸念が解消されたら、次はスタートアップタイムが伸びてしまうんじゃないかという懸念についての返答です。Ruby でメソッドを定義するようにしたら、複数の .rb ファイルを起動時に読むから遅そうなんじゃないの、という話です。

Ruby では 2.3 から、バイトコード（MRI では ISeq という用語を使います）をバイナリにダンプする仕組みを持っています。

# dump
bin = RubyVM::InstructionSequence#to_binary

# load
RubyVM::InstructionSequence.load_from_binary(bin)

AOT コンパイルみたいな用語を使ってもいいと思います。bootsnap でも使っていますね。事前にコンパイルすることで、コンパイルのコストを抑えられるんじゃないか、という期待で作ったものです。

で、そのバイナリデータを、例えば C の配列表現にして MRI と一緒にコンパイルすれば、MRI のバイナリに統合することができます。ちなみに、起動後に mmap しても、だいたい同じような感じにすることができます。実験では、前者を使いましたが、正直最初から mmap でやればよかったな。

で、それだけだとなんなので、二つの仕組みをさらに有効にすることで、より効率的に出来るんじゃないかと思います。

Lazy ローディング

ISeq は、ツリー構造になっています。トップレベル iseq が、クラス定義 iseq をもち、それがメソッド iseq を持つ、という感じです。メソッドを起動されない限り、メソッド iseq は使われません。つまり、iseq のロードを、実際に使われるまで、遅延することができるということです。これを lazy ローディングと言います。

実は、この lazy ローディング、Ruby 2.3 の段階で入っていたんですが（vm_core.h の USE_LAZY_LOAD マクロ）、イマイチ使わないかなーと思ってたんですが、起動時に全部の iseq を作るよりも、実際に使うメソッドやブロックだけロードするほうが圧倒的に速いので、これを有効にしちゃおうかなあと思っています。

たいてい、あるプログラムで呼ばれるメソッドなんて、定義されたメソッドのごく一部でしょうから、そこそこ納得感ある話なんじゃないかと思います。

ロード済みかイチイチチェックが入るので、若干遅くなるんですが、分岐予測で十分カバー出来る範囲かな、と思っています。

なお、この仕組みについては、RubyKaigi 2015 の私の発表や、「笹田等: Ruby処理系のコンパイル済みコードの設計 (2015)」に詳しいです。もう3～4年前なんだな。

複数のファイルをサポート

現在の compiled binary は、一つのファイルが一つのバイナリを出すようにしかなっていません。しかし、複数のファイルをまとめて一つのバイナリにすれば、共有部分が増えて、リソースが若干節約できます（多分）。

そこで、複数ファイルを一つの compiled binary にまとめることができるようにしました。現在は数値インデックスでしかアクセス出来ませんが、ファイル名でアクセスできるように拡張する予定です。

bin = RubyVM::InstructionSequence.to_binary(iseq1, iseq2, ...) と複数の iseq を読み込み、

loader = RubyVM::InstructionSequence::Loader.new(bin)
iseq0 = loader.laod(0)

のように取り出すことができるようにしてみました。

評価

評価のために、3000個のクラス C0～C2999 を作り、各クラスが 1～20個のメソッドを持つ（def m0; m; endのような単純なメソッド。全合計3万メソッドくらい）、というサンプルを作って実験してみました。

• 1ファイルに詰め込む場合
  • .rb が 582KB
  • compiled binary が 16MB
  • それを C の配列表現にすると 79MB（！）
• 各クラスごとにファイルを作る
  • .rb が 3000 個
  • まとめた compiled binary が 17MB
  • それを C の配列表現にすると 86MB
• 従来の C メソッドでの定義の仕方を用いると、4.2MB の .c

この3通りを用いて、ロードして Ruby が起動する時間をはかってみました。なお、--disable-gems で rubygems などのライブラリはロードしないようになっています。

結果は次のようになりました。

ロード時間の評価結果

結果を見ると、従来の C での定義が最も速く 27.5 秒で、lazy loading を用いることで、だいたい 2 倍程度の性能低下で済む、という具合です。

単なる compiled binary のロードだと 3 倍遅い。普通に .rb としてロードするよりも6～16倍程度遅い、という結果になりました（一番下の結果ひどいな）。というわけで、従来手法に比べると、やはり速いのだけれど、まだ C メソッド定義に及ばず、というところです。

まとめと今後の課題

工夫によって、スタートアップタイムについては、従来の C メソッドのロード時間より大幅に遅い、ということはなかったのですが、まだ若干遅いです。もう少しなんとかならないでしょうか。

.rb を書いておくと、事前にどのクラスにどんなメソッドが定義される、というのがわかるので、先にテーブルだけ作っておいて、メソッド問い合わせが来たときに初めて iseq のロードを始めるような、より lazy なやり方なんかが効くんじゃ無いかと思います。そこまでやれば、C メソッドのロードよりも速くなるんじゃないかな？

あと、単純にコンパイル済みバイナリがむっちゃでかいんですよね。わざと小さくしないようにしたんですが、さすがに大きすぎなのでなんとかしたい。多分、簡単に 1/5 くらいにはなると思います。誰かやってくれません？

本稿のまとめ

本稿では、私の RubyKaigi 2019 の発表である「Write a Ruby interpreter in Ruby for Ruby 3」について述べました。

現在 MRI では、ほぼすべて C で記述されていますが、それを良い感じに Ruby と混ぜるために、特別な FFI 記法の導入を提案しました。

そして、そこで懸念される「ランタイムオーバヘッド」および「スタートアップタイムの増加」について、いくつかのテクニックをご紹介し、そこそこ feasible な結果を出すことで、懸念をそこそこ払拭できたんじゃないかと思います。

現在の組込クラス・メソッドの定義を書き換えるとなると、多くの人手が必要になります。まだ、この方針で Ruby 3 向け（Ruby 2.7 向けかな？）に書き換えるという合意は取れていませんが、取れたらばばばーと書き換える作業が発生します。ある程度機械的な作業になるんですが、良い機会なので興味がある方、一緒にやりませんか？

われわれは Ruby Hack Challenge　というイベントを開催しており、次回は Ruby Hack Challenge Holiday #3 が 5/11 (土) に行います。こういう場で、Ruby (MRI) 開発に参加してくれる方がいらっしゃいましたら、お声かけ頂けましたら幸いです。

というわけで、RubyKaigi 2019 でお会いできることを楽しみにしております。