GoジェネリクスのGC Shape Stenciling
Go 1.18(2022年)で導入されたジェネリクスの実装方式。単態化と辞書渡しの中間に位置する「ハイブリッド方式」で、型を「GCから見た形状(shape)」でグループ化し、shapeが同じ型同士は1本の機械語本体を共有しつつ、型固有の違いは辞書経由で渡す。
背景: Generic Dilemma
2009年、Go開発者のRuss Coxは、ジェネリクスの言語設計における根本的なトレードオフをThe Generic Dilemmaとして整理した。「ジェネリクスを持たない(C方式)」「単態化(C++方式)」「暗黙のボクシング(Java方式)」のいずれを選んでも代償があるという三択で、Goのジェネリクス設計はこの二律背反を部分的に回避することを目指した。
設計の紆余曲折(2017-2020年)
- 2018年: 最初の草案「contracts」は、制約をサンプルコードの形で表現する方式だったが、暗黙的すぎるとの批判を受けた。
- 2019年: contractsをメソッド・型を明示的に列挙する形式に改訂し、「type list」(許容する具体型の列挙)を導入。しかしtype listが通常のインターフェース型と見分けにくく、混乱を招いた。
- 2020年(“The Next Step for Generics”): contractsという概念自体を廃止し、type listはインターフェースの制約記法に統合された。
- 2020年9月: 単態化案と辞書渡し案が同一コミット内で並行して提案され、その後の議論を経て両者を折衷するGC Shape Stencilingが採用された。
仕組み: shapeによるグルーピング
GC Shape Stencilingは、型を「ガベージコレクタから見た形状」——サイズ・アラインメント・ポインタの位置——が同じかどうかでグループ化する。Go 1.18時点の実際のルールはより狭く、以下のいずれかを満たす型同士のみが同じshapeになる。
- 基底型(underlying type。型定義から名前を取り除いた素の型)が完全に一致する
- 両方ともポインタ型である(構造体ポインタは中身の型を問わずすべて同じshapeとして扱われる)
構造体の場合、フィールド名・順序・型がすべて一致していないと基底型は同じにならない。
コンパイラが生成するコード
同じshapeの型グループに対して、コンパイラは以下を生成する。
- shape本体: 実際の処理を行う共有された機械語本体。例:
main.First[go.shape.*uint8] - ラッパー: 各具体型ごとに生成される薄い関数で、引数を整えてshape本体を呼び出すだけ。例:
main.First[*int]
darwin/arm64のアセンブリ(Plan 9 syntax)で見ると、ポインタ型のshape本体では
MOVD (R1), R0 ; xs[0]をアドレスR1からロード
のように直接値をロードするだけだが、メソッド呼び出しを含む関数(Greet[T Stringer]など)では、辞書から関数ポインタを取り出して間接呼び出しする。
MOVD (R0), R2 ; 辞書から関数ポインタを取り出す
CALL (R2) ; レジスタ経由の間接呼び出し
ジェネリック関数内でのメソッド呼び出し(例: x.String())は実行時に型を探索するのではなく、コンパイル時に辞書へ埋め込まれた関数ポインタを間接呼び出しする形に静的に解決される。
辞書(dictionary)の中身
shape本体が型固有の情報を得るために参照する辞書には、以下が含まれる。
- 型ディスクリプタへのポインタ
- 派生型情報(スライス・マップなど、元の型から派生する型の情報)
- サブ辞書(ネストされたジェネリック関数呼び出し用の辞書)
- itab(インターフェースとメソッドの対応表)
パフォーマンス
- コード量削減: 25種類の型を検証したケースでは、本体サイズが約71%削減された(25個のインスタンス化 → 7個のshape本体)。ただしshapeを共有できる条件(同一基底型 or ポインタ型同士)は限定的で、実際のアプリケーションコードではこの削減効果が薄れやすいとされる。
- 実行時オーバーヘッド: 2022年のPlanetScaleによる報告(Vincent Marti)の再現実験では、ポインタを扱うケースで単態化に対して1.53〜2.15倍、インターフェースを厳密に扱うケースで1.37〜2.55倍遅いという結果が出た。
- 値型での優位性: 値型を扱う場合、ジェネリクスはインターフェースベースの実装より28〜37%高速だった。これはインターフェースに値を格納する際に発生するボクシング(ヒープ割り当て)を、ジェネリクスでは回避できるため。
理論的基礎・関連研究
- Featherweight Go(2020): Goにジェネリクスを型安全に追加でき、単態化によってコンパイル可能であることを形式的に証明した論文。
- Generic Go to Go(OOPSLA 2022, Ellis他): 実用的なコードにおけるshape共有の効果を測定し、Go 1.18のGC Shape Stencilingと純粋な単態化とで命令数がほぼ同等(703 vs 674)であることを報告。型のネストが深く指数的に組み合わせが増えるケースでは、純粋単態化だとバイナリが6.3MBまで膨らむ例を示した。