5/23

全体ミーティング (5/23)
村田雅之
テーマ
• 決定的なコピーガベージコレクション
– Deterministic Parallel Copying Garbage Collection
• シンプルなアルゴリズムを実装し検証する
• まだ正しく動いていなかった
– 追いかけていないポインタがあった
アルゴリズムの概要
1. 一定サイズ以下なら逐次アルゴリズム
2. 大きければ2分割して再帰的に実行
3. 分割した結果をまとめる
– 分割範囲外へのポインタを処理する
見落としていた例
0
1
2
3
4
5
6
7
1
4
4
2
12
7
4
2
・・・
見落としていた例
0
1
2
3
4
5
6
7
1
4
4
2
12
7
4
2
1
?
5
?
0
1
4
5
2
3
・・・
・・・
6
7
見落としていた例
さらに範囲外
へのポインタ
0
1
2
3
4
5
6
7
1
4
4
2
12
7
4
2
1
2
?
5
?
0
1
2
4
5
3
・・・
・・・
6
7
見落としていた例
0
1
2
3
4
5
6
7
1
4
4
2
12
7
4
2
1
2
?
2
5
3
0
1
2
3
4
5
・・・
・・・
6
7
データは前からつめていく方針
見落としていた例
0
1
2
3
4
5
6
7
1
4
4
2
12
7
4
2
1
2
?
2
5
3
0
1
2
3
4
5
終わっていないのに
無視されてしまう
・・・
・・・
6
7
ここから前は終わった
ことにしていた
対策
• まだコピーが終わっていないポインタは記憶
しておいて次の段階でコピーする
– リストを作って管理
もうひとつの問題
• 統合の過程でヒープに間が空いてしまうが
放置していた
• コピーGCとしては空けるのはよくない
– 利点が失われる
間が空くことによる問題
• ヒープの使用効率が悪い
– データ末尾がヒープからあふれてしまうことも
間が空くことによる問題
• ヒープの使用効率が悪い
– データ末尾がヒープからあふれてしまうことも
使われない空間
間を詰めていく
• 毎回データを移動して間を詰めることにする
– 穴だらけになる前に行うのでシンプルに実現可能
移動のパターン(1)
• 前半の空き空間が後半の使用済み空間より
大きい場合
• 後半をそのままコピーして間を詰める
移動のパターン(2)
• 前半の空き空間が後半の使用済み空間より
小さい場合
• 後半の末尾をコピーして空きを埋める
移動に伴う影響
• ポインタの付け替えが必要
– to space内でのポインタ
– forwarding ポインタ
• fromからtoのどこにコピーされたかという情報
ポインタのつけかえ
0
1
2
3
4
5
6
7
1
4
4
1
0
7
4
5
1
2
0
5
4
0
1
2
4
5
6
7
3
ポインタのつけかえ
0
1
2
3
4
5
6
7
1
4
4
1
0
7
4
5
1
2
0
4
5
0
1
2
3
4
5
6
7
ポインタのつけかえ
0
1
2
3
4
5
6
7
1
4
4
1
0
7
4
5
1
2
0
4
3
0
1
2
3
4
5
6
7
実行時間の計測
• Intel Core i7 3.2GHz
– 4コア、HTで論理的には8コア
• 4GB RAM
分割サイズによる実行時間
• 128Mの長さのヒープ
• ランダムなポインタ
1200000
1000000
800000
600000
400000
200000
0
ワーカースレッドの数の変化
• 8分割
• 性能が伸び悩む
9
8
7
6
5
4
3
2
1
0
1
2
3
4
5
6
7
8
偏ったヒープの場合
• 4つの区間内で固まったポインタ
• ランダムより並列化の恩恵が大きい
9
8
7
6
5
4
3
2
1
0
1
2
3
4
5
6
7
8
遅くなっている原因
• 分割の回数が増えるほど遅くなっているのは
ポインタの付け替えの影響か
– ヒープ全体のポインタの値を調べる必要がある
遅くなっている原因
0
1
2
3
4
5
6
7
1
4
4
1
0
7
4
5
すべて調べる
必要がある
1
2
0
4
5
0
1
2
3
4
5
6
7
速くするには(1)
• 付け替え操作自体は並列化すれば早くなる
• もとが並列処理部分なので並列化をしても
コアが足りず全体の性能は上がらない
速くするには(2)
• ポインタの更新の間隔を長くする
– 後でまとめてやっても結果は変わらない(はず)
• コピーしたデータを他のデータで上書きすることはない
– これから試す
高速化のための他の方法
• From空間は分割しなくてもよいことを利用？
– read-only なので競合しない
• Parallel Garbage Collection for Shared
Memory Multiprocessors (Flood et al., 2001)
– 1スレッドに1つのrootを割り当てる
– 各スレッドは自分のバッファを持つ
– 競合はatomicな命令で回避
• compare and swap

Download Report