2014-4-(3): 情報処理学会プログラミング研究会 発表資料 2014 年 11 月 10 日

Ruby におけるライトバリアのないオブジェクトを考慮した
世代別インクリメンタル GC の実装○笹田 耕一1,a)

松本 行弘1,b)

概要：
ガーベージコレクション（GC）の改善手法として世代別 GC、およびインクリメンタル GC はよく知られているが、実装するためには正確なライトバリアの挿入が必須である。一方、Ruby 処理系は保守的マーク＆スイープ GC を用いることで、C 言語などで拡張コードを書くときに余計なコードを含む必要がなかったが、ライトバリアを挿入しておらず、これを必要とする GC アルゴリズムを導入することができなかった。我々はこの問題を解決するために、ライトバリアに対応しているオブジェクトとしていないオブジェ
クトを区別して、世代別インクリメンタル GC を実装する新しい方法を提案する。本発表では提案する手法について説明し、Ruby への実装について述べる。

Implementation of a generational incremental garbage collector withwrite barrier unprotected objects on Ruby
Koichi Sasada1,a)Yukihiro Matsumoto1,b)Abstract:
Generational GC and incremental GC are well known algorithms to improve performance of garbage collector,
and they require correct write barriers in the interpreter. On the other hands, Ruby interpreter uses conservertive mark and sweep GC, and we can implement C extensions easily without any extra codes. However,Ruby interepreter does not have any write barriers and we can not implement GC algirithms which require
correct write barriers. To solve this problem, we propose new technique to implement generational andincremental GC by separating all objects into write barrier protected objects and write barrier unprotected
objects. In this presentation, we will describe new technique and an implementation on Ruby interpreter.

本稿では、Ruby 処理系と単に呼ぶとき、この我々が開発

1. はじめにしている Ruby インタプリタを指すこととする。

オブジェクト指向プログラミング言語 Ruby[3] は、ウェ

2004 年ごろから、Ruby で記述されたウェブアプリケー

ブアプリケーション開発などの分野で世界中で広く利用さション開発フレームワークである Ruby on Rails などが登れている。Ruby で書かれたプログラムを実行するための場し、例えば、初期のバージョンの Twitter や、github な

インタプリタはいくつか存在するが、我々が開発している

ど、多くのアプリケーションが Ruby で開発されるように*1

Ruby インタプリタがもっとも多く利用されている [4] 。

なった。このような背景から、Ruby 処理系に対する性能の要求は高くなってきている。

1
a)
b)
*1

Heroku, Inc.
ko1@heroku.com
matz@heroku.com
MRI や CRuby とも呼ばれる。他には、Java で開発された JRuby
や、インタプリタの大部分を Ruby 自体で記述した Rubinius がある。

Ruby 処理系の性能にはいくつか改善を要する要素があるが、その 1 つにガーベージコレクション（GC）があげられる。GC は、他のオブジェクト指向プログラミング言語と同様に、不要となったオブジェクトを自動的に回収し、

1

2014-4-(3): 情報処理学会プログラミング研究会 発表資料 2014 年 11 月 10 日

メモリなどの計算機資源を再利用可能にするための機構

した世代別およびインクリメンタル GC について紹介し、である。Ruby 処理系は、1993 年の開発当初から、保守的

Ruby への実装について述べる。

マークアンドスイープを利用してきた。しかし、Ruby が用いる保守的マークアンドスイープは、多くのオブジェク
トが存在するとき、処理性能が低く、停止時間が長いという問題がある。
例えば Ruby がよく利用されるウェブアプリケーション

2. 世代別 GC とインクリメンタル GC
本章では世代別 GC とインクリメンタル GC についての概要を述べる。これらのアルゴリズムには、多くの基礎研究があるため、詳細は適切な文献を参照されたい。

の分野では、処理性能が遅いと単位時間あたりに処理することができる HTTP リクエスト数が減り、必要な計算機

2.1 世代別 GC

リソースが増えるという問題がある。また停止時間が長い

処理性能を上げるための手法の 1 つとして、世代別 GC[1]と 1 リクエストにかかる時間が増え、エンドユーザの待ちが知られている。世代別 GC は、オブジェクトの空間を、時間が増え、問題となる。

オブジェクトの世代ごとに複数に分割し、GC を行なう範

