rurubyのガベージコレクタとアロケータ

この記事は言語実装AdventCalendar 2021の24日目の記事です。

rurubyって何

rurubyは、かれこれ２年ほどRustでチマチマ書いているRuby処理系です。一応CRuby¹ 3.0互換を目指していて、構成としてはCRubyと同じ仮想マシン（VM）インタプリタです。現在の状況としては、Ruby2.7の文法はおおむねカバーしており基本的な組み込みクラスやメソッドも実装していますが、完全ではありません。Rubyで書かれたライブラリもある程度動きますが、rurubyはまだC拡張をサポートしていないため、全く動かないものもまだまだ多くあります。

rurubyのGitHubレポジトリ

１年の進捗

昨年・一昨年は
AdventCalendar 2020：ruruby: RustでつくっているRuby
AdventCalendar 2019：Rustでつくる（つくれるかもしれない）Ruby
という記事を書きましたが、今年１年の進捗としては@mameさんが書いたQuine²をいくつか動くようにしたこと、処理系内部を地道に改良して高速化したことでしょうか。例えば下記のtweetのQuineを動かすのにBignum（可変長整数）の実装が必要でした。Quine駆動開発。
今はruby/specというRubyのための標準テストスイートをクリアしようとしています。

難解quine、動いた〜
Bignumの演算がバグっていた pic.twitter.com/Kqk15ycPyw

— monochrome (@s_isshiki1969) August 15, 2021

高速化

高速化については本題ではないのでデータを並べるのみにとどめますが、だいぶCRubyに近づいてきました（JITなし）。rateはCRubyに比べて何倍遅いかを示しています。

benchmark	CRuby 3.0	ruruby	rate
optcarrot	56.35 ± 0.25 fps	33.55 ± 0.05 fps	x 1.68
optcarrot --opt	129.89 ± 0.69 fps	110.14 ± 0.28 fps	x 1.18

benchmark	CRuby 3.0	ruruby	rate
so_mandelbrot.rb	1.17 ± 0.03 s	1.34 ± 0.00 s	x 1.14
app_mandelbrot.rb	0.81 ± 0.00 s	1.02 ± 0.00 s	x 1.26
app_fibo.rb	0.55 ± 0.01 s	0.71 ± 0.00 s	x 1.30
app_aobench.rb	5.89 ± 0.19 s	9.19 ± 0.03 s	x 1.56
so_nbody.rb	0.76 ± 0.01 s	1.10 ± 0.00 s	x 1.45
collatz.rb	5.82 ± 0.01 s	6.58 ± 0.01 s	x 1.13

さて、今回はrurubyにおけるオブジェクトのメモリ表現と、これをハンドリングするアロケータ・ガベージコレクタについて解説します。

Rubyオブジェクトのデータ構造

まず、動的型付き³オブジェクト指向言語であるRubyにおけるオブジェクトがrurubyの内部でどのように表現されているかを説明します。rurubyのオブジェクトの内部表現はCRubyのそれに大変よく似ていて⁴、笹田さんの連載記事（WEB+DB PRESS Vol.110「Rubyのウラガワ」）の第１回に大変分かりやすく解説されているので正直そちらを見て頂いた方がよいのですが、今回の本題であるメモリ管理の説明の前提として必要な話なので、ここで簡単に説明します。

Value

rurubyのオブジェクトは内部的にはValueと呼ぶ8バイトの構造体で表現されます。Rubyオブジェクトの全情報を8バイトで表現するのは当然無理なので、基本的には後述するRValue構造体（64バイト）へのポインタになっています。一方で整数など、頻繁に演算に使用される値をいちいちヒープアロケートするのは効率が悪いので、ポインタの下位3ビットをタグとして使い、残りの61ビットを使って整数、浮動小数点数、真偽値などの値を表現しています。実際には下図のようにIntegerは最下位1ビット、Floatは下から2番目のビットを立てることで表現していますが、その分データを表すビット数が足りなくなり、63ビット整数と62ビット浮動小数点数しか表現できません。この範囲を超える整数・浮動小数点数は、64バイトのRValueを使って表現しています。

RValue

