速報: Boehm GC version 6.0α1 遠藤 敏夫

ある日のGC mailing list Boehm自らがGCの並列化を始めた From: "Boehm, Hans" <hans_boehm@hp.com> Date: Thu, 15 Jun 2000 15:54:29 -0700 Subject: [gclist] New garbage collector versions ….. Both concurrent marking and concurrent allocation/sweeping is supported. I believe the algorithm is similar in spirit to the work by Endo, Taura, Yonezawa et al at the University of Tokyo. Boehm自らがGCの並列化を始めた

Boehm GCって何 BoehmらによるfreeなGCライブラリ Solaris, Linux, IRIX, Windows... Gc.aをリンクすると、C/C++プログラムから利用可能 GC_malloc()関数でメモリ確保 → 後でいらなくなったら勝手に解放

Boehm GC の系譜 Boehm GC 4.10 Boehm GC 5.1 並列化 並列化 Boehm GC 6.0 影響 Endo SGC 0.x 逐次版(以下、BGC5と呼ぶ)と並列版(BGC6)を平行maintainance

BGC6追加機能(SGCと同じ) 並列memory allocate 並列mark phase 複数のGCスレッドが並列にマークを行うことにより、GC時間を短縮

BGC6設計方針と現状 既存バージョンからの差分を少なく保つ ターゲットは小規模共有メモリマシン 現状: 今はLinuxのみで稼動 ソース20000行のうち2000行程度の変更 (無関係な個所も含む数字なので、実質1000行程度か？) SGCの変更箇所は数えられないくらい広範囲 ターゲットは小規模共有メモリマシン あくまで気楽な並列化であり、大規模マシンで性能がでなくてもよい。ここがSGCとの違い 現状: 今はLinuxのみで稼動

各GC実装の比較 BGC 5 BGC 6 SGC 並列malloc × ○ ○ 並列mark × ○ ○ 並列sweep × × ○ Incremental GC ○ × × maintainance - △ × 速度(小規模) × △ ○ 速度(大規模) × × ○

以下の発表の流れ BGC5/BGC6/SGCのしくみの違い BGC6とSGCの性能比較 → SGCの圧勝 Allocate スレッドモデル

BGC5のallocate Allocate要求 ここでlock Free list 探索 成功終了 Reclaim list探索 成功終了 Heap block free list探索 成功終了 GC

BGC6のallocate F.l. 探索 ここでlock Reclaim list探索 Heap block free list探索 GC

SGCのallocate F.l. 探索 R.l. 探索 ここでlock Heap block free list探索 GC Reclaim listもスレッドローカルに → ソース変更量はより多いが、false sharingが減るはず

BGC5のスレッドモデル GC要求 GC要求を行った(=allocate失敗検出した)スレッドが一人でGC ユーザスレッド GC要求 時間 (非Incremental設定のときの図) GC要求を行った(=allocate失敗検出した)スレッドが一人でGC GC中は他スレッドを、シグナルなどで停止しておく マーク途中でメモリを書き換えられるとまずいので

BGC6のスレッドモデル GC並列度を前もって指定可能(環境変数 GC_NPROCS) GC_NPROCS-1個のGCスレッドが裏で稼動 ユーザスレッド GCスレッド 時間 GC並列度を前もって指定可能(環境変数 GC_NPROCS) GC_NPROCS-1個のGCスレッドが裏で稼動 GC要求者 + GCスレッドで並列にGC処理 SGCもほぼ同様

逐次markアルゴリズム(1) データ構造 mark phaseの目的 各オブジェクトごとにマークビット 処理経過を覚えるマークスタック G H D E Mark stack Root R A B C F Heap R B C A データ構造 各オブジェクトごとにマークビット 処理経過を覚えるマークスタック mark phaseの目的 ルートからたどれる全オブジェクトのマークビットを立てる