処理性能を向上する方法として世代別 GC、停止時間を

囲を、可能な限り新しい世代のみに限定する手法である。

短くする手法としてインクリメンタル GC が知られてい若い世代のオブジェクトのみを対象とする GC をマイナーる [1]。しかし、これらの手法ではライトバリアという、オGC、古い世代のオブジェクトも対象にする GC をメジャー

ブジェクトへの書き込みを検知する手法を実装する必要がGC という。経験的に、マイナー GC のみで十分なことがある。

多いため、この方法によって処理性能が改善することが知Ruby 処理系は C 言語で実装されているが、保守的マーられている。

クアンドスイープアルゴリズムを前提としているため、そ世代別 GC は古い世代から新しい世代への参照を発見の実装にはライトバリアが一切入っていなかった。また、し、間違って回収することがないように覚えておく（リメRuby 処理系を C 言語で拡張する拡張ライブラリでも、ランバーセットに登録する）など、適切に処理する必要があ

イトバリアが無い。Ruby 処理系への適切なライトバリア

る。マイナー GC では、リメンバーセットに登録されたオ

挿入は、不可能ではないが、ミスが許されない作業であり、ブジェクトをルートとすることで、正しく生きているオブ

高い開発コストが必要になる。また、拡張ライブラリへのジェクトとして扱うことができる。この世代間の参照を発ライトバリアの導入は、既存の拡張ライブラリに非互換を見するために、ライトバリアというテクニックがよく利用もたらし、これまで開発されてきた C 拡張ライブラリが利される。

用できなくなるという問題がある。そのため、世代別 GCやインクリメンタル GC が実装できなかった。

ライトバリアは、書き込み（ライト）により、あるオブジェクトの状態変更を検知するプログラミングテクニック

我々は、この問題を解決するため、ライトバリアのないである。世代別 GC では、ライトバリアによって、あるオ

オブジェクトを考慮した世代別 GC、およびインクリメン

ブジェクト A から他のオブジェクト B へ参照が追加され

タル GC を考案し、Ruby 処理系に実装した。考案したア

たことを検知し、A と B の世代を確認し、A が B よりも

ルゴリズムでは、ライトバリアに対応していないオブジェ

古い世代であれば、リメンバーセットへ登録する。

クトがあっても適切に動作するため、既存の拡張ライブラ
リがそのまま動作する。

例えば、Ruby プログラムでは、配列オブジェクト ary
が古い世代のオブジェクトであり、オブジェクト obj が考案した世代別 GC は、従来の手法よりも若干制限があ

新しい世代のオブジェクトであったとき、ary[0] = obj

り、性能が低くなる可能性があるため、Restricted Genra-というプログラムによって、旧世代のオブジェクトから新tional GC（RGenGC）と名付けた。同様に、考案したイ

世代のオブジェクトへの参照が生まれる。このような操作

ンクリメンタル GC は従来の方式よりも停止時間が長くなを、ライトバリアによって検出する必要がある。

ることがあるので、Restricted incremental GC（RincGC）と名付けた。
評価の結果、制限がありながらも、これまでの保守的
マークアンドスイープ GC に比べ、処理性能が向上し、停世代別 GC により、処理性能が改善する。ただし、マイナー GC による停止時間は、メジャー GC よりも短いが、メジャー GC による停止時間は長く、最悪停止時間は改善しない。

止時間が短くなったことが確認出来た。
なお、考案した世代別 GC アルゴリズムを導入した Ruby

2.2 インクリメンタル GC

処理系を 2013 年 12 月に Ruby 2.1 としてリリースした。さ

停止時間に関しては、短くするための手法の 1 つとして、らにインクリメンタル GC アルゴリズムを実装した Ruby

インクリメンタル GC[1] が知られている。インクリメンタ

処理系を 2014 年 12 月にリリース予定である。

ル GC は、GC 処理を複数の処理に分割し、対象プログラ

本稿では、このライトバリアのないオブジェクトを考慮

ム（ミューテータ）と交互に進めていき、対象プログラム2

2014-4-(3): 情報処理学会プログラミング研究会 発表資料 2014 年 11 月 10 日の処理を長時間停止しないようにするテクニックである。

魅力を大きく損ねることになる。

ここでは、その中の 1 つを紹介する。
このアルゴリズムでは、オブジェクトに白、灰、黒とい

