Comparing Mark-and-Sweep and Stop-and-Copy

Comparing Mark-and-Sweep and
Stop-and-Copy Garbage
Collection について
2002/04/18
米澤研究室修士２年
小林義徳
結論
• Trace-driven simulation により、Mark-andSweep と Stop-and-Copy を比較
– CPU overhead は、Mark-and-Sweep の方が 36%大
– メモリ要求は、Mark-and-Sweep の方が 20 % 以
上少なかった
• Copy GC は、一般に言われているほど、
Mark-Sweep に対し、advantage は大きくない
性能評価の指標
• CPU Costs
– Allocation,sweep など、各部分にかかる時間
の見積もり
• Memory Costs
– Page fault rate をある値以下にするのに必要
なメモリ量
以下の発表の概要
• Stop-and-Copy と Mark-and-Sweep
– 共通部分
– 異なる部分
• 比較した方法について
– Trace-driven simulation
• 実験結果について
両方の GC の共通部分
• Generational GC
– オブジェクトの殿堂入りの仕方は異なる
• Allocation Threshold
– GC の起動のタイミングを規定
– 両方のGC が同じ回数だけ呼ばれる
Generational GC
• 4 世代のGenerational GC
• 各世代は、必要に応じて成長可
• Write Barrier はソフトウェアで実装
– Non-initializing pointer store の前にコードを挿
入
• Remembered set は、old -> new のポインタ
の場所を記憶する two-level bitmap
Allocation Threshold
• Allocation の量が、ある一定の量
(Allocation Threshold) を越えた時点でGC
起動
• Allocation Threshold は、パフォーマンスに
強く影響
– Allocation Threshold が小さい場合、GC が頻
繁に起こる
– 本論文では、Allocation Threshold をいろいろ
変えて実験
Frequent Collection
• GC の間隔が短い
• Object promotion rate が増える
• オブジェクトがより早くリサイクルされるので、
空間的局所性が良くなる。
両方のGC で、異なる部分
• ヒープ構造、Allocation の仕方
• Generational GC の、Promotion Policy
Stop-and-Copy Collection
• ヒープ構造
– 各 Generation とも、FromSpace と ToSpace
– Object は、種類によらず FromSpace より
Allocate
• Promotion policy
– 各オブジェクトが Copy-Count を持っていて、
Copy-Count が 3→ 4 になるときに古い世代に
Copy (promotion)
Mark-and-Sweep GC(1)
• ヒープ構造
1. Mark-bitmap
2. Fixed Objects area
3. Relocatable Objects area
• Vector のヘッダーは 2. に置かれ、
本体は 3.に置かれる。
–
Vector への参照はすべて間接参照
Mark-and-Sweep GC(2)
• en-masse promotion
– 4 回 GC が起こった後、Generation 全体を
promote
– 結果として、promotion rate は、Stop-and-Copy
の場合の約２倍になっている。
GC コストの比較の方法
• MARS
(Memory Allocation and Reference Simulator,
Benjamin Zorn 作)
+ Commercial Lisp System
(Franz Allegro Common Lisp)
いくつかの Lisp プログラムを実行
MARS による simulation
• Lisp
Event
• Event
– Object の参照
– Object の Allocation
– Object Deallocation
MARS
Shadow Memory
• MARS は、独自に “shadow memory” を管理
• MARS は、Heap 中にどうオブジェクトが配置
されているかを知っている。
MARS の提供する情報
•
•
•
•
•
実行時間
参照の局所性
Allocation rates
寿命分布
各 GC での停止時間
CPU Costs の測定(1)
• CPU Cost = 実行時間
• MARS は、instruction counter を持っていない
• GC のコストについては、重要な操作の回数
を数え、必要なCPU サイクル数を掛け算
– objects copied, objects marked, etc
– CPU サイクル数は、Sparc のものを使用
CPU Costs の測定(2)
• 全体の実行時間については、Heap 参照に
かかった CPU instruction を約 8 倍して見
積もる
– さまざまな研究によると、多くのプログラムで、
heap instruction の占める割合は約 12 %
– 正確ではないが、二つのアルゴリズムの相対
的な比較には十分
Memory Costs の測定
• Memory Cost = ある Page Fault 率 [faults/sec]
を達成するために必要な物理メモリ量
• Page Fault 率は、Heap 参照の sequence より
求めることができる。
– Data Reference のみ。Instruction reference につい
ては無視
• ページサイズ = 4096 bytes
• Page replacement policy = LRU
実験結果について
• 実験について
• CPU Cost について
• Memory Cost について
実験
• MARS + LISP で、プログラムを実行
– 商用 Lisp Compiler (ACLC)
– ある種の信号処理Architecture のための
Microcode Compiler(RL)
– 他２つ(Curare, BMTP)
• CPU Cost と Memory Cost を測定
CPU Cost について
• Allocation Threshold 依存のもの
– Mark
– Write Barrier
– Copying
• Allocation Threshold 非依存のもの
– Allocate
– Sweep
– Indirect (vector の間接参照)
Threshold Dependent Costs
• Mark,Copy
– Threshold が大きいと、GC 発生時、より多くの
object がゴミになっているので、コストが小さい
• Barrier
– Threshold が小さいと、object の promotion がよ
り遅くなり、コストが小さくてすむ
Mark-Sweep v.s. Stop-Copy(1)
• Threshold に依存しない costs
– Copy GC
• Allocation +4%
– Mark-Sweep GC
• Allocation +8%
• Sweep
+5%
• Vectors +2-3%
• Threshold 非依存なコストについては、
Mark-Sweep の方が大きい
Mark-Sweep v.s. Stop-Copy(2)
• Threshold に依存する Cost
– Copy GC の方がMark-and-Sweep より大きい
– Threshold が大きい場合でもそれなりの割合を
占める。
CPU Cost についての結論
• Copy GC は、一般に言われているほど、
Mark-Sweep に対し、advantage はない
• Threshold のサイズによっては、MarkSweepより悪くなる。
Memory Cost について
• Memory Cost = あるPage Fault 率[faults/sec]
を出すのに必要なメモリ量
• 全体的に、Mark-Sweep の方が、20-40% ほ
ど少ない。
Memory Costs の傾向
• 一般に、Threshold が大きいほど、多くの
•
メモリを要求する
Generational な場合、逆の効果もある
1. Threshold が小さい場合、Promotion 率が高
くなる。
2. Promotion によって、空間的な局所性が悪く
なる
3. より多くのメモリを要求する
Memory Costs の傾向
• さらに、Mark-Sweep の en-masse
promotion policy では、CopyGC の場合の
２倍promotion 率が高い
• Threshold Size が小さい場合、Mark-Sweep
がより多くのメモリを要求してしまう。
Memory Costs の傾向
• Allocation Threshold をある程度大きくした
場合(500 kB ～)
– Promotion rate が小さくなり、newspace への参
照がメモリ使用量を dominate する。
– Mark-and-Sweep は、Heap を二つの semispace
に分けないため、Memory Cost が小さい。
結論
• Trace-driven simulation により、Mark-andSweep と Stop-and-Copy を比較
– CPU overhead は、Mark-and-Sweep の方が
3-6 % 大
– メモリ要求は、Mark-and-Sweep の方が 20 %
以上少なかった
• Copy GC は、一般に言われているほど、
Mark-Sweep に対し、advantage はない

Download Report