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はコンパクション(compaction)を行いません。
    • メモリの断片化が発生する可能性があります。
      • しかし32KB以下のオブジェクトは、Goのメモリアロケータ(Allocator)のper-Pキャッシュを活用して断片化を最小限に抑えます。
  • Non-Generational
    • GoのGCはオブジェクトを世代別に管理しません。
    • すべてのオブジェクトは同一の世代に属します。
  • Escape Analysis
    • Goは Escape Analysis によって、オブジェクトがヒープに割り当てられるか、スタックに割り当てられるかを決定します。
    • 大まかに言えば、ダングリングポインタやインターフェースを使用する場合はヒープに割り当てられるとみなせます。

重要なのは

GoのGCは、すべてのオブジェクトをルートから探索しながらtri-color markを実行するという点です。この過程を一行で書くと位相順序グラフの並行探索アルゴリズムと言えます。しかし、各オブジェクトは互いに異なるメモリ領域に存在する可能性が高いのです。端的に言うと、

  1. 互いに32MB ほど離れた距離にあるメモリ領域があるとしましょう。
  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に割り当てて作業することになります。

こうした問題を解決するために、Goチームは GreenTea GC を発表しました。

あなたにはもう緑茶を飲む余裕はない

何が緑茶を奪うのか

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

そのためか、Goチームが選択した方法は メモリスパン(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バイト以下のオブジェクトを、より頻繁に、そして気軽に割り当てられるということです。

ただし、ここにもある程度有利な区間があります。

  • ツリー/グラフ構造: fan-outが高く、変更がほとんど起きない場合
    • B+ツリー、Trie、AST (Abstract Syntax Tree)
    • キャッシュ親和的なデータ構造
  • バッチ処理: 小さなデータの大量割り当てワークフロー
    • JSONパースによって生成される多数の小さなオブジェクト
    • データベースの結果セットのDAOオブジェクト群

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

それで

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

GreenTea GCは Go 1.25 から導入される実験的機能です。GOEXPERIMENT=greenteagc 環境変数を設定することで有効化して使用できます。この機能はまだ実験的であるため、本番環境で使用する前に十分なテストが必要です。

参考文献