そこで、我々はライトバリアで保護しないオブジェクトを考慮した世代別 GC、およびインクリメンタル GC アル

う色をつけ、次のように進めていく。

ゴリズムを考案し、これを組み合わせ、ライトバリアが不完( 1 ) GC 開始時にすべてのオブジェクトを白色にする。

全であっても動作する世代別インクリメンタル GC を実現( 2 ) ルートセットに含まれるオブジェクトを灰色にする。

した。それぞれ制限付き世代別 GC（RGenGC: Restricted( 3 ) 灰色のオブジェクトのどれか（オブジェクト A）を取Generational GC）、および制限付きインクリメンタル GC

り出し、そこから参照されるオブジェクトを灰色にす（RincGC: Restricted Incremental GC）と呼ぶ。

る。A から参照されるオブジェクトがすべて灰色、もしくは黒色とすれば、A を黒色にする。これを、灰色

3.1 キーアイデアのオブジェクトがなくなるまで繰り返す。

( 4 ) 白色のオブジェクトは、参照されないオブジェクトなので回収できる。

本提案のキーアイデアは、各オブジェクトに、ライトバ
リアが適切に処理されるかどうか区別する、というものである。あるオブジェクト A へ書き込みが行なわれ、A が他

3 の手続きを分割し、ミューテータと交互に実行するこのオブジェクトへの参照があったことを検知することが保とで、対象プログラムの停止時間を短くする。ただし、対障できるとき、A をライトバリアで保護されたオブジェク

象プログラムの総実行時間が短くなるわけではない。

ト（以降、Protected オブジェクト）とし、そうでなけれ

インクリメンタル GC では、ミューテータ実行時に黒色のオブジェクトから白色のオブジェクトへの参照が生成さば A をライトバリアで保護されないオブジェクト（以降、Unprotected オブジェクト）とする。

れることがある。このとき、黒色のオブジェクトから参照

例えば Ruby 処理系であれば、オブジェクトの取り扱されるオブジェクトが灰色から黒色である、という前提条

いはクラスごとに実装されているため、あるクラス C の件が崩れてしまうため問題となる。

実装にライトバリアを完全に挿入すれば、クラス C のイ

この黒色から白色のオブジェクトへの参照生成を検知す

ンスタンスはすべて、Protected オブジェクトといえる。

るため、世代別 GC と同様にライトバリアを利用する。ラ

それ以外の、未対応のクラスのインスタンスについては、

イトバリアによって、オブジェクト A から B への参照がUnprotected オブジェクトとする。Ruby における String

生成されたとき、A が黒色で B が白色だったとき、A を黒クラスのオブジェクトを例にすると、ほとんど他のオブ色から灰色に戻す、もしくは B を白色から灰色にする。

ジェクトへの参照を生成しない *2 ため、対応は容易である。クラスによって、この容易さは異なる。

2.3 世代別インクリメンタル GC

また、Ruby 処理系の拡張ライブラリでは、ある操作を世代別 GC とインクリメンタル GC は、とくに問題無く行なうと、それ以降あるオブジェクトについてライトバリ

共存できるため、素直に世代別インクリメンタル GC を実アを保障することができないような操作が存在する。例え装することができる。たとえば、停止時間が長いメジャー

ば、拡張ライブラリでは、Array（配列）クラスのオブジェ

GC のみをインクリメンタルにすることがでる。

クトの配列の要素を管理するメモリブロックのポインタを

3. ライトバリアで保護しないオブジェクトを考慮した世代別インクリメンタル GC

理系では、このポインタが指し示すメモリブロックにオブ

1 章で説明したとおり、Ruby 処理系には適切なライト

拡張ライブラリでもこのようなプログラムはいくつか存在

バリアが存在せず、従来の世代別 GC、もしくはインクリした。このような処理が行なわれると、参照の生成は検知

メンタル GC を導入するのは困難である。

できない。そこで、このようにある Array オブジェクトの取得することができる（RARRAY_PTR() マクロ）。Ruby 処ジェクトへの参照を書き込む、ということが許されており、

ライトバリアを適切に挿入するには、(1) 大きな開発コ

メモリブロックのポインタを取り出したとき、Array オブ

ストという問題と、(2) 互換性の問題がある。ライトバリ

