Goジェネリクスを支えるGC Shape Stencilingと辞書渡しの仕組み

Goジェネリクスを支える GC Shape Stencilingと辞書渡しの仕組み 株式会社カンム 菅原 元気

Goジェネリクスを支えるGC Shape Stencilingと辞書渡しの仕組み 自己紹介 菅原 元気 株式会社カンム プラットフォームチーム GitHub: @winebarrel / X: @sgwr_dts インフラまわりをやっています いろいろ作っています: https://winebarrel.github.io/ 2

• https://winebarrel.github.io/

Goジェネリクスを支えるGC Shape Stencilingと辞書渡しの仕組み 今日話すこと 1. ジェネリクスの実装方式と、Goが選んだ「中間」の道 2. GC Shape Stenciling ＋ 辞書渡しの仕組み 3. アセンブリで実際の動きを確かめる 4. どれくらいコードサイズが減るのか（と、その限界） 3

Goジェネリクスを支えるGC Shape Stencilingと辞書渡しの仕組み ジェネリクスの実装方式 単態化（Monomorphization）: C++、Rust 「型ごとに専用のコードをコピー」 実行が速い / バイナリの肥大化 辞書渡し（Dictionary Passing）: Haskell 「コードは1本だけ。型ごとの違いは『辞書』で外から渡す」 バイナリが小さい / 実行が遅い その他: Java（型消去）、Swift（ハイブリッド）など ※ 分かりやすさのために単純化しています 4

Goジェネリクスを支えるGC Shape Stencilingと辞書渡しの仕組み Goのジェネリクス Goのジェネリクスは、完全な単態化でも純粋な辞書渡しでもなく GC Shape Stenciling ＋ 辞書渡し で実現されています。 5

Goジェネリクスを支えるGC Shape Stencilingと辞書渡しの仕組み ジェネリクス追加までの経緯 年 2009 できごと Russ Cox "The Generic Dilemma" C方式（プログラマが遅い）／C++方式（コンパイルが遅い・バイナリ肥大）／Java方式（実行効率が悪い） contracts 第1版: 制約を"サンプルコード"で書いてコンパイラが解析 2018 「暗黙的すぎる」「演算子の表現が不透明」「構文が増える」と批判される contracts 改訂版: メソッドと型を明示的に列挙する形へ全面書き換え 2019 結果、インターフェースとほとんど見分けがつかなくなる 設計が固まる。理論的裏付けとして Featherweight Go 2020 contractsを廃止し制約はインターフェース型へ → proposal #43651 Stenciling（完全単態化）／2. Dictionaries（完全辞書渡し） 2020-09 実装方式の提案：1. golang-devでの議論を経て、9/30 に 3. GC Shape Stenciling（両者の中間）が追加され採用 2021-02 proposal #43651 採択 2022-03 Go 1.18 リリース（実装仕様 generics-implementation-dictionaries-go1.18.md ） 6

Goジェネリクスを支えるGC Shape Stencilingと辞書渡しの仕組み Goジェネリクスの実装 7

Goジェネリクスを支えるGC Shape Stencilingと辞書渡しの仕組み 題材コード type Stringer interface{ String() string } type UserA struct{ name string } func (u *UserA) String() string { return u.name } type UserB struct{ id int } func (u *UserB) String() string { return "user" } // 型パラメータ T のメソッド String() を呼ぶジェネリック関数 func Greet[T Stringer](x T) string { return "Hi, " + x.String() } func main() { Greet(&UserA{"alice"}) // *UserA で具体化 Greet(&UserB{42}) // *UserB で具体化 } 8

Goジェネリクスを支えるGC Shape Stencilingと辞書渡しの仕組み コンパイル後の処理の流れ Greet(&UserA{...}) Greet(&UserB{...}) ▼ ラッパー main.Greet[*main.UserA] ラッパー main.Greet[*main.UserB] ▼ 第一引数 .dict に 辞書A / 辞書B をセット shape本体 main.Greet[go.shape.*uint8] （ポインタ型で共有・1本だけ） ▼ x.String() = .dict 先頭の関数ポインタを間接呼び出し（1段） (*UserA).String (*UserB).String 1. Greet(&UserX{}) がラッパー関数を呼ぶ 2. ラッパーが辞書（型ディスクリプタ・関数ポインタ等）と引数をshape本体へ渡す 3. shape本体が辞書経由で (*UserX).String を呼ぶ 4. shape本体が共通処理（ "Hi, " との結合）を行って返す 9

