gc(mark-sweep ガベージコレクタ)

要らなくなったメモリを誰がどう見つけて返すのかを Go でモデル化する。判定基準は到達可能性で、スタックやグローバル(ルート)から辿れるものだけが生き、辿れないものは回収してよい。実装は tricolor マーキングで、white / gray / black の 3 色を使って到達集合を広げ、残った white を掃く。参照カウントが漏らす循環参照も、ルートから辿れなければゴミなので回収できる。

この章で作るもの

malloc した領域を free し忘れればメモリリーク、2回 free すればクラッシュ。この管理を人間に任せず、ランタイムが自動でやるのが GC だ。ではランタイムは「もう要らない」をどう判定するのか。答えは到達可能性。今このプログラムが辿れるオブジェクトだけが生きている、という一点にある。

        roots(スタック/グローバル)
          │
          ▼
        ┌───┐     ┌───┐     ┌───┐
        │ A │────▶│ B │────▶│ C │     到達可能 = 生存(mark)
        └───┘     └───┘     └───┘
                      ▲──────────┘

        ┌───┐     ┌───┐              ┌───┐
        │ E │◀───▶│ F │              │ G │   ルートから辿れない = garbage(sweep)
        └───┘     └───┘              └───┘

GC はヒープを有向グラフとして見る。ルート(スタック/グローバル)から参照をたどって到達できるものが生存。A↔B のように循環していても、ルートから辿れるなら生きている。逆に E↔F は互いを指し合っていても、どのルートからも辿れないのでゴミになる。ここが参照カウントとの決定的な違いだ

順に見ていく。

到達可能性 = 生死: 参照カウントではなく「ルートから辿れるか」で決める
tricolor マーキング: white / gray / black の3色で到達集合を広げる
不変条件「black は white を直接指さない」: 各手でこれを保つ。並行 GC の土台

① ヒープをグラフとして持つ

まずヒープを、オブジェクトの有向グラフとして表す。オブジェクトは ID を持ち、参照は「相手の ID」で表す。ポインタの代わりに ID を使うことで、実メモリ無しに到達可能性だけを純粋に扱える。col は GC 中のマーキング色だ:


// color は tricolor(3色)マーキングの色。mark-sweep や並行 GC の土台となる考え方。
//
//	white = まだ到達していない(回収候補)
//	gray  = 到達したが、参照先(子)をまだ走査していない
//	black = 到達し、子も走査し終えた
type color int

const (
	white color = iota
	gray
	black
)

// String は色の表示名を返す(トレースやデモ用)。
func (c color) String() string {
	switch c {
	case white:
		return "white"
	case gray:
		return "gray"
	case black:
		return "black"
	}
	return "?"
}

// Object はヒープ上の1オブジェクト。refs は「このオブジェクトが指している」他
// オブジェクトの ID(構造体のフィールドに入ったポインタに相当)。col は GC 中の
// マーキング色で、平常時は white。
type Object struct {
	ID   int
	Name string
	refs []int
	col  color
}

// Refs はこのオブジェクトが参照する ID の一覧を返す(内部スライスは渡さない)。
func (o *Object) Refs() []int {
	out := make([]int, len(o.refs))
	copy(out, o.refs)
	return out
}

Heap はオブジェクト集合とルート集合を持つ。ルートとは、スタックのローカル変数やグローバルから直接指されているオブジェクトで、GC が生死を辿り始める起点だ。AddRoot / RemoveRoot は「スタック変数がそのオブジェクトを掴む/手放す」に対応する:


// Heap はオブジェクトの集合と、ルート集合を持つ。ルートとは、スタックのローカル変数や
// グローバル変数から「直接」指されているオブジェクト——GC が生死を辿り始める起点だ。
// GC は「ルートから辿れるか」だけでオブジェクトの生死を決める。
type Heap struct {
	objs   map[int]*Object
	roots  map[int]bool
	nextID int
}

// NewHeap は空のヒープを作る。ID は 1 から振る。
func NewHeap() *Heap {
	return &Heap{objs: map[int]*Object{}, roots: map[int]bool{}, nextID: 1}
}