ジェクトが Protected オブジェクトであったなら、これをアが必要な箇所で、1 箇所でも挿入を忘れると、重大な問

Unprotected オブジェクトへ変更する。これを、Unprotect

題となるため、既存のソフトウェアを精査し、改変する必操作と呼ぶ。

要がある。しかし、Ruby 処理系では、ライトバリアを必まとめると、オブジェクトをライトバリアで保護する要とする箇所が多くあり、漏れなく対応するのは困難な作

Protected オブジェクト、保護しない Unprotected オブジェ業である。また、Ruby 処理系を拡張するための拡張ライ
ブラリにもライトバリアを必須とすると、過去に開発された拡張ライブラリが利用できなくなり、過去のソフトウェ
ア資産を放棄することになり、プログラミング言語環境の*2

Ruby のすべてのオブジェクトは、インスタンス変数経由でその他のオブジェクトを参照可能であるため、String オブジェクトが他のオブジェクトを参照することもある。ただし、このインスタンス変数の追加のような処理は、共通ルーチンを利用しているため、ライトバリアの挿入は容易である。

3

2014-4-(3): 情報処理学会プログラミング研究会 発表資料 2014 年 11 月 10 日

クトに大別し、ライトバリアで保護できないと判断できる

ブジェクトと呼ぶこともできるが、ライトバリア時に「旧タイミングで Protected オブジェクトを Unprotected オブ

世代オブジェクトから参照される新世代オブジェクト」をジェクトへ変更する Unprotected 操作がある。

検知するが、リメンバーセットに追加された Unprotected

このアイデアを使い、世代別 GC、およびインクリメン
タル GC アルゴリズムを実現する。

オブジェクトは必ずルートセットとなるため、この検知対象とする必要がない。そのため、Unprotected オブジェク
トは新世代オブジェクト、ということにする。

3.2 RGenGC: 制限付き世代別 GC
簡単のために、新世代と旧世代、2 世代を管理する世代
別 GC を用いて説明する。

この方式では、リメンバーセットに登録された Unpro-

tected オブジェクトがルートとして加わるため、従来の世代別 GC よりもマイナー GC にかかる時間が多くなる。

世代別 GC でライトバリアが必要となるのは、旧世代オ
ブジェクトから新世代オブジェクトへの参照が生成されたことを検知するためである。ただし、Unprotected オブ

3.3 RincGC: 制限付きインクリメンタル GC
RGenGC と同様に、次のルールをインクリメンタル GC

ジェクトはライトバリアがないため、この生成を検知できアルゴリズムに追加する。

ない。

( 1 ) すべてのオブジェクトを黒色に変更した後、生きていそこで、世代別 GC のアルゴリズムに次のルールを新たに加え、健全性を保つ。

( 1 ) Unprotected オブジェクトは旧世代にしない。

る黒色の Unprotected オブジェクトをルートセットとして、再度停止 GC を行なう。
黒色 Unprotected オブジェクトはライトバリアで保護( 2 ) 旧世代のオブジェクトから Unprotected オブジェク

されないため、ミューテータが実行中に白色のオブジェ

ト A への参照を発見したら、A をリメンバーセット

クトへの参照が生成されている可能性がある。そのため、に追加する。なお、リメンバーセットに追加された

インクリメンタル GC の最後に、全ての Unprotected オ

Unprotected オブジェクトは、次のメジャー GC まで

ブジェクトをルートとした停止 GC を行い、生きている

リメンバーセットから外されず、次のメジャー GC ま

Unprotected オブジェクトから辿ることができるすべてので生き続ける *3 。

オブジェクトを黒色にする。

( 3 ) 旧世代オブジェクト B が Unprotect 操作により、Unprotected オブジェクトとなったら、B を新世代のUnprotected オブジェクトに変更し、B をリメンバー
セットに追加する。
まず、(1) は、Unprotected オブジェクトは旧世代から新世代への参照を検知できないため、旧世代にすることはできないためである。

この 1 つのルールにより、インクリメンタル GC が適切に動作する。
本方式では、当然のことながら、生きている Unprotected
オブジェクトの数に比例した停止時間がかかるため、従来のインクリメンタル GC よりも最悪停止時間が長くなる。
なお、インクリメンタル GC アルゴリズムの説明で、最後にルートの再スキャンする、としているものもある。こ次に (2) は、旧世代オブジェクト A から参照される新世