逐次markアルゴリズム(2) オブジェクトグラフ中に枝別れが多ければ、マークスタックに積まれる仕事量は多くなる → mark処理の並列性 Rootをマークスタックにpush while (マークスタックが空でない) マークスタックからエントリを一つpop → o for (i = 0; i < (oのサイズ); o++) if (o[i]がポインタ && マークビットが0) o[i]のマークビット = 1 o[i]をマークスタックにpush オブジェクトグラフ中に枝別れが多ければ、マークスタックに積まれる仕事量は多くなる → mark処理の並列性 マークスタックを各GCスレッドに持たせるのが自然な並列化

BGC6の並列mark(1) データ構造 各スレッドは自分のLMSを用いて仕事をする 唯一のグローバルマークスタック(GMS) local mark stack local mark stack Global mark stack データ構造 唯一のグローバルマークスタック(GMS) GCスレッド毎のローカルマークスタック(LMS) 各スレッドは自分のLMSを用いて仕事をする

BGC6の並列mark(2) 初期状態 スレッドがGMSから仕事を盗む条件 スレッドがGMSに仕事を返す条件 終了条件 GMSにルートpush / 全LMSは空 スレッドがGMSから仕事を盗む条件 自分のLMSが空のとき。最大5つ仕事を盗む スレッドがGMSに仕事を返す条件 自分のLMSに仕事が2K以上あるとき。全部返す GMSが空、かつ、休んでいるスレッドが1個以上いるとき。LMS内容の上半分を返す 終了条件 GMS, 全LMSが空ならmark phase終了

BGC6の並列mark(3) 詳細事項 マークビットのテスト・更新にcompare&swap命令 busyなスレッドを数えるカウンタ利用 SGCと同じ busyなスレッドを数えるカウンタ利用 ボトルネックになりうるのでSGCでは非採用 仕事を返すときGMSにロックをかける 仕事を盗むときはロックなし 長所: 待ち時間が少ない 短所: 複数スレッドが同じ仕事をして無駄がでるかも

SGCの並列mark(1) データ構造 GCスレッド毎のローカルマークスタック(LMS)のみ local mark stack local

SGCの並列mark(2) 初期状態 スレッドが仕事を盗む条件 終了条件 LMSのどれかにルートpush 自分のLMSが空のとき。他のどれかのLMSから、底の仕事1つ盗む 盗む対象にロックが必要。しかし待たされる可能性は低い 終了条件 全LMSが空ならmark phase終了

SGCの並列mark(3) 詳細事項 マークビット扱いについてはBGC6と同じ ボトルネックを起こさない終了判定アルゴリズム採用 busyカウンタではなく、あるスレッドが全員のLMSをチェック。巻き戻し対応。 仕事を盗むとき、相手LMSにロックをかける BGC6のGMSに比べれば、待たされる可能性は少ない

BGC6/SGC性能の比較(いい加減) スレッド数が多い時の性能はSGCに遠く及ばず、頭打ち Enterprise 10000 アプリはN-Body マーク時間のみ計測 遠藤がSolarisに移植したBGC6利用 SGC16倍 スレッド数が多い時の性能はSGCに遠く及ばず、頭打ち (BGC6のメインターゲットである、)スレッドが8以下のときでもSGCの勝ち

まとめ Boehm GC Ver.6 は並列allocate/mark対応 SGCよりかなり遅く、まだ技術的には未成熟 Global mark stack廃止だけでも、かなりの効果が得られるのでは？ それよりも、世の中がGCのscalabilityに注目しだした事実が重要 SGCは3年前からやっていた！ Boehm’s page: http://www.hpl.hp.com/personal/Hans_Boehm/gc/

性能予測モデルとの関連 性能予測モデルで、BGC6とSGCの違いを捉えられるか？ → 今はできない。 現在捉えることのできる要因は メモリコンテンションによる待ち時間 オブジェクトグラフのクリティカルパスによる不均衡 ロックなどの要因を捉える必要 オブジェクトグラフと仕事移動戦略から、GMSへのアクセス頻度を予測することは果たして可能か？