高いヒープ使用率の下で高速なインクリメンタルGCの設計と実装 2005.2.16 電子情報工学科4年近山・田浦研究室 30384 白井達也 1 背景  メモリ管理の明示は煩雑 Garbage Collection（GC)  メモリの解放を自動的に行う  GCのコスト  スループット ⇒ 総実行時間  停止時間 ⇒ 対話プログラムの反応時間 2 本研究の目的  停止時間が短い  スループットが安定している  ヒープ使用率の増加に伴うスループットの低下を抑える 3 今後の流れ       基本的なGCアルゴリズム本研究の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)  MSの停止時間を短くする  手法  ユーザプログラムがメモリをallocateするたびに、少しずつmarkを行う 7 markの調整(1)  オブジェクトのallocateに対してmarkを進める  allocate : mark = 1 : k  ヒープがなくなる前にmarkを終わらせる  メモリ占有率がしきい値(k-1)/k を超えたらmarkを開始する 8 markの調整(2) メモリ占有率 Heap (k-1)/k 使用率 IMS開始 IMS終了 allocate clock 1サイクル 9 Incremental Mark-Sweep GC (IMS)  長所  停止時間が短い  短所  使用率が高いと効率が悪くなる  ポインタ更新ごとの処理など、MSより効率が悪い 10 本研究の貢献  以下の要件を満たすGCを提案し、実装した１．循環参照のごみも解放する２．停止時間が短い３．ヒープ使用率の上昇に伴う効率の低下を抑える  コストモデルを設計し、従来の手法よりスループットが向上することを求めた 11 基本方針  RCとIMSを併用する  参照回数を維持し、0になったら解放する  メモリ占有率がしきい値を超えたらmarkを始め、 mark終了後にsweepを行う  Mark量の動的な制御  Mark中にRCによる解放が起こるため、markを行うタイミングを動的に制御して無駄なサイクルを無くし、効率を向上させる 12 Mark量を静的に設定した場合 RCによる解放 Heap (k-1)/k 使用率 Mark量は一定 allocate clock Mark開始 1サイクル 13 Mark量を動的に制御した場合 Heap (k-1)/k 使用率 1サイクル空き容量とmark量をもとに次の停止のmark量を制御する allocate clock 14 Mark量の動的な制御  ヒープが足りなくなる前にmarkを終わらせる  mark, sweepのサイクル数を減らす  RCによってヒープに十分余裕ができたときはmarkを行わない 1．IMSはヒープ使用率が(k-1)/kになったらmarkを開始する 2. ヒープの空き容量と未mark量の比が k を上回ったらmarkを行う ※ k はallocate量とmark量の比 15 コストモデル(1)  仕事量の見積もり  コストの種類 = mark、 sweep、 RC  総コスト = 1サイクルのコスト × サイクル数  パラメータ  循環参照の割合 (c)  allocate量とmark量の比 (k)  1オブジェクトのmarkコスト (m) sweepコスト (s) RCのコスト (r)  使用率(e) 16 コストモデル(2) m:s:r=3:1:9 循環参照=0.3 k=4 コスト IMS mark量の調整なし mark量の調整あり使用率が高くてもコストの増加が抑えられている 0 0.2 0.4 使用率 0.6 0.8 17 実装  Jikes RVMのメモリ管理モジュール(JMTk) に実装  JMTk : 50000行程度  GC制御用に書き換えた部分が6000行程度  MS, RC などが既に実装されている  実装したGC  Incremental mark sweep GC  停止時間の短いRC  Mark量を動的に制御したハイブリッドGC 18 実装上の問題  一方のGCバッファ内のオブジェクトを他方のGCが解放してしまう IMS RC 解放オブジェクト解放済みバッファに記録したときのオブジェクトではない 19 IMSによるRCバッファへの影響  現象  RCバッファ内のオブジェクトをsweepで解放  解決手法  Sweepの前にRCの処理を行い、RCバッファのオブジェクトを無くす 20 RCによるIMSバッファへの影響  現象  IMSバッファ内のオブジェクトの参照回数が0になって解放  解決手法  Markしたオブジェクトは解放しない ※ Markされた後、そのサイクル中に参照回数が0になったオブジェクトは次のサイクルで解放される 21 評価  環境     baseコンパイル (adaptiveコンパイルより2～3倍遅い) プログラム    : Intel Xeon 3.2GHz : ２GB : Debian Linux VMのコンパイル   CPU メモリ OS SPECjvm98 の _228_jack(使用メモリ9MB、循環参照5%未満) SPECjvm98 の _213_javac(使用メモリ30MB、循環参照30%) 評価   停止時間実行時間(いろいろなヒープサイズで実行) 22 停止時間  _228_jack (ヒープサイズ30MB) GC 平均停止時間最大停止時間 [ms] [ms] 停止回数 MS 597 608 12 RC 1096 1263 11 IMS 17 30 1127 IRC 25 51 1655 Hybrid GC 25 53 1655 23 停止時間  _213_javac (ヒープサイズ60MB, RCのみ80MB) GC 平均停止時間最大停止時間 [ms] [ms] 停止回数 MS 1089 1102 4 RC 1603 1877 6 IMS 17 32 2568 IRC 31 63 1499 Hybrid GC 32 117 1641 24 _228_jack の実行時間(循環参照5%未満) 実行時間の増加が 120 抑えられている実行時間[sec] Hybrid GC IRC IMS RC MS 実行時間が増加している 80 40 0 5 10 15 20 25 30 35 メモリサイズ[MB] 25 _213_javacの実行時間(循環参照30%) 実行時間の増加が抑えられている実行時間[sec] 160 Hybrid GC IRC IMS RC MS 120 80 実行時間が増加している 40 0 25 35 45 55 65 75 85 メモリサイズ[MB] 26 まとめ  Mark量を動的に制御するハイブリッドGCを実装し、評価を行った  平均停止時間は30ms程度、最大停止時間がsweep による120msに収まった  メモリが小さい時でもスループットの低下が抑えられた  コストモデルを提案し、使用率が高いときにmark 量を動的に制御するハイブリッドGCが有利になることを確かめた 27 今後の課題  Lazy Sweep  Sweepの停止時間を短くする  ヒープ使用率が低い時の対応  ヒープ使用率が低い時はRCの処理を止めることで、IMS と同じ性能にできる  mark時に参照回数を数える 28