れは、ミューテータによって、ルートセットに白色オブ

代オブジェクト B を発見したとき、B を旧世代にするな

ジェクトが加わる可能性があるためである。ルートを 1 つ

どして、適切に処理するが、B が Unprotected オブジェクのオブジェクト R として捉え、R が Unprotected オブジェ

トのとき、旧世代にすることができないため、リメンバー

クトとすれば、本提案と同様となる。

セットに登録し、マイナー GC 期間中、ずっと生きておくようにする。

(3) は、旧世代オブジェクト B が、他の旧世代オブジェク

3.4 議論
今回提案する RGenGC、および RincGC について議論

トのみから参照されている可能性があり、その時マイナーする。

GC では誰からも辿ることができないため、B を生き残ら

3.4.1 段階的な開発せる必要があるためである。
この (1)〜(3) のルールを追加することで、世代別 GC を適切に機能させることができる。

従来、ライトバリアを必要とする GC アルゴリズムを導入するためには、ライトバリアが適切に実装されている必要があった。しかし、本提案では、まずはすべてを

なお、旧世代オブジェクトから参照される、リメンバー

Unprotected オブジェクトとしておき、順次 Protected オ

セットに追加された Unprotected オブジェクトを旧世代オ

ブジェクトを増やす、という戦略をとることができる。この戦略では、まずは実装が容易な箇所や、よく利用される*3

旧世代オブジェクト X が新世代オブジェクト Y を参照したとき、X をリメンバーセットに入れるが、マイナー GC 終了後、リメンバーセットから外され、次のマイナー GC 時にはルートにならない。

オブジェクトからライトバリアを整備していくことができる。
例えば Ruby では、文字列オブジェクトや配列オブジェ

42014-4-(3): 情報処理学会プログラミング研究会 発表資料 2014 年 11 月 10 日

クト、ハッシュオブジェクトが多く利用されるため、これトとしていながら、ライトバリアの実装漏れが存在すると、ら頻出オブジェクトを、まずは集中的に実装することがで重大な問題となる。ライトバリアの挿入漏れを防ぐためにきた。逆に、あまり利用されないような機能や、生成されは、別途チェック機構を用意する必要がある。

るオブジェクトの数が少ないオブジェクトは、Unprotected
オブジェクトのままでも処理性能、および停止時間に与える影響が少ないため、Protected オブジェクトに作り替えることを後回しにすることができ、開発リソースを有効に

4. Ruby への実装
我々は、提案する手法を Ruby 処理系に構築した。本章
では、実装のポイントとなる部分を紹介する。

活用することができた。
また、本質的にライトバリアを入れるのが困難である、

4.1 世代別インクリメンタルマーキング

もしくはとても複雑なプログラミングが必要であるような

今回は、保守的マークアンドスイープ GC のマーク部

場合、性能や停止時間を犠牲にしても、バグの無い実装を分を世代別・インクリメンタル GC とした。もともと、ス

提供するため、Unprotected オブジェクトのままにしてお

イープ処理をインクリメンタルに処理する Lazy sweep とく、という判断ができる。この点も、他のライトバリアをいう機構は実装されていたため、マーク部をインクリメン

必要とする GC アルゴリズムには無い利点である。

タル GC とした。

例えば、Ruby 処理系においては、Module オブジェク

保守的であるため、マイナー GC においてよく利用されトへの適切なライトバリアの挿入が困難であった。というるコピー GC などの移動型 GC アルゴリズムは利用できなのも、複数の Module オブジェクトが 1 つのデータ構造をいため、マイナー GC、およびメジャー GC ともにマーク共有していたためである。そのため、Module オブジェク

アンドスイープ GC を用いている。

トについてはライトバリア挿入を諦める、という判断を行世代は新世代と旧世代の 2 世代として実装した。Pro-なった。

tected オブジェクトは、4 回 GC を生き残ると、旧世代オ

3.4.2 RGenGC における性能低下

ブジェクトに昇格するようにした。

RGenGC では、リメンバーセットに登録される Unprotected オブジェクトが増えると、ルートセットが大きくな

4.2 ビットマップの利用

るため、従来の世代別 GC にくらべ、マイナー GC にかか