// Alloc は新しいオブジェクトを確保して ID を返す(確保直後は誰からも指されていない)。
func (h *Heap) Alloc(name string) int {
	id := h.nextID
	h.nextID++
	h.objs[id] = &Object{ID: id, Name: name, col: white}
	return id
}

// PointTo は from が to を参照するようにする(from のフィールドに to を代入するイメージ)。
// 同じ参照は重複して持たない。
func (h *Heap) PointTo(from, to int) {
	o := h.objs[from]
	if o == nil {
		return
	}
	for _, r := range o.refs {
		if r == to {
			return
		}
	}
	o.refs = append(o.refs, to)
}

// Unpoint は from → to の参照を1本外す(フィールドに nil を代入するイメージ)。
func (h *Heap) Unpoint(from, to int) {
	o := h.objs[from]
	if o == nil {
		return
	}
	kept := make([]int, 0, len(o.refs))
	for _, r := range o.refs {
		if r != to {
			kept = append(kept, r)
		}
	}
	o.refs = kept
}

// AddRoot はオブジェクトをルートにする(スタック変数がそれを掴んだ状態)。
func (h *Heap) AddRoot(id int) { h.roots[id] = true }

// RemoveRoot はルートから外す(スタック変数がスコープを抜けた状態)。
// これを最後の到達経路にしていたオブジェクト群は、次の GC で回収される。
func (h *Heap) RemoveRoot(id int) { delete(h.roots, id) }

// Get は ID のオブジェクトを返す(無ければ nil)。
func (h *Heap) Get(id int) *Object { return h.objs[id] }

// Live は現在のオブジェクト数を返す。
func (h *Heap) Live() int { return len(h.objs) }

// IDs は生存オブジェクトの ID を昇順で返す。
func (h *Heap) IDs() []int {
	out := make([]int, 0, len(h.objs))
	for id := range h.objs {
		out = append(out, id)
	}
	sort.Ints(out)
	return out
}

// Roots はルート ID を昇順で返す。
func (h *Heap) Roots() []int {
	out := make([]int, 0, len(h.roots))
	for id := range h.roots {
		out = append(out, id)
	}
	sort.Ints(out)
	return out
}

② mark: tricolor で到達集合を広げる

ここが心臓部。マーキングは3色で進む。ルートを gray にして始め、gray を1つ取り出して black にし、その参照先の white を gray にする。これを gray が尽きるまで繰り返す。すると到達集合が波紋のように広がっていく:


// Stats は 1 回の GC の結果。
type Stats struct {
	Before   int   // GC 前のオブジェクト数
	Marked   int   // 到達(生存)と判定した数
	Swept    int   // 回収した数
	After    int   // GC 後のオブジェクト数
	SweptIDs []int // 回収した ID(昇順)
}

// Collection は 1 回の mark-sweep の途中経過を表す。tricolor マーキングを
// 1 手ずつ進められるので、GC の内部をそのまま観察できる。
// gray は「到達したが子をまだ走査していない」オブジェクトの作業リスト(ワークリスト)。
type Collection struct {
	heap *Heap
	gray []int
}

// Start はマーキングを始める。まず全オブジェクトを white に戻し、
// ルートを gray にしてワークリストに積む——ここが到達判定の起点。
func (h *Heap) Start() *Collection {
	for _, o := range h.objs {
		o.col = white
	}
	c := &Collection{heap: h}
	for _, id := range h.Roots() {
		if o := h.objs[id]; o != nil && o.col == white {
			o.col = gray
			c.gray = append(c.gray, id)
		}
	}
	return c
}

