ガベコレ3章
/garbage-collection/ガベコレ3章へと引っ越し！
ガベージコレクション 自動的メモリ管理を構成する理論と実装 Richard Jones, Antony Hosking, Eliot Moss, 前田 敦司 978-4798134208 https://amzn.to/2WDEAz7
の3章まとめ
マークコンパクトGC
intors
非移動型コレクタでは断片化が問題になることがある。
断片化については後の章で述べられる。
同サイズのオブジェクトをまとめて割り当てしたりするなどすれば軽減される。
2章で一瞬話出てきたりしたやつ。
とは言え、結局長期的にはヒープの断片化が起きて実行性能は悪くなっていく。
外部断片化
外部断片化を除去する為に、生きてるオブジェクトを圧縮する方法をこの章、次章で論じる。
圧縮されたヒープの利点は、割り当てが高速にできる。
「ずらす」だけで計算できるらしい。
どこまで割り付けたか + 要求サイズとかで計算できる的な感じ……？
詳しくは7章
この章ではオブジェクトを1つの割り当て領域の中で端にズラして圧縮するものを考える。
次の章ではコピーコレクションを扱う。
生きているオブジェクトを領域を分割された領域(例えば2つに分割)に移動させるもの。
マークコンパクト
数フェーズに分かれて動作する。
最初のフェーズはマーク(前章)。
圧縮フェーズ
以下を行い、圧縮する。
オブジェクトの再配置
移動したオブジェクトの参照を更新
ヒープのパス数、これらの実行順序、再配置方法はアルゴリズムによって異なる。
圧縮の順序は局所性に影響をもたらす。
これどういう意味？
圧縮後の配置の順序が局所性の面で重要 ということでは。
再配置の選択肢
任意
オブジェクトの元の順序や、互いに指しているかなどを考えずに配置。
線形化
関連するオブジェクトを近いところに置く。参照関係があるもの、データ構造において兄弟となるものなど。
スライディング
順序を維持してオブジェクトを端に寄せる。
大抵の場合任意 or スライディングを採用する。
任意順序
実装が簡単で高速。
特に全てのノードが同サイズだと高速。
関連するものが近くにならないので空間局所性が悪くなりがち。
スライディングコンパクション
近代的なマークコンパクトコレクタは全てこれ。
再配置における相対順序が変わることは無いので、それによる局所性の悪化は無い。
コピーコレクタ
うまく配置をコピーの際に決めることにより局所性を上げることさえできうる。
制約
任意順序
単一のサイズ あるいはサイズごとに分けて圧縮
再配置情報をヘッダに格納する必要があることもある。
これは一般にコストが高い。
ヒープ上のパス
ポインタ制約がつく。
参照の向き
内部ポインタ
詳しくは11章
例
ツーフィンガーアルゴリズム
実装は単純で高速。
順序を破壊する。
Lisp 2アルゴリズム
広く使われているスライディングコレクタ
各オブジェクトのヘッダに転送先を格納する領域が必要
スレッデッドコンパクション
空間的オーバーヘッド無し
ヒープ上のパスが2つ必要
高コスト
ワンパスアルゴリズム
空間的オーバーヘッド無し
転送アドレスをオンザフライに計算する。
呼び出し方
全て共通
callCopied!
atomic collect: markFromRoots() compact()3.1 ツーフィンガーアルゴリズム
2パス
任意順序
固定サイズオブジェクトに適す。
生きているオブジェクトの数がわかれば圧縮後領域の最高の位置がわかるという考えを基本とする。
この境界より高い位置にあるものを、境界の下の隙間に挿入する。
下からヒープが伸びていく気持ちで書かれていそう。
code
2-fingerCopied!
compact(): relocate(HeapStart, HeapEnd) // これが終わった後、freeは最高位を指している。 updateReferences(HeapStart, free) reocate(start, end): free <- start scan <- end while free < scan while isMarked(free) unsetMarked(free) free <- free + size(free) // 穴を探す。 while not isMarked(scan) && free < scan scan <- scan - size(scan) // 生きてるオブジェクトを探す。 if free < scan unsetMarked(scan) move(scan, free) *scan <- free // 転送アドレスを破壊的に残す(1)。 // もともとそのオブジェクトがあったところに、引越し先の住所を書いておく。 free <- free + size(free) scan <- scan - size(scan) updateReferences(start, end): for each fld in Roots // ルートとしてて持っているもののうち、引越したものを更新。 ref <- *fld if ref >= end // 最高位より高い位置にあることは引っ越したことを表す。 *fld <- *ref // (1) で書いておいたので、移動先のアドレスがわかる。 scan <- start while scan < end // この領域には生きているオブジェクトがある。それらが持っている他のオブジェクトへの参照を更新する。 for each fld in Pointers(scan) ref <- *fld if ref >= end *fld <- *ref // (1) scan <- scan + size(scan)利点と欠点
各反復の間に単純なことしかしないので、局所性等の問題が起きない(再帰したりしていない)。
メモリのオーバーヘッドは無い。
内部ポインタに対応する。
これどういう意味？
先頭を指していないポインタが
Pointers(scan) にあっても大丈夫 という意味……？ 対応していないのでは……？
メモリアクセスのパターンが予測可能なので、プリフェッチ等のチャンスがあり良い。
relocateの中でheap中のオブジェクトを逆順走査しているので、そういう操作が可能であることが求められる。
マークビットを別の場所のビットマップに格納する or オブジェクト割り当て時に開始点を記録しておく必要がある。
可変サイズの際に下端から開始アドレスがぱっとわからないので、
size(scan) が自明ではないので。 圧縮時にオブジェクトの順序が破壊されるので、局所性の問題が起きる。
関連するオブジェクトは一度に産まれ、一度に死ぬ傾向があるので、連続するオブジェクトのグループを一度に大きな隙間に移すことを試みれば、この問題は多少改善する。
3.2 Lisp 2アルゴリズム
これはそのまま or 並列コレクションに適応させて広く使われている。
可変長サイズのオブジェクトを扱える。
ヒープヘ3パス必要。
各反復での作業量は少ない(スレッデッドコンパクタ等と比較して)。
計算量的にはHohen and Nicolauによる計測では最速。
ただしキャッシュ等を考慮していない。
オブジェクトヘッダに移動先アドレスを書くフィールドが必要になる。
ただしこれはマークにも利用できる。
code
lisp2Copied!
compact(): computeLocations(HeapStart, HeapEnd, HeapStart) updateReferences(HeapStart, HeapEnd) relocate(HeapStart, HeapEnd) compuuteLocations(start, end, toRegion): scan <- start free <- toRegion while scan < end if isMarked(scan) forwardingAddress(scan) <- free // scanの指す先の引っ越し先を保存するフィールドに引っ越し先を書く。 free <- scan + size(scan) scan <- scan + size(scan) updateReferences(start, end): for each fld in Roots // update root ref <- *fld if ref != null // これがnullになるのはいつ？ *fld <- forwardingAddress(ref) scan <- start // update fld while scan < end if isMarked(scan) for each fld in Pointers(scan) if *fld != null *fld <- forwardingAddress(*fld) scan <- scan + size(scan) relocate(start, end): scan <- start while scan < end if isMarked(scan) dst <- forwardingAddress(scan) move(scan, dst) unsetMarked(dst) scan <- scan + size(scan)空いている保証
「一般的に移動先の領域と圧縮される領域は同じである」ってあるけど、それなら
toRegion が空いている保障は無いのでは？ それが「各パスの方向(上向き)はオブジェクトの移動方向(下向き)とは反対であることに留意したい」の言ってることで保障があるのでは。
そういうことを「これは第3パスでオブジェクトをコピーする際、すでに退去済みの位置へコピーされることを保障する」の意味な気がするけどよくわからない。
これよく考えたら、
scan のほうが free より先行することになるので(結局前にズラすことになる)、当然空いている。ズラす向き
P363 図14-8
複数のブロックに分割して並列に実行する際には、ズラす方向を互い違いにすることにより、同じ方向にズラすよりも隙間がおおきくなる。
同じ方向に移動した図
改良
マークスイープGCのスイープフェイズと同様のプリフェッチ
computeLocationsの10行目で隣接するごみの結合
隣接するごみをくっつけて行けば 、27行目とかで2回
size(scan) の大きさを足すことが、一度の結合後の size(scan) で済んでうれしい。 久し振りに10行目を通った時に、最後に通った時のサイズとの差の1つのオブジェクトのようなヘッダを書いておけばよい。
この2つ何。
後者はきもちはわかった。
3.3 スレッデッドコンパクション
Lisp 2アルゴリズムの欠点
ヒープのパスが3つ必要。
オブジェクトのヘッダに転送先を書く領域が必要。
参照の更新中に引越し先アドレスを保持する必要がある。
Lisp 2アルゴリズムでは引越し先を記録することで実現。
ツーフィンガーでは移動先を生きているオブジェクトより高い位置にすることで実現。
しかしこれは順序を破壊する。
スレッド化
追加の記憶領域の必要無いスライディングコンパクション
アドレスを格納するのに十分な領域がヘッダにある必要。
必要なら他の情報を破壊してよい。
ポインタ値が他の値と区別できる必要。
これは困難かもしれない。
スレッド化
オブジェクトNへの参照しているオブジェクトをオブジェクトNから辿れるようにすること。
オブジェクトのポインタの向きを反転するとできる。
一本の糸
P47 図3-2
Nのヘッダが保持していた情報は、辿っていった最後のAに一時的に格納されている。
その代わりに、スレッドの先頭のCのアドレスを保持するために元々のNのヘッダは利用されている。
ここがinfoであるかポインタであるかの区別がつかないといけないことが要件(ポインタと値の区別)に表れている。
code
threadCopied!
compact(): updateForwardReferences() updateBackwardReferences() thread(ref): // スレッド化する。 if *ref != null *ref, **ref <- **ref, ref
update(ref, addr): // スレッド化された参照をaddrで置き換えながらほどく。 // addrが引っ越し先で、そこを指すように直していく？ tmp <- *ref while isReferences(tmp) // 仮定から存在する。 *tmp, tmp <- addr, *tmp *ref <- tmp updateForwardRererences(): for each fld in Roots thread(*fld) // 本当はisReferences(*fld) が必要。 // ここは thread(fld)なのでは……？ free <- HeapStart scan <- HeapStart while scan <= HeapEnd if isMarked(scan) update(scan, free) for each fld in Pointers(scan) thread(fld) free <- free + size(scan) scan <- scan + size(scan)
updateBackwardReferences(): free <- HeapStart scan <- HeapStart while scan <= HeapEnd if isMardked(scan) update(scan, free) // scanの後方参照をfreeに。 move(scan, free) // scanを後方のfreeへスライド free <- free + size(scan) scan <- scan + size(scan)動作
thread の動作がぜんぜんわからん……。pros and cons
オブジェクトヘッダに追加の容量が必要無い。
ただしポインタと通常の値との区別がつく必要がある。
生きているオブジェクトの各ポインタフィールドをスレッド化と更新のために2回更新する。
スレッド化はポインタの追跡を必要とするので、マークと同程度にキャッシュに優しくない。
それなのにこのアルゴリズム(Jonkers)では3回もポインタを辿る。
Martin(1982)はマークフェイズと最初の圧縮パスを結合してパスを2/3にできると言っている。
ポインタを破壊的に変更するので、本質的に逐次的。
並行コンパクションには使えない。
図3-2のbにおいて、Nへの参照がスレッド化された後はBのヘッダがNへの参照を持っていたことを知る術が無いので。
追加のヘッダを用いればもちろん可能だが、それは嬉しさが失われる。
内部ポインタを使うことができない。
Morris(1982)による拡張を用いれば可能(以下の追加制約を必要とする)。
フィールド毎のタグビット
第2の圧縮パス(
updateBackwardReferences のことか？)の向きを逆にする。 ヒープが逆向きの走査が可能であること。
3.4 ワンパスアルゴリズム
3.5 考慮すべき点
過去の章のスライド
要認証
#スライド #まとめ