全体ミーティング (5/23) 村田雅之
テーマ 決定的なコピーガベージコレクション シンプルなアルゴリズムを実装し検証する まだ正しく動いていなかった Deterministic Parallel Copying Garbage Collection シンプルなアルゴリズムを実装し検証する まだ正しく動いていなかった 追いかけていないポインタがあった
アルゴリズムの概要 一定サイズ以下なら逐次アルゴリズム 大きければ2分割して再帰的に実行 分割した結果をまとめる 分割範囲外へのポインタを処理する
見落としていた例 1 2 3 4 5 6 7 1 4 4 2 12 7 4 2 ・・・
見落としていた例 1 2 3 4 5 6 7 1 4 4 2 12 7 4 2 ・・・ 1 ? 5 ? ・・・ 1 2 3 4 5 6 7
見落としていた例 さらに範囲外へのポインタ 1 2 3 4 5 6 7 1 4 4 2 12 7 4 2 ・・・ 1 2 ? 5 ? ・・・ 1 2 3 4 5 6 7
見落としていた例 1 2 3 4 5 6 7 1 4 4 2 12 7 4 2 ・・・ 1 2 ? 2 5 3 ・・・ 1 2 3 4 5 6 7 データは前からつめていく方針
見落としていた例 1 2 3 4 5 6 7 1 4 4 2 12 7 4 2 ・・・ 1 2 ? 2 5 3 ・・・ 1 2 3 4 5 6 7 終わっていないのに無視されてしまう ここから前は終わったことにしていた
対策 まだコピーが終わっていないポインタは記憶しておいて次の段階でコピーする リストを作って管理
もうひとつの問題 統合の過程でヒープに間が空いてしまうが 放置していた コピーGCとしては空けるのはよくない 利点が失われる
間が空くことによる問題 ヒープの使用効率が悪い データ末尾がヒープからあふれてしまうことも
間が空くことによる問題 ヒープの使用効率が悪い データ末尾がヒープからあふれてしまうことも 使われない空間
間を詰めていく 毎回データを移動して間を詰めることにする 穴だらけになる前に行うのでシンプルに実現可能
移動のパターン(1) 前半の空き空間が後半の使用済み空間より大きい場合 後半をそのままコピーして間を詰める
移動のパターン(2) 前半の空き空間が後半の使用済み空間より小さい場合 後半の末尾をコピーして空きを埋める
移動に伴う影響 ポインタの付け替えが必要 to space内でのポインタ forwarding ポインタ fromからtoのどこにコピーされたかという情報
ポインタのつけかえ 1 2 3 4 5 6 7 1 4 4 1 7 4 5 1 2 5 4 1 2 3 4 5 6 7
ポインタのつけかえ 1 2 3 4 5 6 7 1 4 4 1 7 4 5 1 2 4 5 1 2 3 4 5 6 7
ポインタのつけかえ 1 2 3 4 5 6 7 1 4 4 1 7 4 5 1 2 4 3 1 2 3 4 5 6 7
実行時間の計測 Intel Core i7 3.2GHz 4コア、HTで論理的には8コア 4GB RAM
分割サイズによる実行時間 128Mの長さのヒープ ランダムなポインタ
ワーカースレッドの数の変化 8分割 性能が伸び悩む
偏ったヒープの場合 4つの区間内で固まったポインタ ランダムより並列化の恩恵が大きい
遅くなっている原因 分割の回数が増えるほど遅くなっているのはポインタの付け替えの影響か ヒープ全体のポインタの値を調べる必要がある
遅くなっている原因 1 2 3 4 5 6 7 1 4 4 1 7 4 5 すべて調べる 必要がある 1 2 4 5 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