GC25 Recap+: Advancing Go Garbage Collection with Green Tea

Transcript

Takuto Nagami @logica0419 Recap+: Advancing Go Garbage Collection with Green

Tea

今回Recapするのは… Advancing Go Garbage Collection with Green Tea by Michael

Knyszek

要約 (TL;DR): Go 1.26からガベージコレクションが速くなります。

本題に入る前に前提知識をおさらいしておきましょう

スタック・ヒープとガベージコレクション

アプリケーションから見たメモリ . . . • Key-value storeの形で表される ◦ Key: Memory

address ◦ Value: 各アドレス1バイト • ほとんどの高級言語は、変数をメモリに格納する時、スタックとヒープの2つの領域を(言語側で作って)使い分ける 0x0000 0x0001 0x0002 0x0003

. . . スタック

. . . main() stack frame スタック

. . . main() stack frame 5 スタック {v addr}

. . . main() stack frame 5 a() stack frame

スタック {v addr}

. . . main() stack frame 5 a() stack frame

5 スタック {arg addr} {v addr}

. . . main() stack frame 5 a() stack frame

5 7 スタック {arg addr} {a addr} {v addr}

. . スタック main() stack frame 5 a() stack frame

{arg addr} {a addr} {v addr} 5 7 b() stack frame

. . スタック main() stack frame 5 a() stack frame

{arg addr} {arg addr} {a addr} {v addr} 5 7 b() stack frame 7

. . スタック main() stack frame 5 a() stack frame

{arg addr} {b addr} {arg addr} {a addr} {v addr} 5 7 b() stack frame 7 1

. . . スタック main() stack frame 5 a() stack

frame {arg addr} {a addr} {v addr} 5 7

. . . スタック main() stack frame 5 {v addr}

. . . スタックプログラム終了

スタックが苦手なデータ • 大きなデータ ◦ Stack Overﬂowを誘発する • コンパイル時にサイズが決まらないデータ ◦ slice・mapなど

◦ スタックはコンパイル時に全て定義される ▪ 動的にサイズを変えるのは効率が悪い • 複数の関数でまたがって使うデータ ◦ グローバル変数など

ヒープ . . . . . . . main() stack

frame

ヒープ . . . . . . . [] {slice_h

addr} main() stack frame

. . . . . . . [] {slice_h addr}

{slice addr} main() stack frame ヒープ {slice_h addr}

ヒープ内でのオブジェクト管理 • 色んなデータ(オブジェクト)がヒープに入る ◦ バラバラに入れていたら管理が面倒 int (8 byte) struct (可変サイズ)

ポインタ (8 byte)

… … ヒープ内でのオブジェクト管理 • 同サイズのオブジェクトをスパンでまとめる int (8 byte) struct (8

byte) struct struct (32 byte) struct struct int int スパン1 (8 byte用) スパン2 (8 byte用) スパン3 (32 byte用) int int

ヒープ内でのオブジェクト管理 • スパン(mspan)はもっと大きな単位でまとめられる ◦ mcentral ▪ 同じサイズのスパンをグループ化 ◦ arena ▪

mheapが1回で引き出してくるメモリ量 ▪ mcentralを複数格納 ◦ mheap ▪ ヒープ本体

ガベージコレクション(GC) • Cなどでは、ヒープに置いたデータを使わなくなった時プログラマーが明示的に削除 ◦ 削除忘れによってメモリ使用量が無限に増える memory leakが多発 ↓ •

要らなくなったヒープ内のデータを自動的に削除する機能がガベージコレクション

これまでのGCとその挙動

GoのGC • Mark and Sweepアルゴリズム ◦ Mark phase: まだ使われているオブジェクトを確認 ◦

Sweep phase: マークされていない物を削除 • Tri-color markingを使うことで中断可能に ◦ 詳しいことは今回割愛 • 色々頑張ってアプリケーションと並列で実行 ◦ 今回割愛

スタック var x T var y T 状態一覧見てない見る予定

今見てるもう見たスパンA スパンB スパンC スパンD T T T T T T [4]*T [4]*T [4]*T

スタック var x T var y T 状態一覧見てない見る予定

今見てるもう見たスパンA スパンB スパンC スパンD T T T T T T [4]*T [4]*T [4]*T ここから、Tri-color markingの root scan phase

