Ruby の NODE を GC から卒業させた

こんにちは、技術部のフルタイム Ruby コミッタの遠藤（@mametter）です。メリークリスマス。

本日 Ruby 2.5.0 がリリース予定です。いろいろな改善が含まれています。クックパッドからの主な貢献としては、「trace 命令の削除による高速化」や「分岐・メソッドカバレッジの測定のサポート」などがあります。

ユーザから見える改善はいろいろと記事が出てくると思うので、この記事では、「抽象構文木のメモリ管理のリファクタリング」というあまりユーザから見えない改善を紹介してみます。

概要

Ruby のパーサは、NODE という内部的なオブジェクトで構成された抽象構文木を生成します。2.4 までの NODE は GC に管理される普通のオブジェクトでしたが、2.5 からは GC の外で管理するようになりました。これにより、3 つ嬉しいことがあります。

  • 大きなコードのパースが速くなりました。
  • NODE に詳細なコード位置情報（カラム情報）を載せることができました。
  • 将来的に NODE まわりのコードを整理できる準備ができました。

背景

NODE は、Ruby の抽象構文木のノードを表現する要素です。抽象構文木はソースコード文字列をプログラムで扱いやすい木構造として表現したものです。知らない人は拙著『Ruby でつくる Ruby』などを読んでください :-)

2.4 の NODE は GC に管理されるオブジェクトとして実装されていました。Ruby のオブジェクトは GC の制約で 5 ワード長と決まっています。そのうち 2 ワードは NODE の種別や行番号を表現するために予約されていて、自由に使えるのは 3 ワードのみでした。イメージ的には、長さが 3 で固定されている配列みたいなものです。

この方法には 3 つの問題がありました。

  • パース中に無駄な GC が起きる
  • 抽象構文木に詳細なコード位置情報を載せる余地がない
  • 抽象構文木の表現にムリ・ムダがある

パース中に無駄な GC が起きる

大きなコードをパースする際に NODE オブジェクトが大量に生成され、GC が走ってしまいます。しかも生成中の NODE は回収できないので、この GC はほぼ完全に無駄です。この現象は、a = 1 が大量に並ぶコードを実行すると観測できます。

図：eval("a = 1\n" * N) の実行時間（x 軸は行数 N 、y 軸は時間）

a = 1 が N 行並ぶコードの実行時間を、N を変えながら計測したものです。実行時間が非線形に増えていっているのがわかります。これはパース中に起きる GC のせいです。1 回の GC にかかる時間は O(N) 、GC が起きる回数は O(log N) なので、全体で O(N log N) の時間がかかります。

抽象構文木に詳細なコード位置情報を載せる余地がない

NODE には、その NODE に対応するコードの行番号だけが記録されていました。バックトレースの表示や行カバレッジの測定などでは、この情報だけで十分でした。

しかし、2.5 では分岐カバレッジをサポートすることになりました。分岐は同一の行の中で複数個現れることが普通にあるため、分岐カバレッジのレポートで「どの分岐の実行回数であるか」を示すために、カラム番号（行内で左から何番目か）が必要になりました。また、メソッドカバレッジのレポートでも、開始位置（def の位置）だけではなく終了位置（end の位置）もある方が便利でしょう。

しかし、大きさが限られている NODE には、これらの情報を載せるための場所がありませんでした。

抽象構文木の表現にムリ・ムダがある

3 ワード制限のために、Ruby の抽象構文木にはムリ・ムダが生じています。たとえば true を表すノード NODE_TRUE は、子ノードを持たないので、3 ワードがまるまるムダになってます。逆に、obj.attr += val を表すノード NODE_OP_ASGN2 は情報を 4 つ持つ *1 ので、2 つの NODE をカスケードさせて無理やり表現しています。

おまけ：昔は GC 管理する意味があったが、今はもう意味がない

Ruby 1.8 のころは、抽象構文木をトラバースする方式でインタプリタが実装されていました。このような実装では、抽象構文木が不要になるタイミングが自明ではないので、GC 管理に任せたい気持ちも理解できます。

しかし Ruby 1.9 では YARV が導入され、YARV コンパイラが抽象構文木をバイトコードに変換したあとは、抽象構文木はもう使われません。つまり、パースから実行開始までのわずかな期間だけのために、少なくない NODE オブジェクトを作って捨てることになります。世代別 GC が導入されたから実害はあまりないですが、ムダはムダです。

やったこと

NODE を GC 管理されるオブジェクトとしてではなく、ただの malloc されたバッファの中に確保するようにしました。大量に NODE を作っても、malloc バッファが増えるだけで GC のオブジェクトバッファは圧迫されないので、無意味な GC 起動は基本的に起きません。