もともと、Ruby 処理系ではあるオブジェクトがマークさる時間が長くなる。リメンバーセットに追加しなければなれたことを表現するために、各オブジェクトに対応する 1らない Unprotected オブジェクトは、次の 2 通り考えら

ビットを集めた、ビットマップとして表現していた（Markれる。

bitmap）。そこで、これに加える形で次のビットマップを( 1 ) GC 時、旧世代オブジェクトから参照された Unpro-用意した。

tected オブジェクト( 2 ) Unprotect 操作で旧世代オブジェクトから Unprotected
オブジェクトとなったオブジェクト
経験上、旧世代オブジェクトからの参照はあまり増える( 1 ) Unprotected bitmap( 2 ) Long lived bitmap( 3 ) Marking bitmap( 4 ) Remember old bitmap

ことはないため、(1) は少ない。また、Unprotect 操作自Unprotected bitmap では、オブジェクトが Protected

体も、あまり多くないため、これらの条件での性能低下はか Unprotected かを示す。Long lived bitmap では、世代あまり起きないので無いかと期待できる。

別 GC における旧世代オブジェクトか、リメンバーセッ

3.4.3 RincGC における停止時間の増加

トに登録された Unprotected オブジェクトが表現される。

RincGC では、インクリメンタル GC の最後に停止 GC

Marking bitmap は、インクリメンタル GC における灰色によって、生きている（黒色の）Unprotected オブジェク

オブジェクトを表現する。Remembered old bitmap では、トをルートセットとして再スキャンを行なう。そのため、世代別 GC における、リメンバーセットに登録された旧世少なくとも、生きている Unprotected オブジェクトの数に代オブジェクトを表現する。

比例した停止時間がかかる。

例えば、マイナー GC 時にマークする必要があるリメン

RGenGC のマイナー GC の停止時間を考えてみると、すバーセットは、次のように取得することができる。Remem-

べての生きている Unprotected オブジェクトを辿るため、

bered old bitmap と（Long lived bitmap と Unprotected

少なくとも、この数に比例した停止時間がかかる。つまり、

bitmap の論理積）の論理和で得ることができる。

マイナー GC の停止時間と同等か、それより短いことが期

また、RincGC で最後に必要となる生きている Unpro-待できる。

tected オブジェクトの集合は、Mark bitmap と Unprotected

3.4.4 ライトバリア挿入漏れ

bitmap の論理積で得ることができる。

本手法でも、あるオブジェクトを Protected オブジェク

なお、Remember old bitmap はマイナー GC でのみ、

52014-4-(3): 情報処理学会プログラミング研究会 発表資料 2014 年 11 月 10 日

Marking bitmap はメジャー GC でのみ利用されるため、同じメモリ領域を共用している。

図 6 に、RDoc プログラムを実行されたとき、確保されたスロット（1 オブジェクトを格納する領域）の数、生きてい

RGenGC および RincGC のために、各オブジェクトに 3るオブジェクトを格納しているスロットの数（つまり、生ビット追加していることになる。100 万オブジェクト（1M

きているオブジェクトの数）、旧世代のオブジェクトの数、

オブジェクト）で試算すると、3bit∗1M = 3M bit = 375KB

Unprotected オブジェクトの数、リメンバーセットに記録さのメモリ使用量の増加となる。

れた Unprotected オブジェクトの数がどのように推移するかを示す。また、図 7 に後者 2 つのみの結果を表示する。こ4.3 RGenGC におけるメジャー GC タイミング

れを見ると、RDoc プログラムでは、Unprotected オブジェ

Ruby 処理系は GC 終了時、確保できる空きスロットのクト、およびリメンバーセットに記録された Unprotected

数が少なければ、ヒープを拡張する。この時、マイナー GC

オブジェクトの数が、他のオブジェクトに比べて十分少な

時に空きスロットの数が少なければ、メジャー GC を実行

いことが確認できる。そのため、マイナー GC への性能のする、というようにした。

影響が殆ど出なかったと考えられる。また、Unprotected

5. 評価

オブジェクトが増えても、リメンバーセットに記録されるものは少ない、ということがわかる。

Ruby 処 理 系 に 実 装 し た RGenGC、お よ び 、そ れ に
RincGC を 加 え た も の で 本 手 法 の 評 価 を 行 な う 。評 価

5.2 RincGC