Goジェネリクスを支えるGC Shape Stencilingと辞書渡しの仕組み 実装のポイントは2点 1. shapeごとに機械語の本体を1本に共通化 型が同じように扱える単位（shape）ごとに本体を1本だけ生成 （ポインタ型はすべて同じshape） 2. 型ごとに違う処理は辞書経由で呼ぶ メソッド呼び出しなど、型ごとに異なる部分は辞書から引く 10

Goジェネリクスを支えるGC Shape Stencilingと辞書渡しの仕組み GC shape のグルーピング規則 「GC（ガベージコレクタ）から見た型の姿」でグループ化 サイズ（何バイトか） アラインメント（何バイト境界に置くか） ポインタの位置（型のどこがポインタか） → 「GCから見て同じ姿」なら同じ機械語で処理して問題ない 11

Goジェネリクスを支えるGC Shape Stencilingと辞書渡しの仕組み 辞書の中身 shape本体には型ごとの情報が埋め込まれない。その情報を「辞書」として渡す。 辞書は呼び出し側のコンパイル時に静的生成され、読み取り専用データとしてバイナリに焼き込まれる。 セクション メソッド式 サブ辞書 型情報 itab 中身 型パラメータのメソッド実体への関数ポインタ 中でさらに別のジェネリック関数を呼ぶとき、その呼び先に渡す辞書 型引数そのもの（ T が実際にどの型か）と、派生型（ []T 、 map[K]V など） 型パラメータの値をインターフェース値に変換するときに使う対応表 この4セクションがこの順に並ぶ。呼び出し時は隠しの第一引数 .dict として本体に渡る。 ※ Go 1.18 にはメソッド式のセクションがなく、メソッド呼び出しも itab 経由だった（1.19 からメソッド式経由に） 12

Goジェネリクスを支えるGC Shape Stencilingと辞書渡しの仕組み アセンブリで確かめる 13