スタック var x T var y T 状態一覧見てない見る予定

今見てるもう見たスパンA スパンB スパンC スパンD T T T T T T [4]*T [4]*T [4]*T ここから、Tri-color markingの mark phase

スタック var x T var y T 状態一覧見てない見る予定

今見てるもう見たスパンA スパンB スパンC スパンD T T T T T T [4]*T [4]*T [4]*T ここから sweep phase

スタック var x T var y T 状態一覧見てない見る予定

今見てるもう見たスパンA スパンB スパンC スパンD T T T T T [4]*T [4]*T

メモリ局所性と OSのメモリ読み込み戦略

メモリ局所性(参照の局所性)とは • データアクセスの傾向に関する概念 • 時間的局所性 ◦ 同じデータには近いうちに再度アクセスされやすい • 空間的局所性 ◦

近い場所にあるデータは一緒にアクセスされやすい • ↑ のような傾向が強いと「局所性が高い」 • 世の中のタスクのほとんどは局所性が高いので、OSはそれに合わせて最適化している

OSのメモリ読み込み戦略 • 多段キャッシュをする ◦ CPUの処理部に近づくほど、小さく速い • この構造を活かすための読み込み戦略が… CPU内キャッシュ (多段)

メモリ (DRAM) ストレージ小さくて速い大きくて遅い

OSのメモリ読み込み戦略 • ページングを行うメモリページ1 (4 kB) ページ2 (4 kB)

ページ3 (4 kB) CPU キャッシュ CPU 処理部

OSのメモリ読み込み戦略 • ページングを行うメモリページ1 (4 kB) ページ2 (4 kB)

ページ3 (4 kB) CPU キャッシュ CPU 処理部ページ1内データ欲しい

OSのメモリ読み込み戦略 • ページングを行うメモリページ1 (4 kB) ページ2 (4 kB)

ページ3 (4 kB) CPU キャッシュ CPU 処理部ページ1内データ欲しいページ1 (4 kB)

OSのメモリ読み込み戦略 • ページングを行うメモリページ1 (4 kB) ページ2 (4 kB)

ページ3 (4 kB) CPU キャッシュ CPU 処理部データを使って処理ページ1 (4 kB)

OSのメモリ読み込み戦略 • ページングを行うメモリページ1 (4 kB) ページ2 (4 kB)

ページ3 (4 kB) CPU キャッシュ CPU 処理部次(ページ1)のデータ欲しいページ1 (4 kB)

OSのメモリ読み込み戦略 • ページングを行うメモリページ1 (4 kB) ページ2 (4 kB)

ページ3 (4 kB) CPU キャッシュ CPU 処理部次(ページ1)のデータ欲しいページ1 (4 kB)

OSのメモリ読み込み戦略 • ページングを行うメモリページ1 (4 kB) ページ2 (4 kB)

ページ3 (4 kB) CPU キャッシュ CPU 処理部次データを使って処理ページ1 (4 kB)

キャッシュ戦略は時間・空間的局所性が高いタスクに効率化されているキャッシュは局所性の高さに対処するという表現が自然

OSのメモリ読み込み戦略 • 近くのページをまとめて取ることも (更なる空間的局所性対策) メモリページ1 (4 kB) ページ2

(4 kB) ページ3 (4 kB) CPU キャッシュ CPU 処理部ページ1内データ欲しい

OSのメモリ読み込み戦略メモリページ1 (4 kB) ページ2 (4 kB) ページ3 (4

kB) CPU キャッシュ CPU 処理部ページ1内データ欲しい • 近くのページをまとめて取ることも (更なる空間的局所性対策)

OSのメモリ読み込み戦略メモリページ1 (4 kB) ページ2 (4 kB) ページ3 (4

kB) CPU キャッシュ CPU 処理部ページ1内データ欲しい • 近くのページをまとめて取ることも (更なる空間的局所性対策)

OSのメモリ読み込み戦略メモリページ1 (4 kB) ページ2 (4 kB) ページ3 (4

kB) CPU キャッシュ CPU 処理部ページ1内データ欲しいページ1 (4 kB) ページ2 (4 kB) • 近くのページをまとめて取ることも (更なる空間的局所性対策)

