GC

Garbage Collection

GCがないとどうなるか

手動でメモリを管理しないといけない

問題

ダングリングポインタの参照

脆弱性ex: IE6/7 ゼロディ脆弱性

使用中のメモリ領域を誤って解放

メモリ系のバグはバグを特定しにくい

考案

1960年

Mark Sweep GCを発表

GCどうしの比較要素

安全性

スループット

完全性と即時性

停止時間

空間的オーバーヘッド

特定の言語への最適化

スケーラビリティとポータビリティ

種類

基本的なもの

応用

GCの大きな2種類

モダンなGC

「Rubyのしくみ」でサラッと触れられてた「JVMで使用できる新しい実験的なGC」

ガベージファースト

継続的同時圧縮

実装編

用語

粒

割り付けの最小単位

セル

小さな連続した粒のグループ全般

オブジェクト

メモリ領域上に配置される基本単位

ヘッダとフィールドによって構成される

ヘッダ

オブジェクト自体の情報(サイズ、種類など)を保持する

利用者は直接変更できない

フィールド

利用者が参照したり、書き換えたりできる部分

フィールドに置かれるデータはポインタか非ポインタの2種類

ポインタ

オブジェクトへのポインタは必ず先頭を指す

非ポインタ

値そのもの

ブロック

特定のサイズのアドレスを境界に整列したチャンク

サイズは通常2のべき乗

カード

2^k境界に整列したチャンクで、ページより小さく、スペース間のポインタを記録する手法に関連するもの

アプリケーション(GC対象となるオブジェクト間の参照関係)を変化させる

GCはミューテータの裏側で動いている

ミューテータが行うこと

オブジェクトの生成

ポインタの更新

評価項目

単位時間あたりの処理能力

GCを行っている間はミューテータの実行は停止する(しないものもある)

この「停止している時間」の最大値のこと

1回のGCで最もかかる時間

スループットと最大停止時間はトレード・オフの関係になることが多い

つまり、短いGCを多くの回数実行するか、回数を減らす代わりに一回の時間を増やすか

ヒープ領域の使用効率

ヘッダに多くの情報を詰めるとGCの効率は向上するが、ヘッダのサイズは小さい方が好ましい

参照の局所性

ワークリスト

ここに入る可能性のあるものは以下を満たす

ルートから辿れる

まだマークされていない

子を持っている

言語別リンク(あとで上とくっつけてまとめる

v1.10: concurrent Mark Sweep

v1.5: tri-color GC

Nim

↑多分こんなふうに言語ごとのドキュメントに書いてると思うので読もう

C, C++

Rust

Java (JVM)

minor GCがCopying GC

major GCがmark sweep

3つの独立したGCをコマンド引数で選択できる

シリアル

並行GCを使用しない。GC実行時はミューテータは停止する

並列

別スレッドでGCを実行

並行

並行で実行。停止時間をへらすように最適化しているが、ミューテータの全体的なスループットは低下するかもしれない

JavaScript

Mark Sweep

PHP

参照カウント

OCaml

コピーGC

Haskell

Copy GC

C#

Mark & Sweep

3世代の世代別GC

Lisp

マークスイープ

関連

RubyでGCを書く

参考

keen氏のブログになんかあったような

John McCarthyの本のフリーリスト実装について

Rubiniusで使用されたImmixアルゴリズムについて

JVMの全体的なGCアルゴリズムの説明とコマンド引数についてのドキュメント

書籍

まとまっているページ