ある日のGC mailing list

速報: Boehm GC
version 6.0α1
遠藤敏夫
ある日のGC mailing list
From: "Boehm, Hans" <[email protected]>
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
影響
Boehm
Endo
SGC 0.x

逐次版(以下、BGC5と呼ぶ)と並列版(BGC6)を平行
maintainance
BGC6追加機能(SGCと同じ)

並列memory allocate


複数ユーザスレッドからのallocate要求に対して(ほと
んどの場合)並列に処理
並列mark phase

複数のGCスレッドが並列にマークを行うことにより、
GC時間を短縮
BGC6設計方針と現状

既存バージョンからの差分を少なく保つ



ターゲットは小規模共有メモリマシン


ソース20000行のうち2000行程度の変更 (無関係な個
所も含む数字なので、実質1000行程度か？)
SGCの変更箇所は数えられないくらい広範囲
あくまで気楽な並列化であり、大規模マシンで性能が
でなくてもよい。ここがSGCとの違い
現状: 今はLinuxのみで稼動
各GC実装の比較
BGC 5
BGC 6
SGC
並列malloc
並列mark
並列sweep
Incremental GC
maintainance
×
×
×
○
-
○
○
×
×
○
○
○
×
速度(小規模)
速度(大規模)
×
×
△
△
×
×
○
○
以下の発表の流れ


BGC5/BGC6/SGCのしくみの違い

Allocate

スレッドモデル

GC
BGC6とSGCの性能比較 → SGCの圧勝
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

Free listを各スレッドローカルに持たせ、ロックを減らす
SGCのallocate
F.l. 探索
R.l. 探索
ここでlock
Heap block free
list探索
GC

Reclaim listもスレッドローカルに →
ソース変更量はより多いが、false sharingが減るはず
BGC5のスレッドモデル
ユーザスレッド
GC要求
時間
(非Incremental設定のときの図)


GC要求を行った(=allocate失敗検出した)スレッドが一人
でGC
GC中は他スレッドを、シグナルなどで停止しておく

マーク途中でメモリを書き換えられるとまずいので
BGC6のスレッドモデル
ユーザスレッド
GCスレッド




時間
GC並列度を前もって指定可能(環境変数 GC_NPROCS)
GC_NPROCS-1個のGCスレッドが裏で稼動
GC要求者 + GCスレッドで並列にGC処理
SGCもほぼ同様
逐次markアルゴリズム(1)
Root R
A
C
B
A
R
Mark stack

B
D
C
E
H
Heap
F
データ構造



G
各オブジェクトごとにマークビット
処理経過を覚えるマークスタック
mark phaseの目的

ルートからたどれる全オブジェクトのマークビットを立
てる
逐次markアルゴリズム(2)
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)
local
mark stack

Global
mark stack
データ構造



local
mark stack
唯一のグローバルマークスタック(GMS)
GCスレッド毎のローカルマークスタック(LMS)
各スレッドは自分のLMSを用いて仕事をする
BGC6の並列mark(2)

初期状態


スレッドがGMSから仕事を盗む条件


自分のLMSが空のとき。最大5つ仕事を盗む
スレッドがGMSに仕事を返す条件



GMSにルートpush / 全LMSは空
自分のLMSに仕事が2K以上あるとき。全部返す
GMSが空、かつ、休んでいるスレッドが1個以上いると
き。LMS内容の上半分を返す
終了条件

GMS, 全LMSが空ならmark phase終了
BGC6の並列mark(3)

詳細事項

マークビットのテスト・更新にcompare&swap命令


busyなスレッドを数えるカウンタ利用



SGCと同じ
ボトルネックになりうるのでSGCでは非採用
仕事を返すときGMSにロックをかける
仕事を盗むときはロックなし


長所: 待ち時間が少ない
短所: 複数スレッドが同じ仕事をして無駄がでるかも
SGCの並列mark(1)
local
mark stack

local
mark stack
データ構造

GCスレッド毎のローカルマークスタック(LMS)のみ
SGCの並列mark(2)

初期状態


LMSのどれかにルートpush
スレッドが仕事を盗む条件

自分のLMSが空のとき。他のどれかのLMSから、底の
仕事1つ盗む


盗む対象にロックが必要。しかし待たされる可能性は低い
終了条件

全LMSが空ならmark phase終了
SGCの並列mark(3)

詳細事項


マークビット扱いについてはBGC6と同じ
ボトルネックを起こさない終了判定アルゴリズム採用

busyカウンタではなく、あるスレッドが全員のLMSをチェック。
巻き戻し対応。

仕事を盗むとき、相手LMSにロックをかける

BGC6のGMSに比べれば、待たされる可能性は少ない
BGC6/SGC性能の比較(いい加減)


speedup
•Enterprise 10000
•アプリはN-Body
•マーク時間のみ計測
•遠藤がSolarisに移植し
たBGC6利用
7
6
SGC16倍
5
BGC6
BGC6-lock
SGC
4
3
2
1
0
0
10
20
# GC threads
30
スレッド数が多い時の性能は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へのア
クセス頻度を予測することは果たして可能か？

Download Report