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

この記事は[言語実装AdventCalendar 2021](https://qiita.com/advent-calendar/2021/lang_dev)の24日目の記事です。

## rurubyって何

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

[rurubyのGitHubレポジトリ](https://github.com/sisshiki1969/ruruby)

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

### １年の進捗

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

<blockquote class="twitter-tweet"><p lang="ja" dir="ltr">難解quine、動いた〜<br>Bignumの演算がバグっていた <a href="https://t.co/Kqk15ycPyw">pic.twitter.com/Kqk15ycPyw</a></p>&mdash; monochrome (@s_isshiki1969) <a href="https://twitter.com/s_isshiki1969/status/1426819577929891842?ref_src=twsrc%5Etfw">August 15, 2021</a></blockquote> <script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>

### 高速化

高速化については本題ではないのでデータを並べるのみにとどめますが、だいぶ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におけるオブジェクトのメモリ表現と、これをハンドリングするアロケータ・ガベージコレクタについて解説します。

[^2]: Quineは「自身のソースコードと完全に同じ文字列を出力するプログラム([Wikipedia](https://ja.wikipedia.org/wiki/%E3%82%AF%E3%83%AF%E3%82%A4%E3%83%B3_(%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0)#:~:text=%E3%82%AF%E3%83%AF%E3%82%A4%E3%83%B3%EF%BC%88%E8%8B%B1%3A%20Quine%EF%BC%89%E3%81%AF,%E3%82%92%E6%9B%B8%E3%81%8F%E3%81%93%E3%81%A8%E3%81%8C%E3%81%82%E3%82%8B%E3%80%82&text=%E3%81%9D%E3%81%AE%E3%82%88%E3%81%86%E3%81%AA%E7%A9%BA%E3%81%AE,%E5%8F%97%E8%B3%9E%E3%81%97%E3%81%9F%E3%81%93%E3%81%A8%E3%82%82%E3%81%82%E3%82%8B%E3%80%82))」で、そんなものを動かすことに何の意味があるのかという疑問を持たれると思うが、[@mame](https://github.com/mame)さんの作品はQuineの定義を満たした上でさらに[山手線を一周したり](https://github.com/mame/yamanote-quine)、[しぶきを飛ばしたり](https://mametter.hatenablog.com/entry/2020/08/05/150835) 、[漢字がほどけたり](https://github.com/mame/sonny-boy-nankai)するので見てて楽しいというのがモチベになる。あと一般にはあまり使われていない謎の文法や機能が駆使されているので、勉強になる。（役に立つとは言っていない）

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

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

[^3]: 「型無し」が正しい、という声もある。
[^4]: もちろん、rurubyがCRubyをパクったためです。

### Value

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

### RValue

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

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

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

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

[^4]: `Value`や`RValue`という構造体名はCRubyの構造体の名前をそのまま使用しています。
[^7]: Rustにはenumという便利なタグ付きunionがあるのでそれを使うと簡単だが、それだとタグに8バイト使われてしまうので、現在は環境にやさしいけど危険なunionで実装している。何のためにRustで書いてんだ感ある。

```Rust
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と呼ばれている）
![Bump Allocation](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/332404/e71e9858-fc7c-cbee-e943-38155f0d6347.png)
ある程度の個数がアロケートされるとガベージコレクタ（GC）が起動する。
![Invoke GC](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/332404/c4c834a5-e037-f27f-70fe-22c0b74f2621.png)
ガベージコレクタはVMから到達可能なオブジェクトを片っ端からたどっていく。実行中のメソッドチェーン内のローカル変数やグローバルに参照できるクラスオブジェクトなどから、各オブジェクトのインスタンス変数、配列オブジェクトであれば配列の全ての要素、ハッシュオブジェクトならすべてのキーと値など、すべてのオブジェクトを巡回して、マーク[^6]していく。
![Mark](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/332404/711e423b-361f-e692-d633-fe84dcef2a37.png)
グレーのボックス内にあるオブジェクトはVMから見えない、つまり未来永劫使用されることのないオブジェクトなので中身を消去し、フリーリストにつないでいく。
![Sweep](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/332404/e8608304-6b3b-dcfd-27da-cac7d748eb5b.png)
以後、アロケータは新たなオブジェクトの要求に対してフリーリストから１つづつスロットを外してVMへ渡す。もしフリーリストが空になったら、最初のようにページの先頭からVMへ渡す。
![Free List Allocation](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/332404/348bf1a8-aef3-0eb1-a8fa-3fd2a85f8950.png)
フリーリストが空で、かつページの全てのスロットを割り当ててしまった場合にはアロケータは新しいページを確保し、また先頭のスロットから順にVMに渡していく。

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

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

[^7]: もっとも素朴なGCですら普通にバグって死ぬので、コンカレントGCとか世代別GCとかコピー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の実行ルーチンを再帰的に呼び出し、値を得る。得られた値は保存する。
- 配列をイテレートし終えたら、得られた値を配列にして返す。
![Lost_objects](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/332404/89f61b93-f047-8291-aa2c-45d8d3245c79.png)

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

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

![Lost_objects2](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/332404/fae12f57-15f5-8195-baa9-5e5f33454993.png)

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

## まとめ

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