ガベージコレクション(GC)の仕組み - 参照カウントから世代別・並行GCまで

newやmallocで確保したメモリは、いつ、誰が解放するのでしょうか。C言語なら書いた本人がfreeで返します。しかしPythonやJava、JavaScriptを書いていて、解放処理を意識した記憶はほとんどないはずです。その裏で働いているのがガベージコレクション(GC)です。この記事では、GCがなぜ必要なのか、どんなアルゴリズムで「もう使われないメモリ」を見つけるのか、そして主要な処理系が実際に何を採用しているのかを、土台から順に整理します。

GCとは何か、なぜ必要か

プログラムは実行中、ヒープと呼ばれる領域にオブジェクトを次々と確保します。問題は、その解放です。手動メモリ管理の言語では、確保(malloc)と解放(free)を人間が対応づけて書きます。これは高速で予測可能な反面、二種類の深刻なバグを生みます。

一つはメモリリークです。解放を忘れたメモリは使われないまま居座り続け、長時間動くサーバーではやがてメモリを食いつぶします。もう一つはダングリングポインタです。まだ使っているメモリを誤って解放し、その後アクセスすると、解放済み領域を読み書きしてクラッシュやセキュリティ脆弱性(use-after-free)につながります。二重解放(double free)も同種の危険です。

ガベージコレクションは、この解放をプログラマの手から処理系に委ねる仕組みです。GCは「プログラムから二度と到達できなくなったオブジェクト」をゴミ(garbage)とみなし、自動的に回収します。解放漏れや二重解放を原理的に防げるのが最大の利点で、その代わりに実行時のオーバーヘッドと、後述する一時停止(pause)という代償を払います。

NOTE

「到達できない」の判定が全体の鍵です。GCの起点となる変数やレジスタ、スタック上の参照をまとめてルート(root)と呼び、ルートからポインタをたどって届くオブジェクトを「生きている」、届かないものを「ゴミ」と判定します。

基本アルゴリズム1: 参照カウント

もっとも素朴な方式が参照カウント(reference counting)です。オブジェクトごとに「今いくつの参照から指されているか」を数え、代入のたびに増減させます。カウントがゼロになった瞬間、そのオブジェクトは誰からも指されていないので即座に解放できます。

a = [1, 2, 3]   # リストの参照カウントは 1
b = a           # 別名で参照 -> カウント 2
b = None        # 参照が1つ外れて -> カウント 1
a = None        # 最後の参照が外れ -> カウント 0 で解放

長所は、ゴミになった瞬間に回収できるので回収タイミングが分散し、大きな一時停止が起きにくいことです。短所は二つあります。カウント操作のコストが常時かかること、そして循環参照を回収できないことです。オブジェクトAがBを、BがAを参照し合っていると、外から誰も見ていなくても互いのカウントが1のまま残り、永遠に解放されません。この弱点を補うため、参照カウントを主軸にする処理系は循環を検出する補助的な仕組みを併用します。

基本アルゴリズム2: マークアンドスイープ

参照カウントとは発想が異なるのがトレース型(tracing)のGCです。その基本形がマークアンドスイープ(mark and sweep)で、二つのフェーズからなります。

マーク(mark): ルートから参照をたどり、到達できたオブジェクトすべてに印を付ける
スイープ(sweep): ヒープを走査し、印の付いていないオブジェクトを解放する

循環参照があっても、その循環がルートから到達不能なら丸ごとゴミと判定できます。参照カウントの弱点をここで克服できるわけです。

Loading diagram...

図のDとEは互いを参照していますが、ルートからは届きません。参照カウントでは回収できないこの循環も、マークアンドスイープなら「マークされなかった」という一事で回収できます。

基本アルゴリズム3: コピーGCとマークコンパクト

マークアンドスイープには弱点があります。解放を繰り返すとヒープに小さな空きが虫食い状に散らばり、合計は空いているのに大きなオブジェクトを置けなくなる断片化(fragmentation)です。これを解消するのが、オブジェクトを移動させる方式です。

コピーGC(セミスペース方式)は、ヒープを同じ大きさの二つの領域(FromとTo)に分けます。生きているオブジェクトだけをFromからToへ順に詰めてコピーし、コピーが終わったらFrom側はまるごと破棄します。生存オブジェクトだけを移動するので、生存率が低いほど効率がよく、コピー後は断片化も解消されています。欠点はヒープの半分を常に空けておく必要があることです。

マークコンパクト(mark-compact)は、マーク後に生存オブジェクトをヒープの片側へ寄せて詰め直します。半分を予約せずに断片化を解消できますが、オブジェクトの移動と参照の張り替えにコストがかかります。

基本アルゴリズム4: 世代別GC

実際のプログラムを観察すると、ほとんどのオブジェクトはすぐ死ぬという経験則が成り立ちます。これを世代仮説(generational hypothesis)と呼びます。ループ内の一時オブジェクトはすぐゴミになり、長生きするものは長生きし続ける、という偏りです。

この偏りを利用するのが世代別GC(generational GC)です。ヒープを「若い世代(young)」と「古い世代(old)」に分け、新しいオブジェクトはまず若い世代に置きます。若い世代だけを対象にした小さな回収をマイナーGC(minor GC)と呼び、高頻度で素早く行います。ここを生き延びたオブジェクトは「昇格(promotion)」して古い世代へ移し、古い世代を含む全体の回収はメジャーGC(major GC)としてまれに行います。