Rubyオブジェクトの本体はRValueという64バイトの構造体になっています⁴。RValueはclass（オブジェクトのクラス、8バイト）、var_table（インスタンス変数テーブル、8バイト）、kind（オブジェクトの内部情報、40バイト）の各フィールドの他、オブジェクトの種類を示すタグと状態を表す各種フラグを格納するflagsから構成されます。実際にはflagsはタグだけではなく、ガベージコレクタが使用する空スロットへのポインタ（後述）との共用体（union）になっています。

例えばArrayクラスのオブジェクトであれば、flagsにはArrayタイプ⁵のオブジェクトであることを示すタグが入り、classにはArrayクラスオブジェクトのValue、kindにはオブジェクトの配列への参照が入ります。

kindの中身がどうなっているのかは本題とあまり関係ないので省略しますが、基本的にはunionになっていて⁶、例えば文字列オブジェクトなら文字列への参照、配列オブジェクトならValueの配列への参照などが入っています。データを読むときはflagsのタグを見て適切なデータ型として読みます。興味のある方はunion: RubyでRustがunsafeになった話をご参照ください（Rustを書く人向けの記事になっています）。なお、最適化の一環として、短い文字列や配列の場合はヒープアロケートせずにそのままkindの中に押し込んでいます。

struct RValue {
    flags: RVFlag,
    class: Value,
    var_table: Option<Box<ValueTable>>,
    kind: ObjKind,
}

union RVFlag {
    flag: u64,
    next: Option<std::ptr::NonNull<RValue>>,
}

アロケータとガベージコレクタ

RValueはVMが新たなオブジェクトを生成するたびにヒープに確保されます。一方、プログラムの実行に従って不要になったRValueは随時破棄して再利用する必要があります。RValueを一つ一つmallocすると遅いので、実際にはアロケータによりページという単位でひとまとめに管理されており、１ページには64x63個のRValue（用のスロット）が並んでいます。

下の図はrurubyにおけるアロケータとガベージコレクタの動作の概要を示しています。アロケータは、VMから要求が来るとまずページの頭からスロットを一つずつ渡していきます。（Bump allocationと呼ばれている）

ある程度の個数がアロケートされるとガベージコレクタ（GC）が起動する。

ガベージコレクタはVMから到達可能なオブジェクトを片っ端からたどっていく。実行中のメソッドチェーン内のローカル変数やグローバルに参照できるクラスオブジェクトなどから、各オブジェクトのインスタンス変数、配列オブジェクトであれば配列の全ての要素、ハッシュオブジェクトならすべてのキーと値など、すべてのオブジェクトを巡回して、マーク⁷していく。

グレーのボックス内にあるオブジェクトはVMから見えない、つまり未来永劫使用されることのないオブジェクトなので中身を消去し、フリーリストにつないでいく。

以後、アロケータは新たなオブジェクトの要求に対してフリーリストから１つづつスロットを外してVMへ渡す。もしフリーリストが空になったら、最初のようにページの先頭からVMへ渡す。

フリーリストが空で、かつページの全てのスロットを割り当ててしまった場合にはアロケータは新しいページを確保し、また先頭のスロットから順にVMに渡していく。

以上、ガベージコレクタとしては最も初歩的なものになっています⁶。もちろん、CRubyのGCではさらに多くの高速化の工夫がなされています。

GC開発にまつわる諸問題

いつGCするか問題

GCの処理はすごく重いので、GCの回数が多すぎるとオーバーヘッドが大きくなり、かつGCを行ってもスロットをほとんど回収できない可能性があります。少なすぎるとメモリ消費が増えます。GCをどのタイミングで起動するかという問題はなかなか難しく、アロケーションのパターンもアプリケーション依存なので常に最適となる一般的な方法はありません。

当初はページがある程度埋まるたびにGCを起動するようにしていましたが、GCのトリガーがそれだけだとアプリケーションによってヒープの消費が極端に増えてしまうパターンがありました。これは、例えばArrayオブジェクトに配列要素がどんどん足されるケースで、足される要素がヒープアロケートされない整数や浮動小数点数だとRValueのkindフィールドにぶらさがっている配列（RustではVec）がどんどん大きくなりますが、ヒープオブジェクトの数は増えないのでGCが起動せず、不必要にメモリ使用量が増えることになります。そこで、RValueのアロケーション数を監視するだけではなく、mallocをフックしてヒープアロケート量全体を監視することとすることで、「オブジェクトの数は増えないがヒープアロケーションが増加するケース」でも適切なタイミングでGCを起動することができるようになりました。これはrurubyのオリジナルではなくて、CRubyも同じような仕組みを持っています。

