最速Green Tea 🍵 Garbage Collector

LTで使った資料です。
内容はほぼこのissueのまとめです。

runtime: green tea garbage collector #73581
(https://github.com/golang/go/issues/73581)

Transcript

1. 最速Green Tea Garbage Collector 2025/05/08 kuroda naoki 1
2. ※ このスライドは2025/05/08時点の情報です。 ※ 説明のために省略している部分があるので、正確な情報が知りたい方は、ぜ ひ　runtime: green tea garbage collector #73581 をチェックしてみてくださ い。 2
3. 三色マーキング オブジェクトを3色で分類して追跡 白: まだ到達していない/未マークのオブジェクト（未処理） 灰: 到達したが子オブジェクトが未処理のオブジェクト（処理中） 黒: 到達済みで子オブジェクトも全て処理済みのオブジェクト（処理済み） mark & sweep i. マーキングフェーズ: ルートから到達可能なオブジェクトをマーク ii. スイープフェーズ: マークされていないオブジェクトを解放 既存のGo GCの基礎 3
4. 並行実行によるSTW時間の削減 Go 1.5で導入されたconcurrent GC STW（Stop The World）を最小限に抑える設計 マーキングフェーズの並行実行 goroutineと同時にGCワーカーが動作 メモリ割り当て量に基づく新GCサイクル開始 ライトバリア（Write Barrier） オブジェクトの参照変更を追跡 マーキング漏れを防止 Goにおけるconcurrent GCの動作 4
5. 1. メモリ制約の問題 コア数の増加により物理的に制限されたメモリバスへの負荷が増大 光速の制約（speed-of-light constraints）が、メモリアクセスの遅延の要因となり、より不均一 なメモリ構造が必要に 2. 既存GCの局所性の問題 空間的局所性の問題：既存GCのグラフ走査はメモリの完全に異なる部分間をジャンプ 時間的局所性の問題：同じメモリへの繰り返しのアクセスが GC サイクル全体に分散 3. パフォーマンスの問題 GC 時間の約 85% がスキャンループに費やされる そのスキャンループの CPU サイクルの 35% 以上がメモリアクセス待ちに使用 多コアシステムと不均一なメモリ構造へと変化する中で顕著になる Green Tea GCが解決したいこと 5
6. 従来のtri-color parallel marking キャッシュミス キャッシュミス オブジェクト単位の処理（局所性が悪い） ⽩: 未処理 灰: 処理中 ⿊: 処理済み 6
7. The core idea behind the new parallel marking algorithm is simple. Instead of scanning individual objects, the garbage collector scans memory in much larger, contiguous blocks. The shared work queue tracks these coarse blocks instead of individual objects, and the individual objects waiting to be scanned in a block are tracked in that block itself. — runtime: green tea garbage collector #73581 個々のオブジェクトではなく、大きな連続したブロック単位でメモリをスキャン 共有ワークキューは個々のオブジェクトではなくこれらの粗いブロックを追跡 Green Tea GCの基本概念 7
8. spanは常に8 KiBの倍数、8 KiBにアライン Green Tea GCのプロトタイプでは、small object spans（8 KiB、最大512バイトのオブジェク トを含む）を対象にしている 各spanには2ビット（gray bitとblack bit）を格納 gray bit: スキャン対象としてキューに入れられたかを示す black bit: スキャン済みかを示す spanの概念 8
9. 1. スキャンがオブジェクトへのポインタを見つけると、対象オブジェクトのgray bitを設定 2. そのspanが既にキューに入っていなければ、spanをキューに追加 3. GCがキューからスキャン対象のspanをデキュー 4. そのspanに対し、キューに入れられてから別のオブジェクトがマークされたかを示すヒット フラグを確認し、スキャンが必要なオブジェクトが複数ある可能性が高いか判断 5. i. ヒットフラグが設定されている場合、GCはspan全体を処理し、gray bitが設定されてい るがblack bitは設定されていないオブジェクト（gray状態）をスキャンし、gray bitを black bitにコピー（black状態に変換） ii. ヒットフラグが設定されていない場合、GCはspan全体ではなく、spanの代表オブジェ クトのみをスキャン Green Tea GCの動作 9
10. Green Tea GC Span 1 Span 2 Span 3 Span 4 Span1 を処理中 Span 単位の処理（局所性が良い） gray/black ビット ⽩: 未処理 灰: 処理中 ⿊: 処理済み 10
11. GC負荷の高いマイクロベンチマーク コア数に応じて10〜50％のGC CPU消費削減 コア数の増加とともにスケーラビリティが向上 L1/L2キャッシュミスが半減 実用ベンチマーク 多くのベンチマークで改善または変化なし。一部ではわずかな後退も tile38（地理空間データベース） ：35%のGCオーバーヘッド削減 ベンチマーク結果 11
12. 1. SIMDアクセラレーテッドスキャンカーネル より大きなメモリブロックでのスキャンにより SIMD 命令の活用が可能になる 小さなオブジェクト用に最適化されたスキャンカーネルを生成 プロトタイプでは既に追加で 15-20% の GC オーバーヘッド削減を実現 2. コンセントレータネットワーク SIMD スキャンに必要な高いポインタ密度を実現するソーティングネットワーク メタデータ操作にも局所性を生成 より汎用性が高く調整可能なアプローチとして今後の研究対象 今後の展望 12
13. gotipツールをインストール $ go install golang.org/dl/gotip@latest $ gotip download プログラムをGOEXPERIMENT=greenteagcを設定してgotipでビ ルド Green Tea GCの試し方 13
14. Green Tea GCはメモリの局所性を考慮した並列マーキングアル ゴリズム Go1.25で実験的に導入 詳細な設計はまだこれから提供される予定 まとめ 14