主に大変だったのは次の 3 つです。

NODE が NODE 以外のオブジェクトを指すケースの検出と対応

NODE の子どもは基本的に NODE ですが、一部の NODE は NODE 以外のオブジェクトを指すことがあります。たとえばリテラルを表す NODE_LIT は、そのリテラルオブジェクト（文字列や配列など）を参照します。 NODE は GC 管理オブジェクトではないので、これらのオブジェクトはマークされません。そのままでは回収されてしまいます。そこで、NODE のバッファの他に、マークが必要なオブジェクトを管理する配列（mark_ary）を用意し、NODE が NODE 以外のオブジェクトを指すタイミングで mark_ary に追加するようにしました。*2

NODE を目的外使用しているコードの削除

NODE は抽象構文木のためのものなのに、「自動的に free される便利なデータ構造」として転用されてしまっていました。NODE_ALLOCA（自動的に free される一時的バッファ）と、NODE_HEREDOC（ヒアドキュメント関係のパーサの状態を管理するための一時的データ構造）で、いずれも抽象構文木の一部にはなりません。これらは imemo と言われる別種の内部オブジェクトに置き換えて対応しました。

Ripper 対応

Ripper は NODE が GC 管理オブジェクトであることを仮定して書かれているので、切り離しが大変でした。実は完全には切り離せておらず、NODE の先頭ワードはオブジェクトと同じ構造でないといけません *3 。これはいずれなんとかしたいと思っています。

結果

この改善により、背景に上げた 3 つの問題が解決しました（または解決のめどが立ちました）。

パース中の無駄な GC がなくなった

大きなコードの eval が線形になりました。

図：eval("a = 1\n" * N) の実行時間（x 軸は行数 N 、y 軸は時間）

グラフ的には圧倒的ですが、正直この改善が現実世界で生きてくることはあんまり期待できないと思っています。クックパッドの全ソースコードのパースで評価すると、2.67 秒が 2.60 秒になった程度でした。まあ、10,000,000 行のコードとか書きませんよね。コードを自動生成しているプロジェクトでは、ひょっとしたら役立つかもしれません。

笹田コメント：「おまけ：昔は GC 管理する意味があったが、今はもう意味がない」にあるように、Ruby 1.9 から NODE を GC 対象にする必要はないことはわかっており、ずっとやりたいと思ってペンディングしていたところ、遠藤さんが入社して一瞬で作ってくれました。ただ、当初は GC 回数が減るので、もっと性能インパクトがあるかと思ったんですが、現実的なコードでは影響がほとんどなく、意外でした。世代別 GC の性能が十分高い、ということだと思います。

NODE に範囲情報をもたせた

NODE が GC 管理から外れて自由に拡張できるようになりました。今までは各 NODE は開始行番号しか持っていませんでしたが、今は次の 4 つの情報を持っています。

  • 開始行番号
  • 開始カラム番号
  • 終端行番号
  • 終端カラム番号

分岐カバレッジ・メソッドカバレッジはこの情報にもとづいて測定結果を出力します。 また、カラム情報は他にも利用価値がありそうです。たとえば、NoMethodError が起きた箇所を行番号だけでなくカラム番号も出すことで、より詳細に位置を特定できるようにできるかも。

抽象構文木の表現のムリ・ムダを省いていける準備ができた

NODE が自由に使える領域は 3 ワードに限らなくなったので、今後はより柔軟に拡張できます。Ruby のソースコードのうち、評価器部分は YARV への置き換えで大きく整理されましたが、パーサ部分は未整理のまま拡張され続けてきていて、現在は Ruby の中でも最もわかりにくいソースコードの 1 つになっています。メンテナンスの観点でも、将来的に型システムを検討する土台としても、わかりやすくてメモリ効率的によいものになるように整理を進めたいと考えています。

まとめ

Ruby 2.5 NODE を GC 管理から外すことで、(1) パース時の無駄な GC を抑えた、(2) NODE の位置情報を詳細化した、(3) 抽象構文木の整理を進める土台を確立した、という改善を行いました。

謝辞：改良の方針や実装について弊社笹田とたくさん相談しました。また、bison を使って NODE の位置情報を実際に実装していくのは @yui-knk さんがやってくれました。ありがとうございます。

*1:レシーバ obj 、読み書きする attr 、演算子 + 、値 val 。

*2:mark_ary は YARV のコンパイラでも使われているテクニックです。

*3:RB_TYPE_P(obj, T_NODE) によって、NODE かそれ以外かを区別できないといけない。