下記は現状の消費メモリ量の比較です。rateが少ない方がメモリ消費が少ないです。

benchmark	CRuby 3.0	ruruby	rate
app_mandelbrot.rb	22.3M	6.6M	x 0.29
app_aobench.rb	22.7M	6.6M	x 0.29
so_concatenate.rb	72.6M	19.3M	x 0.27
optcarrot	78.2M	63.0M	x 0.81
optcarrot --opt	85.7M	83.1M	x 0.97

バグってSEGVする問題

未定義動作を許さない言語であるRustといえども、GCを書くとどうしてもunsafeコードになり、最初のうちはバグによりSEGVが頻発しました。GCのバグは再現性に乏しかったり、実際にバグを踏む場所ではなくてもっと後になって死んだり死ななかったりして、デバッグが困難なケースが多いです。「死んでいない」オブジェクトをGCが回収してしまって死ぬ、というのが多いのですが、下記に１例を紹介して供養することとします。

[1,2,3].map {|x| x.to_s }という式を考えます。to_sはRubyでレシーバを文字列化するメソッドです。

• VMが上記の式を実行すると、数値の配列に対しArrayクラスのmapメソッドを呼び出す。このメソッドはRustで書かれている。
• mapメソッドは配列の要素を一つづつ取り出して、渡されたブロック{|x| x.to_s }（クロージャ）を呼び出す。このメソッドはRubyで書かれているのでVMの実行ルーチンを再帰的に呼び出し、値を得る。得られた値は保存する。
• 配列をイテレートし終えたら、得られた値を配列にして返す。
  

一見問題なく動くように見えますが、

• 右側のVM呼び出しの中ではオブジェクトのアロケートが起こるので時々GCが走る
• Rustで書かれたmapメソッドのなかで、VMから返ってきて保存している文字列オブジェクト（"1" "2"）はRustのスタック上に置かれるためVMからは見えない
• そのためGCで文字列オブジェクトが回収されてしまう
• 後でVM実行に戻ってから、得られたオブジェクトの要素（GCに回収されてしまっている）を読もうとして死亡する

この、うっかりVMの目が届かない場所にオブジェクトを置いたままVMを呼び出して死亡するパターンはよく遭遇しますので、みなさまGCを作るときはご注意ください。

まとめ

GCはつらいよ。
また来年お会いしましょう。よいお年を。

1. Rubyの処理系は数多くあり、その中でまつもとゆきひろさんが作った最初のRuby処理系を（C言語で書かれているので）CRubyと呼ぶ。 ↩

2. Quineは「自身のソースコードと完全に同じ文字列を出力するプログラム(Wikipedia)」で、そんなものを動かすことに何の意味があるのかという疑問を持たれると思うが、@mameさんの作品はQuineの定義を満たした上でさらに山手線を一周したり、しぶきを飛ばしたり 、漢字がほどけたりするので見てて楽しいというのがモチベになる。あと一般にはあまり使われていない謎の文法や機能が駆使されているので、勉強になる。（役に立つとは言っていない） ↩

3. 「型無し」が正しい、という声もある。 ↩

4. もちろん、rurubyがCRubyをパクったためです。 ↩ ↩²

5. Arrayクラスだけではなく、そのサブクラスもすべて「Arrayタイプ」のタグとkindの構造を持つことになる。 ↩

6. Rustにはenumという便利なタグ付きunionがあるのでそれを使うと簡単だが、それだとタグに8バイト使われてしまうので、現在は環境にやさしいけど危険なunionで実装している。何のためにRustで書いてんだ感ある。 ↩ ↩²

7. マークをどこに置くかはいろいろな方法があり一長一短あるが、rurubyでは専用のビットマップを用意して、その中の１ビットを１つのオブジェクトのマークに使っている（bitmap marking）。ページ全体のマークをスキャンするのが簡単。局所性もよさそう。 ↩