Incremental,Generational, Mostly-Copying Garbage Collection in

Incremental,Generational,
Mostly-Copying Garbage Collection
in Uncooperative Environments
by G.May Yip, A Master Thesis, MIT, 1991
について。
発表者: 小林義徳
http://www.research.compaq.com/wrl/techreports/abstracts/91.8.html
About this GC…

Incremental, generational
mostly-copying garbage collector for C++

Uniprocessor
特別な hardware サポートなしで動作。
コンパイラへの変更も不要
UNIXの mprotect システムコールを使用



The collector achieves…
GC 一回あたりの停止時間が短い
(from incremental collection)
 トータルのGC 時間もそれほど長くない
(from generational collection)
 ハードウェアやコンパイラのサポートなしで
動作
(from mostly-copying collection)

内容
Generational GC
 Program Interface in C++
 Bartlett’s Generational MostlyCopying Collector
 Incremental,Generational
Mostly-Copying Collection
詳細
実験結果
今後の課題

Generational GC

経験則:
ほとんどのオブジェクトは生成後すぐにゴミになり、
ある程度の期間以上生き残ったオブジェクトはさらに長期に
わたって生き残る

一定回数以上の GC で生き残ったオブジェクトを古いオブジェ
クトとみなす。
GC の際、古いオブジェクトは、最初から生きているとして扱う。
結果として、GC の仕事を減らすことができる


Generational GC(図)
Old space
Remembered set
New space
stack,registers,static area
Generational GC


Root set は、スタック、レジスタ、スタティック領域の変数の
ほかに、 remembered set も用いる
remembered set
= 新しいオブジェクトを指す古いオブジェクト全体を含む集合
(Bartlett’s GC や this GC では,
the remembered set = 古いオブジェクト全体)
Program Interface in C++
struct word{
word *lesser,*greater;
・・・
GCCLASS(word);
クラス word はGC によって回収される
}
word::word(char* chars){
GCALLOCV(word,sizeof(word) + strlen(chars));
・・・
可変サイズのクラスはGCALLOCV で allocate
}
void word::GCPointers(){
オブジェクト内のポインタを扱うため
のgcpointer(lesser);
CALLBACK
gcpointer(greater);
}
Rules



class C:P{} について、
C::GCPointers() 内に P::GCPointers()を書く
class C { X x;} について、
C::GCPointers() 内に x.GCPointers() を書く
class C { X* x;} について、
C::GCPointers() 内に gcpointer(x) を書く
GCCLASS(word) および
gcpointer(x)

マクロ GCCLASS(word)



インライン関数 gcpointer(x)


コールバック word::GCPointers() を宣言している。
new 演算子をオーバーロードし、その中でコールバック
word::GCPointers のGC への登録を行っている。
x = gcmove(x) のように展開される。
GC 時には、word::GCPointers() が呼び出され、
word 内のポインタが指すオブジェクトをコピー。
Bartlett’s Mostly-Copying
Collector[1][2]

Compacting,conservative collector
スタックやレジスタ内の word については、
すべてポインタとして扱う。
 ヒープ内に確保されるオブジェクトの構造に
ついては、知っているものとする。
 コンパイラのサポートが不要

Allocation

2-level allocation
 small objects (１ページよりも小さいオブジェクト)
1. heap page を一つ確保
2. heap page よりオブジェクトを確保
 large objects (一ページよりも大きいオブジェクト)
1. 十分な量のページを確保
ページの最後の余った部分は使われない
Spaces

heap page (512 bytes/page) について
 space identifier : an integer
current-space , next-space (later)
 type identifier : OBJECT or CONTINUED
小さいオブジェクトをもっているページ
: OBJECT
大きいオブジェクト(１ページ以上)
最初のページ
: OBJECT
残りのページ
: CONTINUED
Two Spaces

current-space
新しいオブジェクトは current-space より確保
Copy GC の from-space に対応