// MarkStep は gray を1つ取り出して black にし、その参照先の white を gray にする。
// これを繰り返すと到達集合が波紋のように広がる。tricolor の不変条件——
// 「black は white を直接指さない」——を各手で保つのが肝で、これが並行 GC の基礎になる。
// gray が尽きたら(到達集合が確定したら)false を返す。
func (c *Collection) MarkStep() bool {
	if len(c.gray) == 0 {
		return false
	}
	id := c.gray[0]
	c.gray = c.gray[1:]
	o := c.heap.objs[id]
	o.col = black
	for _, r := range o.refs {
		if child := c.heap.objs[r]; child != nil && child.col == white {
			child.col = gray
			c.gray = append(c.gray, r)
		}
	}
	return true
}

// Marking はまだマーク中(gray が残っている)かを返す。
func (c *Collection) Marking() bool { return len(c.gray) > 0 }

// Color は id の現在のマーキング色を返す。
func (c *Collection) Color(id int) color {
	if o := c.heap.objs[id]; o != nil {
		return o.col
	}
	return white
}

// GrayIDs は現在ワークリストに積まれている(gray の)ID を返す。
func (c *Collection) GrayIDs() []int {
	out := make([]int, len(c.gray))
	copy(out, c.gray)
	return out
}

// Sweep はマーキング完了後に呼ぶ。到達しなかった white のオブジェクトを全て解放する。
// マーク済みのオブジェクトは white に戻して次の GC に備える。
//
// 生存オブジェクトが回収対象を指すことは起こり得ない——指していれば、そのオブジェクトは
// マーク中に gray になり生存側に入るからだ。だからダングリング参照は生じない。
func (c *Collection) Sweep() Stats {
	before := len(c.heap.objs)
	var swept []int
	marked := 0
	for id, o := range c.heap.objs {
		if o.col == white {
			swept = append(swept, id)
		} else {
			marked++
		}
	}
	sort.Ints(swept)
	for _, id := range swept {
		delete(c.heap.objs, id)
	}
	for _, o := range c.heap.objs {
		o.col = white
	}
	return Stats{
		Before:   before,
		Marked:   marked,
		Swept:    len(swept),
		After:    len(c.heap.objs),
		SweptIDs: swept,
	}
}

// Collect は mark(最後まで)→ sweep を一気に行う便利関数。
// 実機の naive な mark-sweep は、この間プログラムを止める(stop-the-world)。
func (h *Heap) Collect() Stats {
	c := h.Start()
	for c.MarkStep() {
	}
	return c.Sweep()
}

MarkStep の各手では、「black は white を直接指さない」という不変条件が保たれる。black(走査済み)にする前に、その子を必ず gray に格上げするからだ。この性質は、プログラムを止めずに GC する(並行・インクリメンタル GC)ための理論的な土台になる。マークが尽きたら、Sweep が残った white を全て解放する。

ここで大事なのは、生存オブジェクトが回収対象を指すことは起こり得ないという点だ。もし指していれば、その相手はマーク中に gray になり生存側に入る。だから sweep でダングリング参照が生まれることはない。

③ 循環参照が回収できる理由

この方式の利点は、循環参照を正しく回収できることだ。E と F が互いを指し合っていても、どのルートからも辿れなければ、両方とも white のまままとめて回収される。

参照カウント方式(「何本指されているか」を数え、0 で解放)はこれができない。E ↔ F は互いにカウント 1 を持ち続けるので、永久に 0 にならずリークする。Python が参照カウントに加えて循環検出 GC を、Swift が弱参照(weak)を必要とするのは、まさにこの穴を塞ぐためだ。到達可能性で判定する mark-sweep には、この穴が最初から無い。

動かす

下のデモは、この mark-sweep をそのままブラウザで動かしている(Go 実装の考え方を JS に移植)。ヒープにはルートから辿れる A↔B の循環と、辿れない E↔F の循環、孤立した G がある。「mark 1手」で tricolor の色が広がる様子を、「sweep」で white が回収される様子を確かめてほしい。ルート参照を外すと、そこからしか辿れなかった部分グラフがまとめてゴミになる。到達可能性がすべてを決めているのが見える。

デモgc(mark-sweep)mark 中 — gray(作業リスト): root

white 未到達(回収候補)

gray 到達・子は未走査

black 走査済み(生存確定)

