On the Fly Garbage Collection an Exercise in Cooperation (1978)

February 11, 2025

Go1.5で、ガベージコレクション (GC) のアルゴリズムが3色マーキングによるコンカレントマーク&スイープに変わった。このアルゴリズムの起源を辿ると、1978年のOn the Fly Garbage Collection an Exercise in Cooperationにいきつく。ポインタをたどってヒープを黒や灰色に着色するマーキングフェーズと、解放してよい白のヒープを解放するアペンディングフェーズ、この2つのフェーズを繰り返す。アルゴリズムはStop The World (STW)を抑制することを主眼におく。

2015年に書かれたThe Go BlogのGo GC: Prioritizing low latency and simplicityによれば、3色マーキングのコンカレントマーク&スイープはエンタープライズ向けのGCではない。それでも、3色マーキングの考え自体はJavaのZGCなど他のガベージコレクションで採用されている。

Rick HudsonのGo GC: Latency Problem Solvedや、その動画では、JavaとGoのランタイムを対比させて、Goのランタイムに適したGCのアルゴリズムを採用する必要性が説明されている。動画で最も強調されていた理由は、構造体の内部を指すポインタ interior pointerがフィールドを参照する間は構造体全体がメモリに残ることだった。また、Rick Hudsonのほかの資料によると、構造体のメンバーは連続する領域に割り当てられるため、関連のあるデータを構造体にまとめることで、キャッシュ効率を改善できる。

On the Fly Garbage Collection an Exercise in Cooperationは、ヒープをノード数が固定の有向グラフとみなしてノードを白、灰色、黒色に着色する。スタックや大域のオブジェクトから直接参照されるメモリ空間をルートノードとみなす。また、割り当て可能なヒープをリストで管理し、そのリストの先頭にもルートノードをつかう。ルートノードは複数あってよい。

有向グラフにおけるソースコードの処理をmutator, ガベージコレクタをcollectorという。 mutatorとcollectorは有向辺の追加、更新、削除をくりかえす。 collectorは、ルートから辿れないガベージノードだけを、線形リストに追加し、ルートから参照できるノードと区別する。

有向グラフにおけるアルゴリズムの目的は、すべてのガベージノードを有限のステップ数で線形リストに加えることに言いかえられる。具体的な有限のステップ数として、アルゴリズムは、アペンディング開始時にあるガベージノードが次のアペンディングフェーズの終わりまでに解放されることを保証する。また、STWの最小化はcollectorのアトミックな操作の最小化と言いかえられる。

証明を簡単にするために有向グラフに制約があたえられている。制約を導入しても、アルゴリズムを任意のプログラムに適用できる一般性は失われない。有向辺を削除ないし追加するのかを考えると、操作に対する証明の場合分けが増える。この場合分けを減らすために、すべてのノードの出次数を2にし、本来無い有向辺を特別なルートNILへの有向辺で表現する。 NILの2つ有向辺はNIL自身を指す。

ノードの色には、参照されるノードとガベージノードの区別、と、有限のステップ数でフェーズを終了させる役割がある。白、灰色、黒の順に濃い色だとすると、マーキングフェーズにおいて、ノードの色が薄くなることはない。アペンディングフェーズでは、collectorが、白のノードをガベージノードとみなし、線形リストに追加する。 mutatorは、有向辺をはじめて変更する場合を除き、前回変えた有向辺の向き先のノードの色が白であれば灰色に着色し、有向辺の向き先を変更する。着色と向き先の変更はそれぞれ別のアトミックな操作でよい。

マーキングフェーズは、ルートノード以外の灰色のノードがなくなるまで続く。以下の疑似コードはマーキングフェーズを表す。ただし、初期状態では黒のノードがないことを前提とし、ノードの数をMとおく。

for root in roots:
  if root.color == WHITE:
    root.color = GRAY

i, k = 0, M
	
while k > 0:
  c = nodes[i].color // atomic
  if c == GRAY:
    k = M
	for side in range(2):
      succ := nodes[i].successors[side] // atomic
	  // begin atomic
      if succ.color == WHITE:
	    succ.color = GRAY
	  // end atomic
	nodes[i].color = BLACK // atomic
  else:
    k -= 1
	
  i = (i + 1) % M

はじめに、collectorはすべての白のルートノードを灰色に着色する。そして、すべてのノードの色を順番に確認し、後続の白のノードを灰色にし、ノードを黒にする。一巡するまでに灰色を一度でも見かけなければ、マーキングフェースは終了する。線形リストのルートノードが灰色なので、mutatorが新たに線形リストに割当られたノードの色はマーキングフェーズが終わるまでには黒になる。

アペンディングフェーズは、白のノードをリストに追加し、黒のノードを白に着色する。その間、ルートノード以外に灰色のノードはない。以下疑似コードでアペンディングコードを示す。

for i in range(m):
  color := nodes[i].color // atomic
  if color == WHITE:
    free_list.append(nodes[i]) // atomic
  else: // color == BLACK
    nodes[i].color = WHITE // atomic

ただし、Goのガベージコレクションは文献どおり実装されているわけではない。先述の資料によると、ガベージコレクションが無効の期間がある。また、理論上は並行実行可能であるが実装を単純にするために、マーキングフェーズの終了処理時にSTWが起きる。