Goジェネリクスを支えるGC Shape Stencilingと辞書渡しの仕組み shape本体とラッパー func First[T any](xs []T) T { return xs[0] } func main() { First([]*int{new(int)}) // *int で具体化 First([]*string{new(string)}) // *string で具体化 First([]int{0}) // int で具体化 } コンパイル後のシンボル： # shape本体 main.First[go.shape.int] main.First[go.shape.*uint8] # ラッパー main.First[int] main.First[*int] main.First[*string] # int 向け本体 # ポインタ向け本体（*int と *string で共有） → 本体はshapeごとに1本、ラッパーは具体化した型ごとに1個 14

Goジェネリクスを支えるGC Shape Stencilingと辞書渡しの仕組み ラッパーは辞書を積んで本体を呼ぶ Greet[*main.UserA] ラッパーの中身はこれだけ ; 引数 x を第2引数の位置(R1)へずらす（R0 を .dict 用に空ける） MOVD R0, R1 ; 空いた第1引数(R0)に静的辞書のアドレスを入れる MOVD $main..dict.Greet[*main.UserA](SB), R0 ; shape本体を呼ぶ CALL main.Greet[go.shape.*uint8](SB) // 概念的にやっていること func Greet_wrapper(x *UserA) string { return Greet_shape(dictGreetUserA, x) // .dict を先頭に足して呼ぶ } 15

Goジェネリクスを支えるGC Shape Stencilingと辞書渡しの仕組み

shape本体の共有
*int

も *string も同じ main.First[go.shape.*uint8] を呼ぶ

CBZ
MOVD

R2, 48
(R1), R0

; len(R2)==0 なら範囲外パニックへ（xs[0] の境界チェック）
; xs[0]（R1=先頭アドレス）を返り値にロード

// First の shape 本体（return xs[0]）が概念的にやっていること
func First_shape(dict *Dictionary, xs []T) T {
if len(xs) == 0 { // CBZ R2, 48 : len==0 なら
panic("index out of range") // runtime.panicBounds へ
}
return xs[0] // MOVD (R1), R0
}

ポインタは、中身が *int でも *string でも「8バイトのアドレス値」でしかない。
運ぶ操作は指す先の型に関係なく同じ機械語 → 1本で全ポインタ型をまかなえる
16

Goジェネリクスを支えるGC Shape Stencilingと辞書渡しの仕組み

メソッドディスパッチ
Greet[go.shape.*uint8]
MOVD
MOVD
CALL

(R0), R2
R1, R0
(R2)

の中の x.String()

; .dict(R0) の先頭 = String() の関数ポインタを R2 へ取り出す
; レシーバ x(R1) をメソッドの第1引数(R0)へ移す
; R2 の関数ポインタを間接呼び出し（＝ x.String()）

// 概念的にやっていること
func Greet_shape(dict *Dictionary, x someShape) string {
stringFn := dict.funcs[0] // .dict 先頭の関数ポインタを取り出す
s := stringFn(x)
// x をレシーバに間接呼び出し
return "Hi, " + s
}

17

Goジェネリクスを支えるGC Shape Stencilingと辞書渡しの仕組み 効果測定と性能 18

Goジェネリクスを支えるGC Shape Stencilingと辞書渡しの仕組み shape共有はどれくらい効くのか func Process[T fmt.Stringer](items []T) string { /* ループ内で item.String() */ } type P1 struct{ v int }; func (p *P1) String() string {...} // ① ポインタ型 10種類（P2〜P10） type V1 struct{ v int }; func (v V1) String() string {...} // ② 同じ基底型の値型 10種類（V2〜V10） type D1 struct{ a int }; type D3 struct{ x, y int } // ③ 異なる基底型の値型 5種類（D1〜D5） 具体化グループ 具体化数 ポインタ型 10 同じ基底型の値型（ struct{v int} ） 10 異なる基底型の値型 5 合計 25 生成された本体 1本 1本 5本 7本 本体サイズ 288B 288B 計1504B 2080B 完全単態化なら 25本・約 7264B → 本体サイズで約 71%の節約 （288B × 10 + 288B × 10 + 1504B = 7264B） 19

Goジェネリクスを支えるGC Shape Stencilingと辞書渡しの仕組み ただし、これはベストケース OOPSLA 2022 論文 Generic Go to Go（Ellis, Zhu, Yoshida, Song）が 実用的なベンチマークで Go 1.18 と純粋単態化を比較： 命令数は 703 対 674 でほぼ同じ メソッド実装の再利用は観測されなかった In our experiments, we do not observe the reuse of method implementations, or synthesis and use of dictionaries. 20

Goジェネリクスを支えるGC Shape Stencilingと辞書渡しの仕組み まとめ Goのジェネリクスは、完全な単態化と辞書渡しの中間（hybrid） shapeごとに本体を1本だけ生成し、同じshapeの型 （ポインタ型 or 基底型が同じ型どうし）が本体を共有する 型ごとの差分は辞書（隠し第一引数 .dict ）で渡す コードサイズ削減は検証環境のベストケースで約71%。 ただし共有条件は限定的で、実コードで効くとは限らない 21

Goジェネリクスを支えるGC Shape Stencilingと辞書渡しの仕組み 参考資料 Russ Cox, The Generic Dilemma Toward Go 2 / The Next Step for Generics go2draft-contracts.md proposal #43651 / 43651-type-parameters.md generics-implementation-stenciling.md generics-implementation-dictionaries.md generics-implementation-gcshape.md generics-implementation-dictionaries-go1.18.md Featherweight Go Ellis, Zhu, Yoshida, Song, Generic Go to Go (OOPSLA 2022) 検証コード: https://github.com/winebarrel/go-gcshape-verification-example 22

• https://research.swtch.com/generic
• https://go.dev/blog/toward-go2
• https://go.dev/blog/generics-next-step
• https://github.com/golang/proposal/blob/master/design/go2draft-contracts.md
• https://github.com/golang/go/issues/43651
• https://go.googlesource.com/proposal/ /refs/heads/master/design/43651-type-parameters.md
• https://go.googlesource.com/proposal/ /refs/heads/master/design/generics-implementation-stenciling.md
• https://github.com/golang/proposal/blob/master/design/generics-implementation-dictionaries.md
• https://github.com/golang/proposal/blob/master/design/generics-implementation-gcshape.md
• https://go.googlesource.com/proposal/ /master/design/generics-implementation-dictionaries-go1.18.md
• https://arxiv.org/abs/2005.11710
• https://songlh.github.io/paper/generic.pdf
• https://github.com/winebarrel/go-gcshape-verification-example

ご清聴ありがとうございました 元記事の全文はこちら： https://zenn.dev/kanmu_dev/articles/3c7057cc7ee5c8 23

• https://zenn.dev/kanmu_dev/articles/3c7057cc7ee5c8