Loading diagram...

死にやすい若い世代を狭い範囲で頻繁に掃除するので、毎回ヒープ全体を走査するより平均コストが下がります。GCの計算量の考え方は計算量とBig-O記法入門の視点で捉えると整理しやすいでしょう。

トライカラーマーキングと並行GC

素朴なマークアンドスイープには、もう一つ大きな問題があります。マーク中にアプリケーションがオブジェクトの参照を書き換えると、印付けの整合性が崩れることです。そのため単純な実装ではマークの間、アプリを完全に止める必要があります。これがStop-the-world(STW)です。STWが長いと、その間アプリが応答できず、レイテンシ(遅延)が悪化します。

STWを短くするために考案されたのがトライカラーマーキング(tri-color marking)です。オブジェクトを三色に分類します。

白(white): まだ調べていない。最終的に白のまま残ればゴミ
灰(gray): 到達は確認したが、そこから出る参照をまだ調べ終えていない
黒(black): 到達済みで、参照先も調べ終えた

灰のオブジェクトがなくなるまで、灰を一つ取り出してその参照先を灰にし、自身を黒にする、という処理を繰り返します。この方式なら処理を途中で中断・再開できるため、マークをアプリと交互に少しずつ進めるインクリメンタルGCや、アプリと同時に走らせる並行(concurrent)GCが実現できます。並行実行の途中で参照が書き換わっても不変条件を守れるよう、代入時にライトバリア(write barrier)という小さなフックを挟むのが定石です。並行・並列の用語整理は並行と並列・プロセスとスレッドもあわせて読むと理解が深まります。

代表的な処理系のGC

ここまでの部品が、実際の言語処理系でどう組み合わされているかを見ていきます。以下は各処理系の公式ドキュメント等で確認した内容です。

Python(CPython)

CPythonは参照カウントを主軸にし、循環参照を回収できない弱点を補うために、循環専用の世代別マークアンドスイープ収集器を併用します。循環収集器は0・1・2の三世代を持ち、標準ライブラリのgcモジュールからgc.collect()での手動起動や無効化ができます。参照カウントは無効化できませんが、循環収集器は任意です。

Java(HotSpot VM)

HotSpot VMは複数のGCを選べます。JDK 21ではG1(Garbage-First)がデフォルトで、ヒープを多数の領域(region)に分けて世代を仮想的に管理し、一時停止を段階的・並列に抑えます(G1がデフォルトになったのはJDK 9のJEP 248から)。ほかに低レイテンシ用途のZGC(最大停止時間を1ms未満に抑えることを狙う。世代別版はオプションで有効化)、同じく低レイテンシ志向のShenandoah、スループット重視のParallel GC、小規模向けのSerial GCがあります。

Go

Goのランタイムは非移動(non-moving)・非世代別・並行のトライカラーマークスイープを採用します。ライトバリアを使いつつ、二度の短いSTWを挟むだけでマークとスイープの大半をアプリと同時に進めます。回収の頻度は環境変数GOGC(デフォルト100)で制御し、Go 1.19以降は総メモリ量の上限を与えるGOMEMLIMITも使えます。

JavaScript(V8)

ChromeやNode.jsが使うV8は、GCパイプライン全体をOrinocoと呼び、世代別構成をとります。若い世代のマイナーGCはセミスペース方式のコピーGCであるScavenger(並列化済み)が担当し、ヒープ全体のメジャーGCはマークコンパクトが担当します。並行・並列・インクリメンタルの各技法を組み合わせて一時停止を短くしています。

Ruby

CRuby(MRI)は世代別かつインクリメンタルなマークアンドスイープを採用します。世代別GCはRuby 2.1、インクリメンタルマークはRuby 2.2で導入され、Ruby 2.7では断片化を解消するコンパクションが追加されました(コンパクションは自動ではなく明示的に呼び出します)。

まとめ

GCは「到達不能なオブジェクトを見つけて回収する」という一点を、さまざまなアルゴリズムで実現してきました。参照カウントは即時性に優れる一方で循環に弱く、マークアンドスイープは循環を扱えるが断片化とSTWの課題を抱えます。コピーGCやマークコンパクトは断片化を、世代別GCは平均コストを、トライカラーによる並行GCはレイテンシを、それぞれ改善するために生まれた工夫です。実際の処理系はこれらを目的に応じて組み合わせています。使っている言語のデフォルトGCが何かを知り、若い世代・古い世代やSTWといった語彙で挙動を捉えられるようになると、メモリまわりの性能問題にぐっと向き合いやすくなります。データ構造そのものの挙動はハッシュテーブルの仕組みもあわせてどうぞ。

参考リンク

Python公式ドキュメント: gc — Garbage Collector interface: https://docs.python.org/3/library/gc.html
Python Developer's Guide: Design of CPython's Garbage Collector: https://devguide.python.org/garbage_collector/
Oracle: HotSpot Virtual Machine GC Tuning Guide - Available Collectors (JDK 21): https://docs.oracle.com/en/java/javase/21/gctuning/available-collectors.html
The Go Programming Language: A Guide to the Go Garbage Collector: https://go.dev/doc/gc-guide
V8 blog: Trash talk - the Orinoco garbage collector: https://v8.dev/blog/trash-talk
V8 blog: Orinoco - young generation garbage collection: https://v8.dev/blog/orinoco-parallel-scavenger