Ruby 開発チームに4週間インターン生として参加いたしました、永山 (GitHub: NagayamaRyoga) です。私は「Ruby中間表現のバイナリ出力の改善」という課題に取り組み、Railsアプリケーションのコンパイルキャッシュのサイズを70%以上削減することに成功しました。以下ではこの課題の概要とその成果について述べたいと思います。

InstructionSequenceの概要

まず、RubyVM 内で実行される命令の中間表現、InstructionSequence (以下 ISeq と省略) について簡単に説明します。

通常の Ruby プログラムは、以下のような手順で実行されます。

ソースコードを構文解析し、抽象構文木を作る。
抽象構文木をコンパイルして、ISeq を作る。
RubyVM (YARV) で ISeq を解釈し、実行する。

ISeq は、このように RubyVM で解釈される命令列に関する情報を含んだ一種の中間表現です。

ISeq に関する API は RubyVM::InstructionSequence としてその一部が外部に公開されているため、Ruby プログラムからも (ごく簡単な操作に限ってですが) 取り扱うことが可能です。

# 文字列をコンパイルして ISeq を得る
iseq = RubyVM::InstructionSequence.compile("p 42")

# 得られた ISeq を RubyVM で実行する
iseq.eval
# => 42

# ISeq に含まれている命令列を出力する
puts iseq.disasm
# => == disasm: #<ISeq:<compiled>@<compiled>:1 (1,0)-(1,4)> (catch: FALSE)
#    0000 putself                                                          (   1)[Li]
#    0001 putobject                    42
#    0003 opt_send_without_block       <callinfo!mid:p, argc:1, FCALL|ARGS_SIMPLE>, <callcache>
#    0006 leave

また、#to_binary メソッドを呼び出すことで ISeq をバイナリデータにシリアライズすることができます。

bin = iseq.to_binary
p bin
# => "YARB\x02\x00\x00\x00\a\x00\x00\x00D......"

もちろん、シリアライズされたバイナリデータから ISeq に戻すことも可能です。

iseq2 = RubyVM::InstructionSequence.load_from_binary(bin)
iseq2.eval
# => 42

コンパイルキャッシュとBootsnap

では、上の機能がどのように活用できるのかについて説明したいと思います。

先程も述べた通り、Ruby プログラムは実行されるたびにスクリプトファイルの構文解析が行われます。

ソースコードを構文解析し、抽象構文木を作る。

抽象構文木をコンパイルして、ISeq を作る。

RubyVM (YARV) で ISeq を解釈し、実行する。

しかし、スクリプトファイルが変更されていなけば、コンパイル結果として得られる ISeq が実行ごとに変化するようなことはありません。同じ ISeq が得られるにも関わらず、構文解析やコンパイルが行われるのは冗長です。

特に、短時間に何回も実行されるようなプログラムや、多数のスクリプトファイルで構成される巨大なアプリケーションではコンパイル結果 (ISeq) をバイナリデータとしてキャッシュしておくとその起動速度を向上できるかもしれません。

Rails5.2以降ではデフォルトでプロジェクトにインストールされる Bootsnap という gem は、前項で説明した #to_binary メソッドを使って、スクリプトファイルのコンパイル結果を自動的に ./tmp/ 以下のディレクトリにキャッシュしてくれます。 Bootsnapはこの他にもautoloadしたファイルのパスなどをキャッシュすることでRailsプロジェクトの起動時間を50%〜70%程度縮めることに成功しています。例えば、$ rails new によって生成されただけの空のRailsプロジェクトでは、Bootsnapによって起動時間が約65%短くなるのを確認できました。

課題

さて、この #to_binary ですが、その出力にはかなりの無駄があります。

iseq = RubyVM::InstructionSequence.compile("p 42")
p iseq.to_binary.length
# => 580

p 42というごく小さいコードから生成されたバイナリにも関わらず、その出力は 580byte という大きさになってしまいました (出力のサイズは環境によって異なります)。

当然、より大きいコードからは大きいバイナリが生成されます。さきほどの空Railsプロジェクトであれば、Bootsnapが1632個の.rbファイルをキャッシュしており、そのキャッシュファイルの合計サイズは 32MB ほどになりました。

