GoSuda

Goランタイムが奪い去るお茶一杯の安らぎ、GreenTea GC

By snowmerak
views ...

なぜまた新しいGCが登場するのか

既存のGCはなぜ

現在のGoのGCは、以下の言葉で説明できます。

  • concurrent tri-color mark and sweep
    • 合計3つの色（白、灰色、黒）を使用してオブジェクトの状態を追跡します。
      • 白：まだ訪問していないオブジェクト
      • 灰色：訪問したが、すべての子オブジェクトを訪問していないオブジェクト
      • 黒：すべての子オブジェクトを訪問したオブジェクト
      • 走査が終了すると、白いオブジェクトはすべて収集されます。
    • Write Barrierを使用して、GC中に新しく生成されるメモリを保護します。
      • Write BarrierのOn/Off時間は、一般的に言われるStop-The-World（以下STW）の大部分を占めます。
    • このプロセスを並行して実行します。
  • No Compaction
    • GoのGCはコンパクションを行いません。
    • メモリの断片化が発生する可能性があります。
      • しかし、32kb以下のオブジェクトは、Go言語のメモリ割り当て器（Allocator）のper-Pキャッシュを活用して断片化を最小限に抑えます。
  • Non-Generational
    • GoのGCは世代別にオブジェクトを管理しません。
    • すべてのオブジェクトは同じ世代に属します。
  • Escape Analysis
    • GoはEscape Analysisを通じて、オブジェクトがヒープに割り当てられるかスタックに割り当てられるかを決定します。
    • 大まかに言って、ダングリングポインタやインターフェースを使用する場合、ヒープに割り当てられると見なせます。

重要な点

GoのGCは、すべてのオブジェクトをルートから探索し、三色マークを実行するという点です。このプロセスを一行で書くと、「位相整列グラフ並行探索アルゴリズム」と言えます。しかし、各オブジェクトは異なるメモリ領域に存在する可能性が高いです。端的に言えば、

  1. 互いに約32MB離れたメモリ領域があるとします。
  2. この2つのメモリ領域にそれぞれ5つのオブジェクトが割り当てられています。
    1. オブジェクトA、B、Cは1番領域に
    2. オブジェクトD、Eは2番領域に
  3. オブジェクトの参照順序はA -> D -> B -> E -> Cです。
  4. GCが開始されると、Aを訪問し、Dを訪問し、Bを訪問し、Eを訪問し、Cを訪問します。
  5. この時、AとDは異なるメモリ領域に存在するため、Aを訪問してからDを訪問する過程でメモリ領域を移動する必要があります。
  6. この過程では、メモリ領域の移動や新しいキャッシュラインの充填など、いわゆるメモリジャンプコストが発生します。アプリケーションが使用するCPU時間の相当部分が、このようなGC作業に割り当てられる可能性があります。
  7. このコストはGCが進行している間、継続的に発生します。

では何が問題なのか？

このようなGCの動作は、以下のケースで非常に非効率です。

  • コア数が多く、メモリが大きい場合
    • GoのGCは基本的に並行して実行されます。
    • しかし、メモリ領域が広くオブジェクトが分散している場合、複数のコアが同時に様々なメモリ空間でオブジェクトを探索することになります。
    • この過程でCPUとメモリ間のバスが十分に大きくない場合、メモリ帯域幅がボトルネックになる可能性があります。
    • また、物理的に距離があるため、探索一つ一つが比較的大きな遅延となるでしょう。
  • 細かいオブジェクトが多い場合
    • もし、深さが深かったり、子が多いツリーやグラフをGoで運用している場合、GCはこれらのオブジェクトをすべて探索する必要があります。
    • この過程でオブジェクトが互いに異なるメモリ領域に分散している場合、最初の理由により遅延が発生します。
    • また、細かいオブジェクトが多い場合、GCはこれらのオブジェクトをすべて探索する必要があるため、GCが実行されている間、CPUコアはGCにかなりの能力を割り当てて作業することになるでしょう。

これらの問題を解決するために、GolangチームはGreenTea GCを発表しました。

あなたにもはや抹茶を飲む余裕はない

何が抹茶を奪うのか