next-space
Root pointer に指されたオブジェクトをもつページ
GC により動かされたオブジェクトをもつページ
Copy GC の to-space に対応
Space ID を管理する変数
curr_space : current-space の space ID
next_space : next-space の space ID
 初期設定
curr_space = next_space = 3;
 GC が走っていないとき
curr_space == next_space
 GC の最中
curr_space != next_space
Heap Spaces (Normally)
ID = 3
ID = 3
ID = 3
ID = 3
ID = 3
ID = 3
ID = 3
ID = 3
curr_space = next_space = 3
Allocation
GC が走っていない間
オブジェクトは current-space より確保
(curr_space = next_space)
 GC の最中
オブジェクトをコピーするためのスペースは
next-space より確保

Collection(1)

allocatedpages >= heappages /2
となった時点でGC が起動される。
1.
next_space = curr_space + 1;
Root set を探索
(スタック、レジスタ、static 領域の変数、
remembered set)
‘root pointers’ に「指されている」 currentspace を promote
(promote : spaceID = next_space)
2.
3.
Collection(2)
4.
5.
古いオブジェクトおよび promote された
ページより、オブジェクトを探索・コピー
(幅優先探索)
curr_space = curr_space + 2;
next_space = curr_space;
Heap Spaces (Before GC)
Root set
ID = 3
ID = 3
ID = 3
ID = 3
curr_space = next_space = 3
Heap Spaces (Start GC)
Root set
ID = 4
ID = 4
ID = 3
ID = 3
curr_space = 3 , next_space = 4
(next_space++)
Heap Spaces (During
GC(1))
Root set
ID = 4
ID = 4
ID = 3
ID = 3
curr_space = 3 , next_space = 4
Forwarding pointer
Heap Spaces (During
GC(2))
Root set
ID = 4
ID = 4
ID = 3
ID = 3
curr_space = 3 , next_space = 4
Forwarding pointer
Heap Spaces (During
GC(3))
Root set
ID = 4
ID = 4
ID = 3
ID = 3
curr_space = 3 , next_space = 4
Forwarding pointer
Heap Spaces (After GC)
Root set
ID = 4
ID = 4
ID = 5
ID = 5
curr_space = next_space = 5
(curr_space +=2,next_space++)
Picking Up Generations[2]




一度でも GC を生き残ったオブジェクトを古いオブ
ジェクトとみなす。
GC後、古いオブジェクトを持つページは、偶数の
space identifier をもつ。
GC は、古いオブジェクト全体を remembered set
として扱う。
たまには、古いオブジェクトも回収(major
collection)

minor collection 後、古いオブジェクトがヒープの 85 % を超えてい
たとき、Mark-Compact GC を実行[3]
Incremental,Generational
Mostly-Copying Collector

Incremental Collector




アプリケーションの動作の合間に細切れにGarbage
Collection を行う。GC をすこし行ったら、アプリケーションに
制御を返してしまう。
一度のGC の停止時間は短いが、totalのGC時間は長くなる
ページ保護を用い、Page Faultの際に少しずつ探索と Copy
を行う。(mprotect を用いて、read/write protect)
Generational Collector


通常は、新しいオブジェクトのみを対象に GC を行う。
Total のGC 時間を減らすことができる。
3-space strategy

current-space (変数 curr_space)
新しいオブジェクトは、current-space より確保

previous-space (prev_space)
GC の最中で、未探索のページ

forward-space (forw_space)
Root pointer に指されているページ
オブジェクトのコピー用のメモリは forward-space より確保
Bartlett’s GC の next-space に相当
GC が走っていない間は、これら３つの space の区別はない。
cf.2-spaces in Bartlett’s GC

current-space
新しいオブジェクトは current-space より確保
Copy GC の from-space に対応

next-space
Root pointer に指されたオブジェクトをもつページ
GC により動かされたオブジェクトをもつページ
Copy GC の to-space に対応
GC を開始するタイミング

