粗粒度インクリメンタルGC

前田, 敦司, 遠藤, 匠, 山口, 喜教

マークスイープアルゴリズムに基づくインクリメンタルガーベジコレクタは，停止時間をごく短時間に抑えることが可能であるが，効率が悪く，CPU時間が増加する．この性能低下の原因は，一括型GCと比較してマークする時期が早いことに起因するmark/cons比の悪化，GCルーチンを呼び出す回数の増加，write barrierのオーバヘッドなどによる．一方，世代別ガーベジコレクタは高いCPU効率が得られ，また平均の停止時間は比較的短いため良いレスポンスが得られるが，旧世代領域のGC（メジャーコレクション）の際には長い時間にわたって計算処理が停止してしまい，リアルタイム応用には適さない．本発表では，世代別GCがある意味でインクリメンタルGCの一種と見なせることを指摘する．この観察に基づき，新世代領域のGC（マイナーコレクション）のたびに，インクリメンタルに旧世代領域のガーベジコレクションを行う新しいGCアルゴリズムを提案する．インクリメンタル化のために必要となるライトバリアは，世代別ガーベジコレクタの実装にいずれにせよ必要なライトバリアと同じ仕組みを利用する．このアルゴリズムは，通常の世代別ガーベジコレクタに近い効率を保ちながら，停止時間を短く保ち，ガーベジコレクタのリアルタイム性を向上させることができる．

Incremental garbage collectors based on mark-sweep algorithms can minimize the pause time caused by garbage collection at the expense of increased CPU time. The main reasons for this performance degradation include: (1) mark/cons ratio gets worse in incremental collectors because objects are marked earlier than in non-incremental counterparts, (2) increase in number of calls to collector routine and (3) write barrier overhead. Generational collectors, on the other hand, can achieve high efficiency and relatively short average pause time, while occasional long pause for collection of old generation space (major collection) makes these collectors unsuitable for real-time applications. In this presentation we point out that certain class of generational collectors can be viewed as a special case of incremental garbage collection. Based on this observation, we propose a new GC algorithm which incrementally reclaims old generation space every time a minor collection is performed. Write barrier for generational collector is also used for incremental collection. With this algorithm, we can improve real-time response of garbage collector by keeping pause time short, with little overhead added to ordinary generational collectors.

粗粒度インクリメンタルGC

書誌事項

この論文をさがす

抄録

収録刊行物

キーワード

詳細情報詳細情報について

書き出し

問題の指摘

粗粒度インクリメンタルGC

書誌事項

この論文をさがす

抄録

収録刊行物

キーワード

詳細情報 詳細情報について

書き出し

問題の指摘

参加プロジェクトリスト

詳細情報詳細情報について