環 境 は Intel(R) Core(TM) i7-4930K CPU @ 3.40GHz

図 8 に、前節で示したマクロベンチマークプログラムの、上の Ubuntu 14.04.1 LTS (GNU/Linux 3.13.0-37-generic

GC による停止時間の長い順に上位 2048 個を、RGenGC（たx86 64) で 行 な っ た 。対 象 と す る Ruby 処 理 系 は ruby

だし、強制的にメジャー GC を起動する）、および RincGC

2.2.0dev (2014-11-09 trunk 48334) [x86 64-linux] を用いで実行した結果を示す。

た。

結果を見ると、意図と反して RincGC のほうが最悪停止
時間が長いことがわかる。まだ詳しく調査出来ていない

5.1 RGenGC

が、実装上の問題ではないかと思われる。

まず、次に示すマイクロベンチマークを実行し、マーク

RDoc アプリケーションでは、通常の RGenGC、およ

時間、およびスイープ時間がどのようになるか調査する。

び、それに RincGC を加えたもので実行し、GC 処理によ

スイープの時間計測を確実にするため、インクリメンタ

る停止時間の長い順に上位 256 個を表示したものを図 9 にルにスイープを行なう Lazy Sweep 機構は切って評価を行示す。こちらでは若干効果が見えるが、あまり大きな効果なった。

ではない。インクリメンタル GC の起動タイミングや各ス# Make 1M objects (long lived)

テップの停止時間の選択方法などに、まだ課題が残っていary = (1..1_000_000).map{|e| Object.new}

ると思われる。

# Make short-lived 100M objects

6. 関連研究

100_000_000.times{Object.new}
このプログラムでは、まず旧世代のオブジェクトを 100

世代別 GC、およびインクリメンタル GC には関連研究万個作成し、さらに短寿命オブジェクトを 1 億個生成するが多くあるが、必要となるライトバリアをいかに挿入するというプログラムである。結果を図 1、図 2 に示す。

か、という点を議論する研究は多くない。これは、モダン

図 1 を見ると、各 GC において、RGenGC によって、なプログラミング言語処理系では、ライトバリア（もしくマーク時間が大幅に短縮できていることがわかる。ただし、はそれに代わるもの）を前提に開発が進められるからではスイープ時間は余分にかかっていることが確認できる。ス

ないかと思われる。

イープ時間には変更がないと期待されるため、何らかの実装の不備が考えられる。

数少ない研究として、花井らは処理系を記述する言語を解析し、自動的にライトバリアを挿入する手法を提案して次に、Rdoc という Ruby のソースコードを読み込み、ドいる [2]。この手法では、ほぼ漏れなくライトバリアが挿入

キュメントを生成するプログラムを走らせた結果を、図 3、できるが、解析の限界による挿入漏れがあり得ること、挿図 4、図 5 に示す。

入のしすぎがあり得ること、それから専用の解析器が必要

図 3 を見ると、マイナー GC により、ほとんどの GC 時となることといった問題点がある。

間が少なくなっていることがわかる。また、いくつかのライトバリアではなく、ハードウェアのページ保護機能

ピークが観測できるが、これはメジャー GC であると予想を用いてライトバリアの代わりにする手法もよく知られてされる。結果的に、マークにかかる時間を 8 倍程度圧縮すいる [1] が、ページ保護機能は移植性が低いという点や、ることができたことがわかった。

Ruby のデータ構造にあわない、という問題がある。

6

2014-4-(3): 情報処理学会プログラミング研究会 発表資料 2014 年 11 月 10 日

7. まとめ
本稿では、正確なライトバリアが必須であるとされる世代別 GC、およびインクリメンタル GC について、ライトバ
リアを適切に導入することが困難な Ruby 処理系に導入するために、ライトバリアに対応した Protected オブジェク
トと対応しない Unprotected オブジェクトを用いて、世代別 GC、およびインクリメンタル GC を実現するアルゴリ
ズムを提案した。そして、提案したアルゴリズムを Ruby
処理系に実装し、性能改善、および停止時間の短縮に効果があることを示した。
今回実装した世代別 GC では、マーク処理のみを世代別とするため、スイープ処理の時間は変わらない。そのため、スイープ時間のさらなる削減が必要である。
開発した Ruby 処理系は、RGenGC を組み込んだもの
を Ruby 2.1 として 2013 年 12 月にリリースし、これにRincGC を組み込んだものを Ruby 2.2 として 2014 年 12月にリリースする予定である。
参考文献
[1]