GC を開始するタイミング


allocatedpages >= heappages /3
GC を再開するタイミング


保護されたページへのアクセスがあったとき
アプリケーションが新しい heap page を確保したとき。
保護されたページをランダムに選び、GC を行う。
Start GC
1.
space-ID を管理する変数を更新
(forw_space,prev_space,curr_space)
2.
3.
Root set を探索
root pointer に指されているpages を promote
(Promote : space-ID = forw_space)
4.
古いオブジェクトをもつページと３. のページを保護
(mprotect
5.
: read/write protect)
アプリケーションに制御を返す
Start GC
curr_space
protected pages
unprotected pages
A
Root set
forw_space = curr_space
B
= prev_space
C
prev_space = curr_space
D
curr_space
forw_space = curr_space + 1;
curr_space
= curr_space + 2;
Protect Pages(1)
forw_space
protected pages
unprotected pages
A
Root set
B
C
D
prev_space
Trap Handler’s Works
(During GC)
1.
2.
3.
4.

Page Fault の起こったページの保護を外す
ページ内のオブジェクトを探索・コピー
２.でコピーされたオブジェクトを含むページを保護
(Protect : neither readable nor writable)
アプリケーションに制御を返す。
アプリケーションが新しい heap page を確保する際、
保護されたページをランダムに選び、scan を行う。
Handle Page Fault(1)
forw_space
B’
C’
A
forw_space
B
C
protected pages
unprotected pages
forwarding pointers
D
prev_space
Handler Protects Pages(2)
forw_space
B’
C’
A
forw_space
B
C
protected pages
unprotected pages
forwarding pointers
D
prev_space
Handle Page Fault(2)
forw_space
B’
C’
A
forw_space
B
C
D’
D
prev_space
forw_space
Handler Protects Pages(3)
forw_space
B’
C’
A
forw_space
B
C
D’
D
prev_space
forw_space
Handle Page Fault(3)
forw_space
B’
C’
A
forw_space
All protected pages
have been
unprotected and
scanned
D’
forw_space
Finish GC

保護されたページがなくなった時点で、GC 終了

Space-ID 変数を更新
prev_space = forw_space = curr_space
(At the start of GC,
prev_space = curr_space
forw_space = curr_space + 1;
curr_space

= curr_space + 2;)
最後まで prev_space だったページはGC 後、
再利用可能になる。
Benchmark Program

words
テキストファイルを読み、その中の単語について、
辞書順のbinary tree を生成するプログラム。

bipsctrl
WRL で作られた CAD system の一部
実験結果

Non-Incremental Generational
V.S. Incremental Generational
別紙の実験結果によると、
Incremental 化による GC 処理時間の増加は、
words
で 24 %,
bipsctrl で
にとどまっている。
7%
Real-Time Performance
使用したベンチマークプログラムについて、
平均の GC の停止時間は、約 4msec ほど
であった。
 最大の停止時間も、せいぜい 100 msec 以
内に収まった

まとめ

Bartlett のGenerational Mostly-Copying
GC が Incremental化された。
previous-space の概念を追加
 mprotect によるページ保護


Performance もそれなりによかった
最大の停止時間も 100msec 以下に抑えられた。
 Total のGC 時間もそれほど大きくならなかった。

Future Works

Non-concurrent collector
concurrent collector

GC の初期化プロセスも incremental 化
GC 初期化処理による停止時間が一番長い
 GC 初期化時間は、root set の大きさに比例。

References
[1] Joel F.Bartlett,1988
Compacting Garbage Collection with Ambiguous Roots
[2] Joel F.Bartlett,1989
Mostly-Copying Garbage Collection Picks Up Generations and
C++
[3] Richard Jones and Rafael Lins,1996
Garbage Collection,Algorithm for Automatic Dynamic Memory
Management
References
[4] 遠藤敏夫,1999
一般教養としての Garbage Collection

Download Report