高速で実時間性を持つGCの設計と実装

高速で実時間性を持つGCの設計と
実装
2004.10.5
電子情報工学科4年
近山・田浦研究室
30384 白井達也
1
発表の流れ







背景
本研究の目的
基本的なGCアルゴリズム
関連研究
本研究のGC
モデルによる性能予測
現状と今後の予定
2
背景
 メモリ管理の明示は煩雑
メモリの自動管理の必要性
 Garbage Collection（GC)
 メモリの解放を自動的に行う
 プログラマは解放のタイミングを明示する必要が
無くなり、負担が軽減する
 GCのコスト
 効率
 停止時間
⇒総実行時間
⇒対話プログラムの反応時間
3
本研究の目的
 効率と停止時間
 まとめて処理すると、効率はよいが、停止時間が長い
 処理を分けると、停止時間は短いが、効率は悪い
効率と停止時間はトレードオフの関係
 本研究の目的
一度に停止する最大時間を抑えた上で
効率の高いGCを設計、実装する
4
Reference Count GC (RC)

手法



長所



オブジェクトから参照されている数（参照数）を数える
ポインタが更新されたら参照数も更新し、0になったら解放する
停止時間が短い
効率がオブジェクトの
生存率によらない
local or global variables
root
root
短所


ポインタ更新ごとの
処理が大きい
循環参照を解放できない
1 A
2 D
1 B
1 C
2 E
0 F
5
Mark-Sweep GC (MS)

手法



長所


rootからたどれたオブジェクトをmarkする
ヒープをsweepしてmarkされていないオブジェクトを解放
循環参照のごみを
解放できる
local or global variables
root
root
短所


停止時間が長い
オブジェクト生存率が
高いと効率が悪くなる
T A
T D
F B
F C
T E
F F
6
Incremental Mark-Sweep GC (IMS)

手法



長所


ヒープ使用率が(k-1)/kを超えたらmarkフェーズに入る
ユーザプログラムがメモリをallocateするたびに、k個のオブジェ
クトだけmarkを行う
停止時間が短い
短所


Heap
使用量
(k-1)/k
生存率が高いと
効率が悪くなる
ポインタ更新ごとの処理
など、MSより効率が悪い
markした量
allocate clock
1サイクル
IMS開始
IMS終了
7
関連研究
 RCとIMSのハイブリッドGC [J. DeTreville 1990]
 循環参照のごみを解放することを目的としたGC
 効率は考慮されていない
 Ulterior Reference Counting [S. M. Blackburn et al. 2003]
 停止時間を抑え、効率の向上を目指したGC
 Generational GCで、若い世代はCopying GCを、古い世代
はRCを用いている。循環参照のごみの解放にはBaconらに
よるCycle detectionを用いる
 プログラムによっては停止時間が長くなる
8
本研究の貢献
 以下の要件を満たすGCを提案する
１．循環参照のごみも解放する
２．停止時間が短い
３．生存率の上昇による、効率の低下を抑
える
 その上で、できるだけ効率を向上させること
を考える
9
基本方針
 RCとIMSを用いる
 停止時間が短い
 生存率が高くても、効率の低下が少ない
 循環参照構造を解放する
 IMSの調整
 1 allocateごとのIMSの mark量を調整し、サイ
クル数を減らすことで、効率を向上させる
10
RCとIMSの調整(1)
ヒープが足りなくなる前に、しかし、できるだけ遅くにIMSのmarkが終わるように設定する
1．RCによる解放は 1 allocateにつき 1 objectまで
2．IMSのmark は 1 allocateにつき k objectずつ(kは停止時間の設定による)
3．IMSはヒープ使用率が(k-1)/kになったらmark を開始する
4．RCの解放中はIMSのmarkを行わない
RCによる解放中
使用量
heap size
heap×(k-1)/k
IMS終了時の
使用量
mark後にごみ
なったオブジェクト
生存量
markした量
allocate clock
IMS開始
1サイクル
IMS終了
11
RCとIMSの調整(2)
R
markフェーズ中の
「ヒープの空き領域 R」と
「未markオブジェクトの最大量T」
の関係は常に
T
k T R
ヒープが足りなくなる前に
IMSのmarkが終わる
12
モデルを用いた性能予測
仮定


生存率とサイクル終了時の
使用率が一定
1
本研究のGCがIMSよりも効
率がよくなる条件
0.8
(1  1 k )r  s
ra 
(1  1 k )r  m
ra
r
m
s
k
：サイクル終了時のヒープ使用率
：RCによる1オブジェクトの解放コスト
：1オブジェクトのmarkコスト
：1オブジェクトのsweepコスト
：1allocateあたりのmark量
(r,m,sは実装によって決まる)
使用率が高いときは
本研究のGCのほうが有利 !!
使用率 ra

0.6
0.4
0.2
0
3
4
5
6
7
8
一度のmark量 k
9
10
本研究のGCが有利になる使用率の条件
(r=2,m=1,s=0.2)
13
実装
 Jikes RVMを用いる
 オープンソースのJava VM
 メモリ管理はモジュール(JMTk [S. M. Blackburn et al. 2003])に
分かれている
 すでに実装されているGC




Mark-Sweep GC
Copying GC
Reference Count GC
Generational GC (hybrid)
 本研究ではRCを元に実装する
14
現状と今後の予定

現状


GCの設計が決まった
今後の予定

GCモデルの改良
IMSを調整しないGCモデルを作り、IMSを調整することによる性能向
上の予測を立てる

実装
Jikes RVMに本研究のGCを実装する

評価
生存率の異なるプログラムを用いて、停止時間を確認し、総実行時間
を測定する

ヒープ使用率の低い時の対応
ヒープ使用率が低い時はRCの処理を止めることで、IMSと同じ性能に
できる
15

Download Report