> Source: https://www.ymotongpoo.com/works/goblog-ja/greenteagc/


# Green Teaガベージコレクタ

[The Green Tea Garbage Collector](https://go.dev/blog/greenteagc) by Michael Knyszek and Austin Clements

Go 1.25には、Green Teaと呼ばれる新しい実験的なガベージコレクタが搭載されています。ビルド時に `GOEXPERIMENT=greenteagc` を設定することで有効にできます。多くのワークロードではガベージコレクタに費やす時間が約10%削減されますが、ワークロードによっては最大40%もの削減が見られることもあります。

すでにプロダクションレディであり、Google内でも利用されているので、ぜひ試してみてください。ワークロードによってはそれほど恩恵を受けない、あるいはまったく恩恵を受けないものもあることはわかっているので、みなさんのフィードバックは私たちが前に進むうえで非常に重要です。現時点で得られているデータに基づき、Go 1.26ではこれをデフォルトにする予定です。

問題を報告する場合は、[新しいIssueを作成](https://go.dev/issue/new)してください。

うまくいった場合は、[既存のGreen Tea Issue](https://go.dev/issue/73581)に返信してください。

以下の記事は、Michael KnyszekによるGopherCon 2025での講演をもとにしたものです。

[講演の動画(YouTube)](https://www.youtube.com/watch?v=gPJkM95KpKo)

## トレーシングガベージコレクション

Green Teaについて説明する前に、ガベージコレクションについて共通の理解を持っておきましょう。

### オブジェクトとポインタ

ガベージコレクションの目的は、プログラムがもはや使用していないメモリを自動的に回収し、再利用することです。

そのために、Goのガベージコレクタは_オブジェクト_と_ポインタ_を対象として扱います。

Goランタイムの文脈では、_オブジェクト_とは、その裏にあるメモリがヒープから確保されたGoの値のことです。ヒープオブジェクトは、Goコンパイラがある値に対してヒープ以外の方法でメモリを確保する方法を判断できない場合に作られます。たとえば、次のコードスニペットは1つのヒープオブジェクト、すなわちポインタのスライスの裏付けとなる配列(バッキングストア)を確保します。

```go
var x = make([]*int, 10) // グローバル変数
```

Goコンパイラは、`x` がそのオブジェクトをどれだけの期間参照し続けるかを知ることが非常に難しく、場合によっては不可能でもあるため、このスライスのバッキングストアをヒープ以外の場所に確保できません。

_ポインタ_とは、単にGoの値のメモリ上の位置を示す数値であり、Goプログラムがオブジェクトを参照する手段です。たとえば、直前のコードスニペットで確保したオブジェクトの先頭へのポインタを取得するには、次のように書けます。

```go
&x[0] // 0xc000104000
```

### マークスイープアルゴリズム

Goのガベージコレクタは、広く_トレーシングガベージコレクション_と呼ばれる方式に従っています。これは単に、ガベージコレクタがプログラム内のポインタをたどる(トレースする)ことで、プログラムがまだ使用しているオブジェクトを特定するという意味です。

より具体的に言うと、Goのガベージコレクタは_マークスイープアルゴリズム_を実装しています。これは聞こえるよりもずっと単純なものです。オブジェクトとポインタを、計算機科学的な意味でのグラフだと想像してください。オブジェクトがノードで、ポインタが辺です。

マークスイープアルゴリズムはこのグラフに対して動作し、その名前が示唆するとおり、2つのフェーズで進みます。

最初のフェーズである_マークフェーズ_では、_ルート_と呼ばれる明確に定義された起点となる辺からオブジェクトグラフをたどっていきます。グローバル変数やローカル変数を思い浮かべてください。そして、たどる過程で見つけたものをすべて_訪問済み_としてマークし、同じところをぐるぐる回らないようにします。これは、深さ優先探索や幅優先探索のような、典型的なグラフの塗りつぶし探索(以下「グラフフラッド」)アルゴリズムに似ています。

次は_スイープフェーズ_です。グラフの探索で訪問されなかったオブジェクトは、プログラムにとって未使用、すなわち_到達不能_です。この状態を到達不能と呼ぶのは、通常の安全なGoのコードでは、言語の意味論上、そのメモリに二度とアクセスできないからです。スイープフェーズを完了させるには、アルゴリズムは単に訪問されなかったすべてのノードを走査し、そのメモリを解放済みとしてマークするだけです。これにより、メモリアロケータがそのメモリを再利用できるようになります。

### 単純化の裏にあるもの

ここまでの説明は少し単純化しすぎだと思われるかもしれません。ガベージコレクタはしばしば_魔法_とか_ブラックボックス_などと呼ばれます。それはある意味で正しく、実際にはもっと複雑な部分があります。

たとえば、このアルゴリズムは実際には、通常のGoのコードと並行に実行されます。足元で変化し続けるグラフをたどるのは、それ自体が難題です。また私たちはこのアルゴリズムを並列化してもいますが、この点については後ほどまた触れます。

ですが、こうした詳細はアルゴリズムの核心部分とはほとんど切り離されているということを信じてください。中心にあるのは、本当にただの単純なグラフフラッドにすぎません。

### グラフフラッドの例

1つ例を見ていきましょう。以下は、その様子を1コマずつ順を追って示したものです。

![greenteagc-marksweep-007](./greenteagc/marksweep-007.png)

*ここには、いくつかのグローバル変数とGoのヒープの図があります。1つずつ、順番に見ていきましょう。*

![greenteagc-marksweep-008](./greenteagc/marksweep-008.png)

*左側にあるのが私たちのルートです。これらはグローバル変数 `x` と `y` です。これらがグラフ探索の起点になります。左下の凡例のとおり、青色でマークされているので、これらは現在ワークリストに入っています。*

![greenteagc-marksweep-009](./greenteagc/marksweep-009.png)

*右側にあるのが私たちのヒープです。現時点ではヒープ内のすべてがグレーアウトしています。まだ何も訪問していないからです。*

![greenteagc-marksweep-010](./greenteagc/marksweep-010.png)

*これらの四角形の1つ1つがオブジェクトを表しています。各オブジェクトにはその型がラベル付けされています。この特定のオブジェクトは型 `T` のオブジェクトであり、その型定義は左上にあります。子要素の配列へのポインタと、何らかの値を持っています。これは何らかの再帰的な木構造のデータ構造だと推測できます。*

![greenteagc-marksweep-011](./greenteagc/marksweep-011.png)

*型 `T` のオブジェクトに加えて、`*T` を格納する配列オブジェクトもあることに気づくでしょう。これらは型 `T` のオブジェクトの「children」フィールドから指されています。*

![greenteagc-marksweep-012](./greenteagc/marksweep-012.png)

*四角形の中の各マスは、8バイトのメモリを表しています。点が入ったマスはポインタです。矢印が付いていれば、それは何か別のオブジェクトを指すnilでないポインタです。*

![greenteagc-marksweep-013](./greenteagc/marksweep-013.png)

*そして対応する矢印がなければ、それはnilポインタです。*

![greenteagc-marksweep-014](./greenteagc/marksweep-014.png)

*次に、これらの点線の四角形は空き領域を表しており、ここでは空きの「スロット」と呼ぶことにします。そこにオブジェクトを置くこともできますが、現時点では何も置かれていません。*

![greenteagc-marksweep-015](./greenteagc/marksweep-015.png)

*また、オブジェクトがラベル付きの点線の角丸四角形によってグループ化されていることにも気づくでしょう。これらはそれぞれ_ページ_を表しており、ページとは固定サイズでアライメントされた連続したメモリブロックのことです。Goでは、(ハードウェアの仮想メモリのページサイズにかかわらず)ページは8KiBです。これらのページにはA、B、C、Dというラベルが付いており、以降もこの呼び方をします。*

![greenteagc-marksweep-015b](./greenteagc/marksweep-015.png)

*この図では、各オブジェクトはいずれかのページの一部として確保されています。実際の実装と同じく、ここでも各ページには特定のサイズのオブジェクトのみが含まれています。これは単に、Goのヒープがそのように構成されているということです。*

![greenteagc-marksweep-016](./greenteagc/marksweep-016.png)

*ページは、オブジェクトごとのメタデータを整理する単位でもあります。ここには7つのボックスがあり、それぞれがページAの7つのオブジェクトスロットの1つに対応しています。*

![greenteagc-marksweep-016b](./greenteagc/marksweep-016.png)

*各ボックスは1ビットの情報、すなわちそのオブジェクトを以前に見たことがあるかどうかを表しています。これは実際のランタイムがオブジェクトの訪問済みかどうかを管理する方法そのものであり、後ほど重要な詳細になります。*

![greenteagc-marksweep-017](./greenteagc/marksweep-017.png)

*ここまで多くの詳細を説明してきましたが、読み進めてくださりありがとうございます。これらはすべて後で活きてきます。ひとまず、この図に対して私たちのグラフフラッドがどう適用されるかを見てみましょう。*

![greenteagc-marksweep-018](./greenteagc/marksweep-018.png)

*まず、ワークリストからルートを1つ取り出します。それが現在アクティブであることを示すために、赤色でマークします。*

![greenteagc-marksweep-019](./greenteagc/marksweep-019.png)

*そのルートのポインタをたどると、型 `T` のオブジェクトが見つかるので、これをワークリストに追加します。凡例のとおり、ワークリストに入っていることを示すためにこのオブジェクトを青色で描きます。また、このオブジェクトに対応するメタデータ内のseenビットも立てていることに注目してください。*

![greenteagc-marksweep-020](./greenteagc/marksweep-020.png)

*次のルートについても同様です。*

![greenteagc-marksweep-021](./greenteagc/marksweep-021.png)

*すべてのルートを処理し終えたので、ワークリストには2つのオブジェクトが残りました。ワークリストからオブジェクトを1つ取り出してみましょう。*

![greenteagc-marksweep-022](./greenteagc/marksweep-022.png)

*ここから行うのは、オブジェクトのポインタをたどって、さらに多くのオブジェクトを見つけることです。ちなみに、オブジェクトのポインタをたどることを、そのオブジェクトを「スキャンする」と呼びます。*

![greenteagc-marksweep-023](./greenteagc/marksweep-023.png)

*この有効な配列オブジェクトが見つかりました……*

![greenteagc-marksweep-024](./greenteagc/marksweep-024.png)

*……そしてこれをワークリストに追加します。*

![greenteagc-marksweep-025](./greenteagc/marksweep-025.png)

*ここからは再帰的に処理を進めます。*

![greenteagc-marksweep-026](./greenteagc/marksweep-026.png)

*配列のポインタをたどります。*

![greenteagc-marksweep-027](./greenteagc/marksweep-027.png)

![greenteagc-marksweep-028](./greenteagc/marksweep-028.png)

![greenteagc-marksweep-029](./greenteagc/marksweep-029.png)

*さらにいくつかオブジェクトが見つかりました……*

![greenteagc-marksweep-030](./greenteagc/marksweep-030.png)

![greenteagc-marksweep-031](./greenteagc/marksweep-031.png)

![greenteagc-marksweep-032](./greenteagc/marksweep-032.png)

*続いて、その配列オブジェクトが参照していたオブジェクトをたどります！*

![greenteagc-marksweep-033](./greenteagc/marksweep-033.png)

*たとえnilであっても、すべてのポインタを走査しなければならないことに注意してください。事前にnilかどうかはわからないからです。*

![greenteagc-marksweep-034](./greenteagc/marksweep-034.png)

*この枝をもう1つたどると……*

![greenteagc-marksweep-035](./greenteagc/marksweep-035.png)

![greenteagc-marksweep-036](./greenteagc/marksweep-036.png)

*そしてここで、もう一方の枝にたどり着きました。これは、ずっと前にいずれかのルートから見つけた、ページA内のあのオブジェクトから始まる枝です。*

![greenteagc-marksweep-036b](./greenteagc/marksweep-036.png)

*ここまでで、私たちのワークリストが後入れ先出し(LIFO)の規律に従っていること、つまりワークリストがスタックであり、したがって私たちのグラフフラッドがおおよそ深さ優先であることに気づいたかもしれません。これは意図的なものであり、Goランタイムの実際のグラフフラッドアルゴリズムを反映しています。*

![greenteagc-marksweep-037](./greenteagc/marksweep-037.png)

*続けていきましょう……*

![greenteagc-marksweep-038](./greenteagc/marksweep-038.png)

*次に、別の配列オブジェクトが見つかりました……*

![greenteagc-marksweep-039](./greenteagc/marksweep-039.png)

*そしてそれをたどります……*

![greenteagc-marksweep-040](./greenteagc/marksweep-040.png)

![greenteagc-marksweep-041](./greenteagc/marksweep-041.png)

![greenteagc-marksweep-042](./greenteagc/marksweep-042.png)

![greenteagc-marksweep-043](./greenteagc/marksweep-043.png)

![greenteagc-marksweep-044](./greenteagc/marksweep-044.png)

*ワークリストに残っているのは、あと1つのオブジェクトだけです……*

![greenteagc-marksweep-045](./greenteagc/marksweep-045.png)

*それをスキャンしましょう……*

![greenteagc-marksweep-046](./greenteagc/marksweep-046.png)

![greenteagc-marksweep-047](./greenteagc/marksweep-047.png)

*これでマークフェーズは完了です！現在作業中のものは何もなく、ワークリストにも何も残っていません。黒で描かれたオブジェクトはすべて到達可能で、グレーで描かれたオブジェクトはすべて到達不能です。到達不能なオブジェクトを、まとめて一気にスイープしましょう。*

![greenteagc-marksweep-048](./greenteagc/marksweep-048.png)

*これらのオブジェクトを、新しいオブジェクトを格納できる空きスロットに変換しました。*

## 問題点

ここまでで、Goのガベージコレクタが実際に何をしているのか、大まかにつかめたと思います。この仕組みは今のところ十分にうまく機能しているように見えますが、では何が問題なのでしょうか。

実のところ、一部のプログラムではこのアルゴリズムの実行に_非常に多くの_時間を費やすことがあり、ほとんどすべてのGoプログラムにかなりのオーバーヘッドを追加してしまっています。GoプログラムがCPU時間の20%以上をガベージコレクタに費やしているのを目にすることも、それほど珍しくありません。

その時間がどこで消費されているのか、分解して見ていきましょう。

### ガベージコレクションのコスト

大まかに言うと、ガベージコレクタのコストは2つの要素からなります。1つはどれだけの頻度で実行されるか、もう1つは実行するたびにどれだけの作業をするかです。この2つを掛け合わせると、ガベージコレクタの総コストが得られます。

*GCの総コスト = GCサイクルの回数 × GC1サイクルあたりの平均コスト*

私たちはこれまで、この式の両方の項に取り組んできました。ガベージコレクタが_どれだけの頻度で_実行されるかについては、メモリ制限についてのMichaelによる[2022年のGopherCon EUでの講演](https://www.youtube.com/watch?v=07wduWyWx8M)を参照してください。[Goのガベージコレクタガイド](https://go.dev/doc/gc-guide)にもこの話題について詳しく書かれているので、さらに深く知りたい方は一読の価値があります。

ですが、ここでは2つめの要素、すなわち1サイクルあたりのコストにだけ注目しましょう。

長年にわたりパフォーマンス改善のためにCPUプロファイルを読み込んできた結果、Goのガベージコレクタについて2つの大きなことがわかっています。

1つめは、ガベージコレクタのコストのうち約90%がマーキングに費やされており、スイープに費やされるのは約10%に過ぎないということです。スイープはマーキングよりもずっと最適化しやすく、Goは長年にわたって非常に効率的なスイーパーを備えてきました。

2つめは、マーキングに費やされる時間のうち、かなりの部分、通常は少なくとも35%が、単にヒープメモリへのアクセスで_ストール_(停止)しているだけの時間だということです。これ自体だけでも十分に困りものですが、それに加えて、現代のCPUを実際に高速たらしめている仕組みを完全に台無しにしてしまいます。

### 「マイクロアーキテクチャ的な災害」

ここで言う「仕組みを台無しにする」とはどういう意味でしょうか。現代のCPUの詳細はかなり複雑になりがちなので、たとえ話を使いましょう。

CPUが道路を走っている様子を想像してください。その道路があなたのプログラムです。CPUは高速に加速したいのですが、そのためには前方を遠くまで見通せる必要があり、かつ道が空いている必要があります。しかし、グラフフラッドアルゴリズムは、CPUにとっては市街地の道路を走るようなものです。CPUは角の先を見ることができず、次に何が起こるかを予測することもできません。前に進むためには、絶えず速度を落として曲がり、信号で止まり、歩行者を避けなければなりません。エンジンがどれだけ速くても、加速するチャンスがまったく訪れないのですから、ほとんど意味がありません。

先ほどの例をもう一度見て、これをもっと具体的にしてみましょう。ここではヒープの上に、私たちがたどった経路を重ねて描いています。左から右への矢印はそれぞれ、私たちが行ったスキャン作業の一片を表しており、破線の矢印は、スキャン作業の断片同士の間をどのように飛び回ったかを示しています。

![greenteagc-graphflood-path](./greenteagc/graphflood-path.png)

*私たちのグラフフラッドの例で、ガベージコレクタがヒープ内をたどった経路。*

あちこちのメモリに飛び回りながら、それぞれの場所でごく小さな作業をしていたことに注目してください。特に、ページとページの間、そしてページ内の異なる部分の間を頻繁に飛び越えています。

現代のCPUは多くのキャッシュを利用します。メインメモリへのアクセスは、キャッシュ内のメモリへのアクセスに比べて最大で100倍も遅くなることがあります。CPUキャッシュには、最近アクセスされたメモリと、そのメモリの近くにあるメモリが取り込まれます。しかし、互いを指し合う2つのオブジェクトが、メモリ上でも近くに配置されているという保証はどこにもありません。グラフフラッドはこの点を考慮していません。

少し余談ですが、単にメインメモリへのフェッチでストールしているだけなら、それほど悪くはなかったかもしれません。CPUはメモリリクエストを非同期に発行するため、たとえ遅いリクエストであっても、CPUが十分先まで見通せるのであれば重ね合わせることができます。しかし、グラフフラッドでは、あらゆる作業の単位が小さく、予測不能で、かつ直前の作業に強く依存しているため、CPUはほとんどすべての個々のメモリフェッチについて待たされることを強いられます。

そして残念なことに、この問題は悪化する一方です。業界には「2年待てばコードは速くなる」ということわざがあります。

しかし、マークスイープアルゴリズムに依存するガベージコレクション言語であるGoは、その逆のリスクを抱えています。「2年待てばコードは遅くなる」のです。現代のCPUハードウェアのトレンドは、ガベージコレクタの性能にとって新たな課題を生み出しています。

**非一様メモリアクセス。** まず、今日ではメモリはCPUコアの部分集合に紐づく傾向があります。そのメモリに対する_他の_CPUコアからのアクセスは、以前よりも遅くなります。つまり、メインメモリへのアクセスのコストは、[どのCPUコアがアクセスしているかに依存する](https://jprahman.substack.com/p/sapphire-rapids-core-to-core-latency)ようになっているのです。これは一様ではないため、非一様メモリアクセス、略してNUMAと呼ばれます。

**メモリ帯域幅の低下。** CPUあたりで利用可能なメモリ帯域幅は、時間とともに低下する傾向にあります。これは単に、CPUコアの数は増えているものの、各コアがメインメモリに送信できるリクエストの数は相対的に少なくなり、キャッシュされていないリクエストは以前より長く待たされるようになっている、ということを意味します。

**増え続けるCPUコア数。** ここまでは逐次的なマーキングアルゴリズムを見てきましたが、実際のガベージコレクタはこのアルゴリズムを並列に実行します。これは限られた数のCPUコアまでは十分にスケールしますが、どれだけ注意深く設計しても、スキャン対象のオブジェクトを保持する共有キューがボトルネックになってしまいます。

**現代的なハードウェア機能。** 新しいハードウェアには、一度に大量のデータを操作できるベクトル命令のような凝った機能があります。これには大きな高速化の可能性がありますが、マーキングはこれほど不規則で、多くの場合小さな作業の集まりであるため、それをマーキングにどう活かせばよいのかは、すぐにはわかりません。

## Green Tea

ようやく、Green Teaの話にたどり着きました。これは、マークスイープアルゴリズムに対する私たちの新しいアプローチです。Green Teaの背後にある鍵となるアイデアは、驚くほど単純です。

_オブジェクトではなく、ページを単位として扱う。_

当たり前のことのように聞こえますよね？それでも、オブジェクトグラフの探索をどのような順序で行うか、そしてこれを実際にうまく機能させるために何を追跡する必要があるかを解明するには、多くの作業が必要でした。

より具体的には、これは次のようなことを意味します。

* オブジェクトをスキャンする代わりに、ページ全体をスキャンする。
* ワークリストで追跡する対象を、オブジェクトではなくページ全体にする。
* 最終的にはオブジェクトをマークする必要があるが、マーク済みのオブジェクトは、ヒープ全体を通してではなく、各ページに局所的に追跡する。

### Green Teaの例

これが実際に何を意味するのか、もう一度同じ例のヒープを見ながら確認しましょう。ただし今度は、単純なグラフフラッドの代わりにGreen Teaを実行します。

先ほどと同様に、注釈付きの1コマずつの説明を見ながら読み進めてください。

![greenteagc-greentea-060a](./greenteagc/greentea-060.png)

*これは先ほどと同じヒープですが、今回はオブジェクトごとのメタデータが1ビットではなく2ビットになっています。ここでも、各ビット(ボックス)はページ内のいずれかのオブジェクトスロットに対応しています。全体として、ページAの7つのスロットに対応する14個のビットがあることになります。*

![greenteagc-greentea-060b](./greenteagc/greentea-060.png)

*上のビット集合は先ほどと同じもの、すなわちそのオブジェクトへのポインタを見たかどうかを表します。これを「seen」ビットと呼びます。下のビット集合は新しいものです。この「scanned」ビットは、そのオブジェクトをスキャンしたかどうかを追跡します。*

![greenteagc-greentea-060c](./greenteagc/greentea-060.png)

*この新しいメタデータが必要なのは、Green Teaではワークリストがオブジェクトではなくページを追跡するからです。それでもどこかのレベルではオブジェクトを追跡する必要があり、それがこれらのビットの役割です。*

![greenteagc-greentea-062](./greenteagc/greentea-062.png)

*先ほどと同様に、ルートからオブジェクトをたどるところから始めます。*

![greenteagc-greentea-063](./greenteagc/greentea-063.png)

![greenteagc-greentea-064](./greenteagc/greentea-064.png)

*ですが今回は、オブジェクトをワークリストに置く代わりに、ページ全体(この場合はページA)をワークリストに置きます。これは、ページ全体を青色で塗ることで示されています。*

![greenteagc-greentea-066](./greenteagc/greentea-066.png)

*見つかったオブジェクトも青色になっています。これは、このページをワークリストから取り出したときに、そのオブジェクトを見る必要があることを示しています。このオブジェクトの青みは、ページA内のメタデータをそのまま反映していることに注目してください。対応するseenビットは立っていますが、scannedビットは立っていません。*

![greenteagc-greentea-069](./greenteagc/greentea-069.png)

*次のルートをたどると、別のオブジェクトが見つかるので、再びページ全体(今度はページC)をワークリストに置き、そのオブジェクトのseenビットを立てます。*

![greenteagc-greentea-071](./greenteagc/greentea-071.png)

*ルートをたどり終えたので、ワークリストに目を向け、ページAをワークリストから取り出します。*

![greenteagc-greentea-072](./greenteagc/greentea-072.png)

*seenビットとscannedビットを使うことで、ページAにはスキャンすべきオブジェクトが1つあることがわかります。*

![greenteagc-greentea-074](./greenteagc/greentea-074.png)

*そのオブジェクトをスキャンし、そのポインタをたどります。その結果、ページA内の最初のオブジェクトがページB内のオブジェクトを指しているため、ページBをワークリストに追加します。*

![greenteagc-greentea-075](./greenteagc/greentea-075.png)

*ページAの処理は完了です。次にページCをワークリストから取り出します。*

![greenteagc-greentea-076](./greenteagc/greentea-076.png)

*ページAと同様に、ページCにもスキャンすべきオブジェクトが1つあります。*

![greenteagc-greentea-078](./greenteagc/greentea-078.png)

*ページB内の別のオブジェクトへのポインタが見つかりました。ページBはすでにワークリストに入っているため、ワークリストに何かを追加する必要はありません。対象のオブジェクトのseenビットを立てるだけで済みます。*

![greenteagc-greentea-079](./greenteagc/greentea-079.png)

*今度はページBの番です。ページBにはスキャンすべきオブジェクトが2つ蓄積されており、この2つのオブジェクトをメモリ上の並び順で連続して処理できます！*

![greenteagc-greentea-081](./greenteagc/greentea-081.png)

*最初のオブジェクトのポインタをたどります……*

![greenteagc-greentea-082](./greenteagc/greentea-082.png)

![greenteagc-greentea-083](./greenteagc/greentea-083.png)

![greenteagc-greentea-084](./greenteagc/greentea-084.png)

*ページA内のオブジェクトへのポインタが見つかりました。ページAは以前ワークリストに入っていましたが、現時点では入っていないため、再びワークリストに戻します。元のマークスイープアルゴリズムでは、あるオブジェクトがマークフェーズ全体を通して高々1回しかワークリストに追加されなかったのに対し、Green Teaでは、あるページがマークフェーズの中で複数回ワークリストに再登場することがあります。*

![greenteagc-greentea-085](./greenteagc/greentea-085.png)

![greenteagc-greentea-086](./greenteagc/greentea-086.png)

*最初のオブジェクトの直後に、そのページで2番目にseen状態になっているオブジェクトをスキャンします。*

![greenteagc-greentea-087](./greenteagc/greentea-087.png)

![greenteagc-greentea-088](./greenteagc/greentea-088.png)

![greenteagc-greentea-089](./greenteagc/greentea-089.png)

*ページAでさらにいくつかのオブジェクトが見つかりました……*

![greenteagc-greentea-090](./greenteagc/greentea-090.png)

![greenteagc-greentea-091](./greenteagc/greentea-091.png)

![greenteagc-greentea-092](./greenteagc/greentea-092.png)

![greenteagc-greentea-093](./greenteagc/greentea-093.png)

*ページBのスキャンが完了したので、ページAをワークリストから取り出します。*

![greenteagc-greentea-094](./greenteagc/greentea-094.png)

*最初のオブジェクトはすでにスキャン済みなので、今回スキャンする必要があるのは4つではなく3つのオブジェクトだけです。「seen」ビットと「scanned」ビットの差分を見ることで、どのオブジェクトをスキャンすべきかがわかります。*

![greenteagc-greentea-095](./greenteagc/greentea-095.png)

*これらのオブジェクトを順番にスキャンしていきます。*

![greenteagc-greentea-096](./greenteagc/greentea-096.png)

![greenteagc-greentea-097](./greenteagc/greentea-097.png)

![greenteagc-greentea-098](./greenteagc/greentea-098.png)

![greenteagc-greentea-099](./greenteagc/greentea-099.png)

![greenteagc-greentea-100](./greenteagc/greentea-100.png)

![greenteagc-greentea-101a](./greenteagc/greentea-101.png)

*完了です！ワークリストにはもうページが残っておらず、現在着目しているものもありません。到達可能なすべてのオブジェクトがseenかつscanned状態になったことで、メタデータがきれいに揃っていることに注目してください。*

![greenteagc-greentea-101b](./greenteagc/greentea-101.png)

*また、この探索の間に、ワークリストの順序がグラフフラッドとは少し違うことに気づいたかもしれません。グラフフラッドでは後入れ先出し、すなわちスタック的な順序だったのに対し、ここではワークリスト上のページに対して先入れ先出し、すなわちキュー的な順序を使っています。*

![greenteagc-greentea-101c](./greenteagc/greentea-101.png)

*これは意図的なものです。ページがキューに入っている間に、seen状態のオブジェクトを各ページ上に蓄積させておくことで、できる限り多くをまとめて処理できるようにしています。これが、ページAで一度にあれほど多くのオブジェクトを処理できた理由です。時には、怠けることも美徳なのです。*

![greenteagc-greentea-102](./greenteagc/greentea-102.png)

*そして最後に、先ほどと同様に、未訪問のオブジェクトをスイープして片付けます。*

### ハイウェイに乗る

運転のたとえ話に戻りましょう。私たちはついにハイウェイに乗れたのでしょうか？

先ほどのグラフフラッドの図を思い出してみましょう。

![greenteagc-graphflood-path2](./greenteagc/graphflood-path2.png)

*元のグラフフラッドがヒープ内でたどった経路では、7回の別々のスキャンが必要でした。*

あちこちに飛び回りながら、いろいろな場所で小さな作業をしていました。Green Teaがたどる経路は、これとはまったく異なって見えます。

![greenteagc-greentea-path](./greenteagc/greentea-path.png)

*Green Teaがたどる経路では、わずか4回のスキャンで済みます。*

対照的に、Green Teaはページ AとBに対して、より少ない回数の、より長い左から右へのパスを行います。この矢印が長ければ長いほどよく、ヒープが大きくなればなるほど、この効果はさらに強くなります。_それ_こそが、Green Teaの魔法です。

そしてこれこそが、ハイウェイに乗るチャンスでもあります。

これらすべてが積み重なって、マイクロアーキテクチャとの相性が向上します。近くにあるオブジェクトをはるかに高い確率で連続してスキャンできるようになるため、キャッシュを活用してメインメモリへのアクセスを避けられる可能性が高まります。同様に、ページごとのメタデータもキャッシュに乗りやすくなります。オブジェクトではなくページを追跡することで、ワークリストは小さくなり、ワークリストへの負荷が減ることで競合が減り、CPUのストールも減少します。

そしてハイウェイと言えば、これまでにない高いギアに、比喩的なエンジンを入れることができるようになります。というのも、ここでついにベクトルハードウェアを活用できるようになるからです！

### ベクトルによる高速化

ベクトルハードウェアについてぼんやりとしか知らない方は、ここでそれをどう使うのか戸惑うかもしれません。しかし、通常の算術演算や三角関数演算に加えて、最近のベクトルハードウェアはGreen Teaにとって価値のある2つの機能をサポートしています。非常に幅の広いレジスタと、高度なビット単位の演算です。

最近のx86 CPUの多くはAVX-512をサポートしており、512ビット幅のベクトルレジスタを備えています。これは、ページ全体分のメタデータを、CPU上のわずか2つのレジスタにすべて収められるほどの幅であり、Green Teaがページ全体を、わずか数個の直線的な命令列だけで処理できるようにしてくれます。ベクトルハードウェアは以前から、ベクトルレジスタ全体に対する基本的なビット単位演算をサポートしていましたが、AMD Zen 4とIntel Ice Lake以降では、Green Teaのスキャン処理の重要な一歩をわずか数CPUサイクルで実行できるようにする、新しいビットベクトルの「万能ナイフ」的命令もサポートされています。これらが組み合わさることで、Green Teaのスキャンループをターボチャージできます。

これは、グラフフラッドではそもそも選択肢にすらなり得ませんでした。グラフフラッドでは、あらゆる大きさのオブジェクトのスキャンの間を飛び回ることになるからです。必要なメタデータが2ビットで済むこともあれば、1万ビット必要なこともありました。ベクトルハードウェアを使うために必要な予測可能性や規則性が、単純に足りていなかったのです。

細かい部分までオタク気質全開で読みたい方は、このまま読み進めてください！そうでない方は、遠慮なく後述の「評価」まで読み飛ばしてください。

#### AVX-512スキャンカーネル

AVX-512によるGCスキャンがどのようなものか感覚をつかむために、以下の図を見てみましょう。

![greenteagc-avx512](./greenteagc/avx512.svg)

*スキャン用のAVX-512ベクトルカーネル。*

ここには多くの要素が詰まっており、この仕組みだけでブログ記事1本分になってしまうかもしれません。ここでは、大まかなレベルで分解してみましょう。

1. まず、あるページの「seen」ビットと「scanned」ビットを取得します。これらはページ内のオブジェクト1個につき1ビットであり、1つのページ内のオブジェクトはすべて同じサイズであったことを思い出してください。

2. 次に、この2つのビット集合を比較します。両者の和集合が新しい「scanned」ビットとなり、両者の差分が「アクティブオブジェクト」ビットマップとなります。このビットマップは、(これまでのパスと比較して)今回のページに対するパスでスキャンする必要があるオブジェクトを教えてくれます。

3. このビットマップの差分を取り、それを「展開」することで、オブジェクト1個につき1ビットだったものを、ページ内のワード(8バイト)1個につき1ビットに変換します。これを「アクティブワード」ビットマップと呼びます。たとえば、ページが6ワード(48バイト)のオブジェクトを格納している場合、アクティブオブジェクトビットマップの各ビットは、アクティブワードビットマップの6ビットにコピーされます。次のようにです。

   ```
   0 0 1 1 ...  →  000000 000000 111111 111111 ...
   ```

4. 次に、ページのポインタ/スカラービットマップを取得します。ここでも、各ビットはページ内のワード(8バイト)に対応しており、そのワードがポインタを格納しているかどうかを示します。このデータはメモリアロケータによって管理されています。

5. 続いて、ポインタ/スカラービットマップとアクティブワードビットマップの共通部分を取ります。結果として得られるのが「アクティブポインタ」ビットマップです。これは、まだスキャンしていない生きているオブジェクトに含まれる、ページ全体の中のすべてのポインタの位置を教えてくれるビットマップです。

6. 最後に、ページのメモリを走査してすべてのポインタを収集します。論理的には、アクティブポインタビットマップの中で立っているビットをそれぞれたどり、そのワードにあるポインタの値をロードし、それを後でオブジェクトをseen済みとしてマークしたりページをワークリストに追加したりするために使うバッファに書き戻します。ベクトル命令を使うことで、これを一度に64バイトずつ、わずか数個の命令で行うことができます。

これが高速である理由の一端は、x86拡張命令セット「Galois Field New Instructions」の一部である `VGF2P8AFFINEQB` 命令にあります。これが、先ほど触れたビット操作の「万能ナイフ」です。これこそがこの仕組みの真の主役であり、スキャンカーネルのステップ(3)を非常に、非常に効率的に行うことを可能にしてくれます。この命令はビット単位の[アフィン変換](https://en.wikipedia.org/wiki/Affine_transformation)を行うもので、ベクトル内の各バイトをそれ自体8ビットの数学的なベクトルとみなし、それを8×8のビット行列と掛け合わせます。これはすべて[ガロア体](https://en.wikipedia.org/wiki/Finite_field) `GF(2)` 上で行われ、これは単に乗算がAND、加算がXORになるということを意味します。この結果として、私たちはオブジェクトサイズごとに、必要とする1対nのビット展開をちょうど実現するいくつかの8×8ビット行列を定義できるのです。

アセンブリコード全体については、[このファイル](https://cs.opensource.google/go/go/+/master:src/internal/runtime/gc/scan/scan_amd64.s;l=23;drc=041f564b3e6fa3f4af13a01b94db14c1ee8a42e0)を参照してください。「エキスパンダー」はサイズクラスごとに異なる行列と異なる並べ替えを使用するため、[コードジェネレータ](https://cs.opensource.google/go/go/+/master:src/internal/runtime/gc/scan/mkasm.go;drc=041f564b3e6fa3f4af13a01b94db14c1ee8a42e0)によって生成される[別のファイル](https://cs.opensource.google/go/go/+/master:src/internal/runtime/gc/scan/expand_amd64.s;drc=041f564b3e6fa3f4af13a01b94db14c1ee8a42e0)に置かれています。展開関数を除けば、実際のところコード量はそれほど多くありません。上記の演算のほとんどをレジスタ上だけに存在するデータに対して行えるという事実によって、コードの大部分が劇的に単純化されています。そして、このアセンブリコードも近いうちに[Goのコードに置き換えられる](https://go.dev/issue/73787)ことを期待しています！

この仕組みを考案したAustin Clementsに感謝します。信じられないほどクールで、信じられないほど高速です！

### 評価

仕組みについての説明はここまでです。では、実際にどれだけ効果があるのでしょうか。

かなり大きな効果があり得ます。ベクトルによる強化を行わなくても、私たちのベンチマークスイートでは、ガベージコレクションのCPUコストが10%から40%削減されています。たとえば、あるアプリケーションが実行時間の10%をガベージコレクタに費やしている場合、ワークロードの詳細にもよりますが、これは全体のCPU使用量にして1%から4%の削減に相当します。ガベージコレクションのCPU時間が10%削減されるというのが、おおよその最頻値としての改善幅です。(この詳細の一部については[GitHubのIssue](https://go.dev/issue/73581)を参照してください。)

私たちはGreen TeaをGoogle社内にも展開しており、大規模な環境でも同様の結果が得られています。

ベクトルによる強化についてはまだ展開の途中ですが、ベンチマークと初期の結果からは、これによってさらに10%のGC CPU時間削減が見込めることが示唆されています。

ほとんどのワークロードは何らかの恩恵を受けますが、中にはそうでないものもあります。

Green Teaは、蓄積処理にかかるコストを相殺できるだけの十分な数のオブジェクトを、1回のパスで1つのページ上に蓄積できるという仮説に基づいています。これは、ヒープが非常に規則的な構造、すなわちオブジェクトグラフの中で似たような深さにある同じサイズのオブジェクトを持つ場合には、明らかに当てはまります。しかし、ワークロードの中には、1度に1ページあたり1つのオブジェクトしかスキャンできないことが多いものもあります。この場合、ページ上にオブジェクトを蓄積しようとして失敗し続けることで、以前より多くの作業をしてしまう可能性があるため、グラフフラッドよりも悪化する可能性があります。

Green Teaの実装には、スキャンすべきオブジェクトが1つしかないページのための特別なケースが用意されています。これによって性能低下はある程度抑えられますが、完全になくなるわけではありません。

しかし、グラフフラッドを上回る性能を出すために必要なページごとの蓄積量は、想像よりもずっと少なくて済みます。この作業で得られた驚くべき結果の1つは、一度にページのわずか2%をスキャンするだけでも、グラフフラッドに対する改善が得られるということでした。

### 利用方法

Green Teaは、最近リリースされたGo 1.25にすでに実験的機能として搭載されており、ビルド時に環境変数 `GOEXPERIMENT` を `greenteagc` に設定することで有効化できます。ここには、前述のベクトルによる高速化は含まれていません。

Go 1.26ではこれをデフォルトのガベージコレクタにする予定ですが、ビルド時に `GOEXPERIMENT=nogreenteagc` を指定することで、引き続きオプトアウトすることも可能です。Go 1.26では、より新しいx86ハードウェア向けのベクトルによる高速化も追加されるほか、これまでに集めたフィードバックに基づく数多くの調整や改善も含まれる予定です。

可能であれば、Goの開発ブランチの最新版(tip-of-tree)でぜひ試してみてください！Go 1.25を使い続けたい方でも、フィードバックは大歓迎です。共有していただけるのであれば私たちが見たいと考えている診断情報の詳細や、フィードバックを報告するのに望ましい方法について、[こちらのGitHubコメント](https://go.dev/issue/73581#issuecomment-2847696497)を参照してください。

## これまでの道のり

この記事を締めくくる前に、少し時間を取って、ここに至るまでの道のりについてお話しさせてください。この技術の人間的な側面についてです。

Green Teaの核心は、たった1つの単純なアイデアのように見えるかもしれません。まるで、たった1人がひらめいたひとつの閃きであるかのように。

しかし、それはまったくの誤りです。Green Teaは、何年にもわたる多くの人々の作業とアイデアの結晶です。Michael Pratt、Cherry Mui、David Chase、Keith Randallをはじめとする、Goチームの複数のメンバーがアイデアに貢献しました。当時Intelに在籍していたYves Vandriesscheによるマイクロアーキテクチャに関する洞察も、設計の探索の方向性を定めるうえで大いに役立ちました。うまくいかなかったアイデアもたくさんありましたし、詰めなければならない詳細もたくさんありました。それもすべて、このたった1つの単純なアイデアを実現可能にするためだけにです。

![greenteagc-timeline](./greenteagc/timeline.png)

*今日にたどり着くまでにこの方向性で試してきたアイデアの一部を示したタイムライン。*

このアイデアの種は、はるか2018年にまでさかのぼります。面白いことに、チームの誰もが、この最初のアイデアを思いついたのは自分ではなく誰か他の人だと思っています。

Green Teaという名前が付いたのは2024年のことで、Austinが日本でカフェ巡りをしながら大量の抹茶を飲んでいたときに、初期バージョンのプロトタイプを作り上げたのがきっかけでした！このプロトタイプによって、Green Teaの核心となるアイデアが実現可能であることが示されました。そしてそこから、私たちは一気に加速していきました。

2025年を通して、MichaelがGreen Teaを実装し、プロダクション品質に仕上げていく中で、アイデアはさらに進化し、変化していきました。

これほど多くの共同での探索が必要だったのは、Green Teaが単なるアルゴリズムではなく、1つの設計空間全体だからです。私たちの誰か1人だけでは、とても乗り越えられなかっただろうと思っています。アイデアを持っているだけでは十分ではなく、その詳細を詰め、それを証明する必要があります。そして今、それをやり遂げたことで、ようやく私たちは反復改善を進めることができます。

Green Teaの未来は明るいものです。

改めて、`GOEXPERIMENT=greenteagc` を設定してぜひ試してみてください。そしてその結果をぜひ教えてください！私たちはこの成果にとてもわくわくしていますし、みなさんの声を聞きたいと思っています！

By Michael Knyszek and Austin Clements