References will be Garbage

参照カウント方式のメモリ管理機構ではメモリ解放のプロセスを分散できるために、他のメモリ管理と比べて目に見える停止時間が少ない。 ただ、純粋な参照カウント方式では全てのオブジェクトの状態を管理することは難しくて、例えば循環参照などの問題が発生する。 歴史は色々あるのでそうした問題解決方法について少し調べたものをまとめてみた。 GCハンドブックなどを見れば一通り書いてあるので、気になったら書籍を参考にしてもらえればと思ったり。

循環参照の解決

参照を持っていればオブジェクトは破棄されない。そのため参照カウント方式のメモリ管理機構では参照の状態が循環状態になるとオブジェクトは一生解放されないという問題点がある。以下はReferenceクラスのインスタンス変数としてお互いを参照している例である。この状態ではa, bそれぞれ他のオブジェクトからの参照が残っているため、参照カウント方式のメモリ管理ではどちらも解放されない。(rubyっぽく書いているが一応疑似コード)

class Reference
  instance_var :ref
end

a = classA.new
b = classB.new

a.ref = b
b.ref = a

弱参照と強参照

一つの手段として参照に強弱を持たせる。それぞれ強参照、弱参照と呼び、強参照は一般的な参照と似たようなもので。参照されている先のオブジェクトは参照が残っている限り破棄されない。 対して、弱参照は参照先から強参照が消えると破棄される。つまり破棄を防ぐ強制力を持たない。

対策としてしばしば参照カウント方式のメモリ管理機構には弱参照の概念が導入される。 例えば、イミュータブルな参照を弱参照で扱ったり、強弱両方の参照記法を用意し、プログラマに明示させるなどの方法がある。

もともと手動管理であったり、 静的にメモリを管理できる機構が備わっている場合は負担は少ないだろうけど、 記述のミスが原因でメモリリークを引き起こしたりする可能性があるため若干怖い節がある。

ちなみにC++11以降ではスマートポインタ、objective-cではARC(Auto reference count)、RustではArc・Rcが似たような機能を持っている。

ガベージコレクションGC)の分散

また、別の対策としてあるのが、別のGCを導入することである。 例えば Mark and sweep を導入し、使用未使用の状態をフラグで管理することで循環参照状態のオブジェクトを発見、破棄できる。

逆に Mark and sweep のみの構成ではMarkフェーズ、sweepフェーズの負荷が大きく、プログラムに停止時間を与える可能性がある。 そのため、参照カウントを用いて適度にオブジェクトの破棄を進めつつ、参照カウントで破棄できないオブジェクトをまとめて破棄する。 互いの欠点を補いつつ複数のアルゴリズムGCしていくのは一般的な手段であると言える。

例えば、Python2.2では参照カウント方式のGCと Mark and sweep を組み合わせてメモリ管理を動的に行っている。 最近あったその手の話では、instagramがWebサーバーへのリクエスト時にMark and sweepによるGCを停止させ、参照カウントのみでメモリ管理を一時的に行うことで性能を向上させるなどの工夫があった。*1

参照カウントのトレードオフ

闇雲に参照カウントを入れればフルGCの機会が減って性能が向上するわけでもない。 オブジェクトの参照をカウントするにはそれ専用の領域が必要になる。すなわち、オブジェクトが確保するヒープ領域には最大オブジェクト数分のカウントが可能な領域が余分に確保される。 余分に確保されるということはヒープ領域をフルに活用できるない。フルに活用できないのであればメジャーGCの頻度は向上するだろう。 結局、参照カウントによって分散できるはずが、総フルGC時間が長くなってしまい、逆に性能が悪化する恐れがある。

そこで例えば、参照カウント用のビット数を絞る方法なども考えられる。例えば、ビット数を1ビットとして参照カウントをし、2つ以上の参照があった場合には参照カウントによるGCを諦め、他のGCに処理を移譲する。 こういった方法は一般的なオブジェクトの生存期間や参照の数について統計やベンチマークを行い、言語やフレームワーク、設計の特性からビット数を工夫することで性能は向上する可能性がある。