というわけで、本課題の目的はこの #to_binary の出力するバイナリのサイズを小さくすることです。 #to_binary の出力が小さくなると単純にストレージや転送時間の節約になるほか、Bootsnapがコンパイルキャッシュにアクセスする際のディスクアクセスが少なくなるため、Railsアプリケーションの起動時間が短くなることが期待されます。

方法

#to_binary の実装の大部分は Ruby の compile.c に書かれています。

今回のインターンシップではこの実装を読みつつ、部分部分を書き換えていくことで徐々に出力のサイズを小さくしていきました。

特にバイナリサイズの削減に寄与した変更は主に以下の2つです。

1. 不要な構造体フィールドの出力の削除

従来の実装では ISeq の情報を格納した構造体の、本来出力する必要のないものや、常に同じ定数が出力されているフィールドなどが存在していました。コードを読み解いて、それらを出力に含めないようにすることでバイナリのサイズを削減しました。

2. 整数値の符号化方法を変更

また、出力に含まれていたあらゆる整数値はほぼすべてが固定長で符号化され、4byteや8byteのデータ長で出力されていました。しかし、出力される整数値はその出現頻度に大きな偏りがあり、多くが 0 や 1 などの少ないbit数で表現できる値です。そこで、UTF-8を参考に可変長な整数の符号化方法を考え、導入することにしました。

0x0000000000000000 - 0x000000000000007f: 1byte | XXXXXXX1 |
0x0000000000000080 - 0x0000000000003fff: 2byte | XXXXXX10 | XXXXXXXX |
0x0000000000004000 - 0x00000000001fffff: 3byte | XXXXX100 | XXXXXXXX | XXXXXXXX |
0x0000000000020000 - 0x000000000fffffff: 4byte | XXXX1000 | XXXXXXXX | XXXXXXXX | XXXXXXXX |
...
0x0001000000000000 - 0x00ffffffffffffff: 8byte | 10000000 | XXXXXXXX | XXXXXXXX | XXXXXXXX | XXXXXXXX | XXXXXXXX | XXXXXXXX | XXXXXXXX |
0x0100000000000000 - 0xffffffffffffffff: 9byte | 00000000 | XXXXXXXX | XXXXXXXX | XXXXXXXX | XXXXXXXX | XXXXXXXX | XXXXXXXX | XXXXXXXX | XXXXXXXX |

この方法では、7bitで十分に表現できる値は1byteに、14bitで表現できる値は2byteに、というように符号化する整数の大きさによって必要なバイト長を変化させています。

UTF-8では1byte目の上位bitを使って後続のバイト数を表しているのに対して、この符号化方法では下位bitの連続する0bitの個数でバイト数を表現しています。このような形式を採用した理由は、x86_64などの命令セットではbsfやtzcntといった命令を用いることで後続のバイト数が1命令で数えられるためです。

評価

これらの変更によって、バイナリの読み込み速度を損なうことなく #to_binary の出力のサイズを平均して 70%から75% 程度小さくすることに成功しました。上記の空Railsプロジェクトでは、キャッシュファイルのサイズは合計 9.4MB (元の約30%) になりました。

f:id:NagayamaRyoga:20190926141101p:plain

その他の詳細なデータに関しては以下のチケットにまとめてあります。

https://bugs.ruby-lang.org/issues/16163

苦労した点

以下、今回の課題に取り組むにあたって苦労した点です。

プロジェクトの規模が大きいこと

Rubyは20年以上も継続して開発が続けられているプロジェクトであり、1万に近い個数のファイルによって構成されています。特にC言語で記述されたソースコードの中には1ファイルが1万行を超えているものもあり、 (今回の実装に関連する部分はそのごくごく一部とは言え)処理の流れを把握するのが大変でした。

インターン期間の最初の1日は、ソースコードを読みながらバイナリデータを手でデコードし、おおよその処理の流れとデータ構造を理解していきました。

マルチプラットフォームなソフトウェアであること

Rubyは様々なOS、CPU、etcで実行される可能性のあるプログラムです。そのため、どのような環境であっても正しく動作をするようにプログラムを書く必要がありますが、 C言語はその言語仕様の詳細 (例えば整数型のサイズと表現可能な数値の範囲、式の評価方法、評価結果など) の一部を"処理系定義"としています。

"処理系定義"の動作はコンパイラや環境によって異なる可能性があるため、ある環境では動作をするが別の環境では動作しない、というようなことが起こらないように常に意識をする必要がありました。