TL;DR
- 従来の三色マーキングはプロセッサ中心の設計で、メモリの局所性が欠けており、今のハードウェアと合わなくなっている。
- Green Tea GC は 8KiB のスパンを単位に走査し、近くのオブジェクトをまとめて処理することで CPU コストを減らす。
内容
従来の GC の課題
Go の従来の GC は、三色マーキングを並列に行う。オブジェクトの状態を、未走査（White）、処理中（Gray）、走査済み（Black）で管理する古典的なアルゴリズムである。並行処理でチューニングされているが、次の課題がある。
1つ目はハードウェアの傾向とのずれである。CPU のクロック速度に比べて DRAM のクロックは伸び悩んでおり、両者の性能差が開いている（メモリウォール）。
2つ目はメモリの局所性の欠如である。GC がポインタをたどるとき、物理的に離れたアドレスの間を頻繁に移動しうるので、CPU のキャッシュミスが多発し、遅い DRAM へのアクセスが増える（空間的局所性）。同じメモリ領域へのアクセスが GC サイクル全体に分散すると、キャッシュしたデータを再利用できない（時間的局所性）。また、NUMA のような不均一なメモリトポロジを認識できず、メモリアクセスのコストが均一だと仮定している。
3つ目は設計思想と時代とのずれである。現行の GC は、局所性を犠牲にしてでも、すべての CPU コアを使い切って積極的に並列化するプロセッサ中心の設計である。ハードウェアが進化して、このトレードオフの損得が逆転し、性能への影響が目立つようになった。
Green Tea GC のコンセプト
Green Tea Garbage Collector は、個々のオブジェクトではなく、メモリブロック（8KiB のスパン）を処理の単位にする。「メモリ内で近いオブジェクトを一緒に処理したい」という動機から生まれ、コア数が多い環境や、小さなオブジェクトを大量に扱う処理で特に効果がある。ただし、今のところ対象は 512 バイト以下のオブジェクトだけで、それより大きいものは従来のアルゴリズムで処理する。Green Tea GC は、従来の GC アルゴリズムの延長にあるものである。
GC Worker も専用に実装されており、ゴルーチンのスケジューラで実績のある Work-Stealing のランキューに基づいている。Worker は、スパンをキューに入れてから取り出すまでに隣接したオブジェクトが複数たまっていると想定し、それらをまとめて走査する（楽観的アルゴリズム）。
メリット
これらにより、CPU コスト、特にスキャンループのコストを減らせる。
- ランダムアクセスが減る。オブジェクト単位でポインタをたどるとランダムアクセスが起きやすいが、スパン内の線形走査は近いアドレスへのアクセスが多い。
- スパン内のオブジェクトのメタデータも持っているので、事実上ゼロコストでプリフェッチできる。
- スパンを一度だけキューに入れる設計で操作回数を減らし、グローバルキューでの競合も減らす。
単一オブジェクト最適化
スパン内にオブジェクトが 1 つしかない場合は、従来の GC の方が圧倒的に速い。そこで、このケースに特化した最適化も行っている。Representative オブジェクト（最初のオブジェクト）とフラグを導入し、スパンに属するオブジェクトが 1 つだけのときは O(1) でアクセスできるようにする。
今後
Green Tea GC は Go 1.26 のマイルストーンに含まれており、安定化に向けて開発が進んでいる。SIMD（AVX-512）のサポートもすでにマージされている。これは Green Tea GC のためというより純粋な SIMD のサポートだが、スパン単位で処理するので Green Tea GC も恩恵を受けられる。
キーワード
- Go
- ガベージコレクション
- 三色マーキング
- Green Tea Garbage Collector
- メモリウォール
- 局所性
- NUMA
- トレードオフ
- ゴルーチン
- Work-Stealing
- SIMD
自分の理解
単一オブジェクト最適化で代表のオブジェクトを決める話を聞いて、Raft を思い出した。
Green Tea GC では、グローバルキューが使われなくなるのだろうか。