ガベージコレクションの種類

プログラム

今時の言語はだいたいガベージコレクションが備わってるんだけど、デストラクタが使える言語と使えない言語があったり、JavaはGCのタイミングが……などと言われたりするので、GCにはどんな種類があるのか調べてみた。
自分はGCに詳しいわけでもなんでもなくて、ググりまくって調べた結果をまとめただけなので間違っている箇所があるかもしれない。

ざっと4つぐらいの種類が出てきたが、大別すると参照カウントで管理するタイプと全走査して使われてないものを回収するタイプの二種類に分かれるようだ。

リファレンスカウント

オブジェクト自身にカウンタを持たせ、参照が増えるたびにカウンタを増やし、参照が減るたびにカウンタを減らす。そうしてカウンタが0になったときにオブジェクトを破棄する。
言語内部だけでなく、リソースの管理などアプリケーションレベルでも活躍してたりする。

メリット
  • GCの負荷が分散される（デメリットでもあるかもしれない）。
  • 必要なくなったオブジェクトが即座に解放される。
デメリット
  • 循環参照を解放できない。
  • 参照カウントが頻繁に書き換わるような状況では、書き換え処理そのものが問題になる。
  • 実装によっては大量のオブジェクトが一斉に解放されることがあり、処理が遅くなる場合がある。


一言で言うと、デストラクタが利用できるけど循環参照に気をつけないといけない。
循環参照へのアプローチとしてはウィークリファレンス（weak; カウンタを変更しないリファレンス）や、マーク＆スイープなどの併用がある。

マーク＆スイープ

グローバルオブジェクトやスタック上のオブジェクトなど「確実に必要なオブジェクト（GCのルート）」と、そこから再帰的に辿ることの出来る「到達可能なオブジェクト」にマークをつけていき、全ての調査が終わった段階でマークの付いていないオブジェクトを破棄する手法。

メリット
  • 参照カウントがないので、GCが動いてないときは高速。
  • 循環参照も解放できる。
デメリット
  • オブジェクト総なめなのでGCの処理自体は負荷が高い。
  • GCを走らせるタイミングが難しい。


一言で言うと、循環参照とか気にしなくてもいいけど、デストラクタの利用が絶望的。

ストップ＆コピー

マーク＆コピーの変形。
メモリ領域を複数用意しておいて、マークをつける処理の代わりにもう一方へコピーし、最後に古い領域に残っているオブジェクトを破棄し、新しいメモリ領域をアクティブとする。

メリット
  • GCと同時にコンパクション（デフラグ）も行える。
  • 参照しているオブジェクト同士を近くに配置できるのでキャッシュにヒットしやすくなる。
デメリット
  • メモリ領域が倍以上必要になる。
  • オブジェクトの位置が変わってしまう。

世代別ガベージコレクション（ジェネレーション・スカベンジング）

経験上、オブジェクトの利用には「生成してはすぐに破棄する一時的なもの」と「長期的に生存するもの」の二種類に分かれるので、メモリ領域を世代別に分けて管理するように工夫した、マーク＆スイープやストップ＆コピーの派生的な手法。
長期的に生存すると思われるオブジェクトをひとまず置いておくことで対象を絞り込み高速化を図る。

  1. 第一世代に属するオブジェクトは頻繁に回収する。
  2. 第二世代に属するオブジェクトは基本的に回収せず、長いインターバルやメモリ不足が発生しそうな場合に回収する。
  3. 第一世代で一定回数以上回収されなかったオブジェクトは第二世代に移動する。
メリット
  • マーク＆スイープやストップ＆コピー単体よりもバランスよくGCが行える。
  • 閾値や第一世代領域のサイズなどのチューニングが行える。
  • 仮想記憶との相性がよい。
デメリット
  • マーク＆スイープやストップ＆コピーのデメリットは（程度の差こそあれ）依然として引き継ぐ。

言語と採用されているGC

ざっと並べてみようと思ったんだけど、バージョンによって違ったり独自の改良が加えられてたり、呼び名が違うのかはたまた新しいタイプなのかわからなかったりと、調べるのが面倒くさそうなのでやめた。

参考ページ