ルートから辿れる A↔B・C→D は生存。互いを指し合う E↔F はどのルートからも辿れないのでゴミ——参照カウントが漏らす循環を mark-sweep は回収できる。 root→C を外すと C・D がまとめてゴミになる。

設計の観点: GC の方式とトレードオフ

参照カウント vs トレース(mark-sweep 系): 参照カウントは即座に解放でき実装も素直だが、循環を漏らし、カウント更新のコストが常にかかる。トレース方式は循環を掃けるが、GC のタイミングでまとめて仕事をする。多くの言語(Java/Go/JS)は後者の系統
stop-the-world とレイテンシ: naive な mark-sweep は GC 中プログラムを止める。ヒープが大きいと停止時間が伸び、応答性が落ちる。だから実用 GC は並行(プログラムと同時にマーク)・インクリメンタル(少しずつ)・世代別(若いオブジェクトだけ頻繁に見る)といった工夫で停止時間を削る
tricolor 不変条件と write barrier: 並行マーク中にプログラムが「black から white へ」新しい参照を張ると、white が見逃されて誤って回収されうる。これを防ぐのが write barrier だ。ポインタ書き込みを GC がフックして、white を gray に格上げする。本章の不変条件がそのまま実務の要になる
世代仮説: 「ほとんどのオブジェクトは若くして死ぬ」。だから若い世代(nursery)だけを頻繁に GC すれば、少ないコストで大半のゴミを回収できる。Java の G1/ZGC、Go 以外の多くのランタイムが採る

メリット・デメリットと実例

方式	循環回収	停止時間	即時性	実例
参照カウント	漏らす	無し(逐次解放)	即座	CPython(基本)、Swift ARC
mark-sweep(本章)	回収できる	大(stop-the-world)	GC 時	初期の JVM、素朴な実装
世代別 mark-sweep	回収できる	中	GC 時	Java(Parallel/G1)、.NET
並行 mark-sweep	回収できる	小(数百µs〜)	GC 時	Go(write barrier)、ZGC

裏どり:

CPython: 参照カウントが基本。循環は別途 gc モジュール(世代別のトレース)が回収する。参照カウント単体では循環を漏らす証拠
Go の GC: 並行 mark-sweep。三色マーキングと write barrier で、プログラムを走らせたまま(数百µs の短い停止で)マークする。本章の tricolor はその中核の最小版
Java の G1 / ZGC: 世代別 + 並行 + リージョン分割で、巨大ヒープでも停止時間を数ms〜サブms に抑える。停止時間を「予算」として設定できる
Swift の ARC: コンパイル時に参照カウント操作を挿入する参照カウント方式。循環は開発者が weak / unowned で断ち切る必要がある。mark-sweep なら不要な手当て

簡略化したこと

stop-the-world 前提: マーク中にプログラムが参照を書き換えない前提。実機の並行 GC が使う write barrier は実装しない(仕組みは設計の観点の節で説明)
mark-sweep のみ: コピー GC・世代別・コンパクションは扱わない(対比としてのみ言及)
確保器・断片化なし: sweep は印を消すだけ。free list・メモリの空き管理・コンパクションは無し
オブジェクトは個数で数える: バイト単位のヒープ会計はしない
ルートは手動指定: 実機はスタックフレームやレジスタを走査してルートを見つける(スタックマップ)。ここでは集合として明示的に持つ

参考資料

Richard Jones, Antony Hosking, Eliot Moss, The Garbage Collection Handbook — GC の決定版
Dijkstra ほか, "On-the-Fly Garbage Collection: An Exercise in Cooperation"(1978) — tricolor の原典
Go の GC ガイド — 並行 mark-sweep と write barrier の実際
実装: foundations/gc

gc(mark-sweep ガベージコレクタ) ​

この章で作るもの ​

① ヒープをグラフとして持つ ​

② mark: tricolor で到達集合を広げる ​

③ 循環参照が回収できる理由 ​

動かす ​

設計の観点: GC の方式とトレードオフ ​

メリット・デメリットと実例 ​

簡略化したこと ​

参考資料 ​