参照カウントGC

Reference Counting GC

各オブジェクトが「自分への参照の数」を記録しておく

チャンクがなくなったタイミングでGCを走らす

ミューテータが処理を行う中で、カウンタの増減を行う

カウンタの増減は、以下のいずれかの場合に行われる

オブジェクトが新規作成されたとき、にカウンタを増やす

ポインタが更新された時、増減させる

減らした時に、0になったらGCを行う

ヘッダに格納するもの

カウンタ

符号なしの整数

メリット

ゴミがすぐに回収できる

Mark Sweep GCとの違いが顕著な点。

これによって、ゴミがメモリ領域を占拠する瞬間がないようになっている

最大停止時間が短い

1個1個を回収するので、最大停止時間は短い

ポインタをたどる必要がない

Mark Sweep GCではSwepp Phaseに各オブジェクトを見て、ポインタをたどって生きているかどうかを判断していたが、それをする必要がないのでコストが低くなる

デメリット

カウンタの値の増減処理が重い

一般的に、ポインタの更新は頻繁に起こるので、そのたびにカウンタの増減を行うので、重くなってしまう

カウンタに多くのビットが必要

例えば32bitマシンの場合、2^32個のオブジェクトが同時に一つのオブジェクトを参照する可能性がある

なので、それに備えるために各オブジェクトのカウンタに32bitを用意しないといけない

それらの領域を使わない場合、それらの領域が余分に必要になってしまう

例えば2つしかフィールドを持たない場合、カウンタがオブジェクトの1/3を占めてしまう

実装が煩雑

循環参照が回収できない

例えば2つのオブジェクトが互いに参照しあっていると、それらのカウンタは共に1になるが、それらはルートからは辿れない独立したゴミになっているので回収したい、が、カウンタは1なので回収できない

デメリットに対する対策

Deferred Reference Counting(遅延参照カウント法)

「ルートからのポインタの更新が頻発する」問題への対策

手順

1. 各オブジェクトはルートからの参照はカウントせずに、カウンタの値が0になったものを一時的にZCT(Zero Count Table)に保存しておく

2. ある程度溜まったら、テーブル上にあるオブジェクトがルートから参照されているかどうかを確認

3. ルートから参照されていればカウンタを増加し、参照されていなければ削除

メリット

ある程度溜めてからルートからの参照を反映させるので、頻繁に起こるルートからのポインタの更新を抑える

デメリット

ゴミが一定時間メモリ領域を占有することになる(せっかく参照カウントのメリットだったのに。)

ZCT上のオブジェクトに対し一気に操作するので最大停止時間が増大する

Sticky 参照カウント法

「カウンタに多くのビットが必要」への対策

今までは32bitをカウンタに使っていたが、5bitにしてみる。

すると、2^5-1(=31)個までしかカウントできなくなる。31個以上参照された場合は以下の2通りの扱い方がある

なにもしない

これを超えたら、もうずっと放置。管理しない。

実際のところ、多くのオブジェクトは生成されてからすぐに死ぬという研究報告があるらしい、つまりカウンタは多くの場合0もしくは1を取るということ

ということは、31個以上も参照されているということはとても重要なものなので、将来的にごみになる可能性も低いと考えて差し支えない

ちょっと変わったMark Sweepをバックアップとして行う

カウンタがオーバーフローしたあとにゴミになったものや、循環参照したゴミも回収できる

普通のMarkSweepGCよりも時間がかかりスループットが悪化する

1bit Reference Counting (1ビット参照カウント)

1bitのみで参照カウントを行う

0なら悲参照数1、1なら非参照数2以上を示す

キャッシュミスを減らせる

Partial Mark & Sweep (部分マークスイープ法)

循環参照をもつかもしれないオブジェクト郡に対してのみMark SweepGCを行う

(ちゃんと読んでない)

どっかに書いてたこと

難しいのは割り当てられたメモリが、今後必要とされない」ことを保証すること

メモリーの断片が不要になって解放する必要があるかを決定するには、開発者による判断が必要なことが多いです。

並行参照カウント