[2]

[3]
[4]

Jones, R., Hosking, A. and Moss, E.: The Garbage Collection Handbook: The Art of Automatic Memory Management, CRC Applied Algorithms and Data Structures,
Chapman & Hall (2012).
花 井 亮 ，小 宮 常 康 ，八 杉 昌 宏 ，湯 淺 太 一：Scheme
処理系における C 言語拡張コードへのライトバリ
ア 自 動 挿 入 ，情 報 処 理 学 会 論 文 誌. プ ロ グ ラ ミ ン
グ， Vol. 44, No. 4, pp. 17–24（オンライン），入手先⟨http://ci.nii.ac.jp/naid/110002711929/⟩ (2003).
松本行弘：Ruby の真実，情報処理， Vol. 44, No. 5, pp.
515–521 (2003).
笹田耕一，松本行弘，前田敦司，並木美太郎：Ruby 用仮想マシン YARV の実装と評価，情報処理学会論文誌 (PRO)，
Vol. 47, No. SIG 2(PRO28), pp. 57–73 (2006).

7図2. RGenGC: Micro-benchmark

25

3000

20

2500

15

2000

Time (ms)Time (ms)

図1. RGenGC: Micro-benchmark

10
5
0

1000

1
6
11
16
21
26
31
36
41
46
51
56
61
66
71
76
81
86
91
96
101
106
111
116
121
126
131
136
sweep time/nomark time/RGenGC

87.230735
RGenGCnototal marktotal sweep

図4. RGenGC: Rdoc application

200

9000

180

8000

160

7000

140

6000

Time (ms)

120
100
80

5000
4000
3000

60

2000

40

1000

20

0

1
5
9
13
17
21
25
29
33
37
41
45
49
53
57
61
65
69
73
77
81
85
89
93
97
101
105
109
113
117
121
125
129
133
137
141
145

0
nth-GC
mark time/nosweep time/nomark time/RGenGC

total mark8210.724461
1049.27184

no
RGenGC

total sweep
3524.425873
3579.584833

sweep time/RGenGC

図5. RGenGC: Rdoc applicationno

RGenGC図6. RGenGC: Rdoc application

1200003,000,000

1000002,500,000

80000
2,000,000
60000
1,500,000

40000

1,000,000

20000
0total sweep
total markothers

no3524.425873
8210.724461
100907.4225
othersRGenGC3579.584833
1049.27184
100640.8472
total marktotal sweep

500,000
0

1
5
9
13
17
21
25
29
33
37
41
45
49
53
57
61
65
69
73
77
81
85
89
93
97
101
105
109
113
117
121
125
129
133
137
141
145

Time (ms)867.740319

0

sweep time/RGenGC

図3. RGenGC: Rdoc application

Time (ms)1699.805974

500

n-th GC
mark time/no704.843669

1500

available slots

live slots

old objects

unprotected objects

remembered unprotected objects

図7. RGenGC: Rdoc application

図8. RincGC: Micro-benchmark

70,000Top 2048 of pause time
0.035

60,0000.03

50,0000.025

Time (sec)

40,00030,0000.02
0.015

20,0000.01

10,000

0.005

1
5
9
13
17
21
25
29
33
37
41
45
49
53
57
61
65
69
73
77
81
85
89
93
97
101
105
109
113
117
121
125
129
133
137
141
145
unprotected objects

remembered unprotected objects

図9. RincGC: Rdoc application
Pause time top 256
0.25

0.1

0.05
0

1
7
13
19
25
31
37
43
49
55
61
67
73
79
85
91
97
103
109
115
121
127
133
139
145
151
157
163
169
175
181
187
193
199
205
211
217
223
229
235
241
247
253

Time (sec)

0.2
0.15

pause time (rgengc+lazy sweep)

pause time (rgengc+rincgc)

1
49
97
145
193
241
289
337
385
433
481
529
577
625
673
721
769
817
865
913
961
1009
1057
1105
1153
1201
1249
1297
1345
1393
1441
1489
1537
1585
1633
1681
1729
1777
1825
1873
1921
1969
2017

0

0

pause time (lazy sweep)

pause time (rincgc)