An Implementation of Mostly-copying GC on Ruby

IPSJ Web Site

Bibliographic Information

Other Title
  • Ruby における Mostly-Copying GC の実装
  • Ruby ニ オケル Mostly-Copying GC ノ ジッソウ

Search this article

Description

本研究では Ruby VM にコピー GC を実装した．従来の Ruby VM は，メモリ管理に保守的マークスイープ GC を用いていた．その理由は，Ruby には多くの C 言語で記述された拡張モジュールがあり，これらの関数が扱う領域のどこに Ruby オブジェクトへのポインタがあるかが精確には分からないためである．我々は，Bartlett のmostly-copying GC を応用しコピー GC を実現した．基本的なアイデアは，ポインタかどうか分からない値の含まれる 「あいまいなルート」 から指されるオブジェクトは移動させず，それ以外のオブジェクトのみを移動させるというものである．しかし Bartlett のアルゴリズムは，あいまいなルートが多くのポインタを含む場合に回収できないごみが多くなる．そのため改善したアルゴリズムを提案する．提案アルゴリズムでは，マークスイープ GC を組み合わせることにより，このような場合もごみを回収できるようにした．これによりヒープのコンパクションが可能になり，生きているオブジェクトの減少に合わせて広がったヒープを縮小できるようになった．本論文では，そのアルゴリズムの詳細を述べ，それを実装した VM の性能評価を行う．

We implemented a copying GC on a Ruby VM. The Ruby VM has been employed a conservative mark-sweep GC. This is because Ruby has many extension libraries written in C and we cannot find pointers to Ruby objects accurately in memory used by them. We implemented a copying GC on the Ruby VM using the idea of mostly-copying GC of Bartlett. The basic idea is that the collector pins the objects pointed by the "ambiguous root", where we cannot find pointers accurately, and moves only the others. However, Bartlett's algorithm retains many garbages when ambiguous root has many pointers. Thus we propose a variant of the algorithm. The algorithm collects garbages by using the technique of mark-sweep GC under such an environment. The algorithm allows us to compact the heap. As a result, we can shrink the heap when the number of live objects is decreased. In this script, we show the details of the algorithm and evaluate the performance of the VM with the algorithm.

Journal

Related Projects

See more

Keywords

Details 詳細情報について

Report a problem

Back to top