既存のGCの最も迅速な解決策を適用できる領域として、メモリ局所性が注目されたようです。つまり、オブジェクトが互いに近くに位置するようにして、メモリジャンプを最小限に抑えることです。しかし、コードを書くプログラマのパターンを強制することはできず、またワークフローによってオブジェクトの割り当ては予測できません。

そのためか、Golangチームが選択した方法は**メモリ スパン(Memory Span)**です。

メモリ スパンとは？

メモリ スパンは、比較的大きなメモリ領域を割り当てられ、そこに小さなオブジェクトを割り当てる場所です。そして、GreenTea GCと名付けられた新しいGCは、このメモリ スパンに対してガベージコレクションを実行します。詳細な動作は既存のTri-Color Mark and Sweepとほぼ同じです。

GreenTea GCの動作

まず、GreenTea GCはメモリ スパンを割り当てます。サイズは前述の通り、ある程度の大きさがある8KiBです。そして、その中には最大512バイトのオブジェクトを割り当てることができます。まさに例に挙げたツリーやグラフのノードサイズ、あるいは一般的なヒープにエスケープする構造体のサイズがこれより大きくなることは考えにくい程度の大きさです。512バイト以下のオブジェクトは、ヒープにエスケープするたびにこのメモリ スパンに積まれ、このメモリ スパンがいっぱいになると新しいメモリ スパンを割り当てます。

GCが発生すると、GreenTea GCはこのメモリ スパンをキューに積んで順次検査します。この過程で、GreenTea GCは既存のGMPモデルとほぼ同様のスケジューリングを使用します。作業強奪のような領域も実装されています。とにかく、キューからメモリ スパンを取り出したワーカーは、自身に割り当てられたメモリ スパンの内部オブジェクトを検査します。この過程でTri-Color Mark and Sweepが同様に使用されます。

これにどんな利点が？

この過程で、既存のGCとの大きな違いはただ一つです。一度にGCを実行する単位がオブジェクトからメモリ スパンになったという点です。これにより、GCは以下の利点を得ます。

  • メモリ局所性：オブジェクトがメモリ スパンに集まっているため、オブジェクトを探索する際のメモリジャンプが最小化されます。つまり、CPUキャッシュを最大限に活用できます。
  • GC性能向上：メモリ スパン単位でGCを実行することで、GCがマルチコア環境でより効率的に動作します。
  • メモリ割り当て最適化：メモリ スパンは固定サイズで割り当てられるため、小さなオブジェクトを割り当てる際のメモリ割り当てのオーバーヘッドが減少し、断片化発生の可能性が低減します。これはメモリ割り当て解除の効率性を高めます。

簡単に言えば、これからは512バイト以下のオブジェクトを、より頻繁に、そして気軽に割り当てられるようになるということです。

ただし、ここにもある程度の有利な状況があります。

  • ツリー/グラフ構造：ファンアウトが高く、変更が頻繁に発生しない場合
    • B+ツリー、Trie、AST (Abstract Syntax Tree)
    • キャッシュ親和性の高いデータ構造
  • バッチ処理：小さなデータの大量割り当てワークフロー
    • JSONパースで生成される多数の小さなオブジェクト
    • データベース結果セットのDAOオブジェクト

これらの場合、GreenTea GCは既存のGCよりも優れた性能を発揮する可能性があります。しかし、すべてのケースに適用されるわけではなく、特にオブジェクトが互いに異なるメモリ領域に分散している場合は、依然として劇的な性能向上は期待しにくいです。

それで

Golangチームは、おそらく長期的にGCを改善し続ける意向があるようです。今回のGreenTea GCは、小さな領域におけるマイナーチェンジと見なすことができ、既存のGCを置き換えるものではありません。しかし、GreenTea GCはGolangチームが直面している、あるいは予想している問題を垣間見ることができる興味深い事例だと考えられます。意外と複雑な問題ですが、比較的簡単な概念の追加で解決しようとする試みも印象的でした。個人的には興味深い事例だと思います。

GreenTea GCはGo 1.25から導入される実験的機能です。GOEXPERIMENT=greenteagc環境変数を使用することで有効にして利用できます。この機能はまだ実験的なため、プロダクション環境で使用する前に十分なテストが必要です。

レファレンス