OSのメモリ読み込み戦略メモリページ1 (4 kB) ページ2 (4 kB) ページ3 (4

kB) CPU キャッシュ CPU 処理部データを使って処理ページ1 (4 kB) ページ2 (4 kB) • 近くのページをまとめて取ることも (更なる空間的局所性対策)

OSのメモリ読み込み戦略メモリページ1 (4 kB) ページ2 (4 kB) ページ3 (4

kB) CPU キャッシュ CPU 処理部データを使って処理ページ1 (4 kB) ページ2 (4 kB) • 近くのページをまとめて取ることも (更なる空間的局所性対策)

OSは様々な手法を用いてメモリ局所性の高いタスクを効率的に走らせているこれがGreen Teaへの伏線

Green Tea🍵とその挙動

… … おさらい: Goのヒープ管理 • 同サイズのオブジェクトをスパンでまとめる int (8 byte) struct

(8 byte) struct struct (32 byte) struct struct int int スパン1 (8 byte用) スパン2 (8 byte用) スパン3 (32 byte用) int int

スパンの実態 • Goのスパンは、OSのページを数個まとめたもの ◦ 原則となり合ったページが使われる • 同じスパンを読む方がOSのキャッシュ戦略を活かせる object スパン (32kB)

ページ (4 kB) ページ (4 kB) ページ (4 kB) object object object

これまでのGCの課題 • GC自体のメモリ局所性が低い ◦ スパン(ページ)間を飛び回っている ◦ OSのキャッシュ戦略を上手く活かせてない ▪ 遠いページに移動するたびキャッシュリセット •

↑ のせいでメモリ読み込みが遅く、CPUの処理性能をフルで活かせない ◦ CPUの進歩の方が速く、昔とは犠牲にしたいものが逆になってしまった

Green Tea🍵 • メモリ局所性の高い、新たなマークアルゴリズム ◦ Tri-colorを拡張し、スパンごとにオブジェクトをスキャンする • 実は名前の由来が日本 ◦

Green Teaのプロトタイプを作ったのは、今のTech LeadであるAustine Clements ◦ プロトタイピングの大部分は、Austineさんが横浜のカフェで大量の抹茶をしばきながら行った

Green Teaはスパンごとのオブジェクトスキャンで局所性を上げている実際の挙動を見てみましょう

スタック var x T var y T 状態一覧見てない見る予定

今見てるもう見たスパンA スパンB スパンC スパンD T T T T T T [4]*T [4]*T [4]*T おさらい: ここから sweep phase

スタック var x T var y T 状態一覧見てない見る予定

今見てるもう見たスパンA スパンB スパンC スパンD T T T T T [4]*T [4]*T

実験: Green Teaってホントに速いの？

効きそうなパターンを作成してみた

やってること 100万件の slice s □□□...

やってること s □□□... T a:□ b:□

やってること s □□□... T a:□ b:□ int □

やってること s □□□... T a:□ b:□ int □ まだsは使う状態で

GC

T T T T []T スタック var s []T スパン

(T 用) スパン (int 用) スパン ([]*T 用) T T.b T.b T.b T.b T.b T.b T.b

T T T T []T スタック var s []T スパン

(T 用) スパン (int 用) スパン ([]*T 用) T T.b T.b T.b T.b T.b T.b T.b これまでなら

T T T T []T スタック var s []T スパン

(T 用) スパン (int 用) スパン ([]*T 用) T T.b T.b T.b T.b T.b T.b T.b Green Teaなら

T T T T []T スタック var s []T スパン

T T T T []*T スパン (T 用) スパン (int

用) スパン ([]*T 用) T T.b T.b T.b T.b T.b T.b T.b スタック var s *[]T こうなって欲しい (実際に確かめてはいません)

こんな感じで実行 (最適化は切った)

結果

結果 5回ともちゃんと速い

まとめ • Green Teaはスパン単位のスキャンで局所性をup • とてもシンプル、だけど一部のケースで強力 ◦ OSの特性をよく活かす方向性 Go 1.26から

ガベージコレクションが速くなります。

GC25 Recap+: Advancing Go Garbage Collection wi...

GC25 Recap+: Advancing Go Garbage Collection with Green Tea

More Decks by Takuto Nagami

Other Decks in Technology

Featured

Transcript