GoジェネリクスにおけるGCシェイプステンシリング

Goのジェネリクス提案を調べているうちに、コンパイラがそれをどのように実装しているのか興味を持ちました。コンパイラは通常、ジェネリクスを2つの方法のいずれかで扱います。 完全なモナド化では、コンパイラはジェネリックコードを具体的な型固有のコードに変換します。プログラムが使用する型引数のセットごとに個別のバージョンを生成します。Rustはこの方法で動作し、C++のテンプレートも同様です。 型消去では、コンパイラはジェネリックコードの共有バージョンを保持し、型パラメータを共通の型に置き換えます。JavaはそれらをObjectまたは宣言された境界に消去します。 完全なモナド化は、コンパイラに各生成関数に正確な型を与えます。通常のコードのように各関数を最適化でき、ジェネリック抽象化は実行時のオーバーヘッドを追加しません。欠点は、型引数の各異なるセットが別の関数本体を追加する可能性があり、コンパイル時間とバイナリサイズが増加することです。消去はスペクトルの反対側にあります。コンパイルする本体は1つだけですが、具体的な型は実行時には失われます。プログラムは代わりにキャストとボクシングを必要とします。 Goは、GCシェイプステンシリングと呼ばれるアプローチで、この2つの中間に位置します。モナド化しますが、型のGCシェイプまでです。同じ形状を持つ型は、1つのコンパイル済み本体を共有します。 完全なモナド化 小さなRustプログラムは、完全なモナド化がどのようにすべての具体的な関数を生成するかを示しています。ジェネリックなアイデンティティ関数をu32とu64でそれぞれ1回呼び出します。 ```rust #[inline(never)] fn identity<T>(value: T) -> T { value } fn main() { println!("{} {}", identity(42_u32), identity(42_u64)); } ``` これをmono.rsとして保存します。rustcの--emitオプションは、LLVM中間表現をmono.llに書き出します。-Cフラグは、最適化レベルゼロ、単一のコード生成ユニット、v0シンボルマングリングを選択します。次に、rgは生成されたアイデンティティ関数のみを保持します。 ```bash rustc mono.rs --emit=llvm-ir=mono.ll \ -C opt-level=0 \ -C codegen-units=1 \ -C symbol-mangling-version=v0 rg -A5 '; mono::identity' mono.ll | rg -v 'Function Attrs|^--$' ``` Rust 1.96.1では、関連する出力は次のようになります。 ```llvm ; mono::identity::<u32> define internal i32 @_RINvCs15VVTAbh19D_4mono8identitymEB2_(i32 %value) unnamed_addr #0 { start: ret i32 %value } ; mono::identity::<u64> define internal i64 @_RINvCs15VVTAbh19D_4mono8identityyEB2_(i64 %value) unnamed_addr #0 { start: ret i64 %value } ``` ハイライトされたシグネチャは、何が起こったかを示しています。1つの関数はi32を受け取り、返します。もう1つはi64を使用します。1つのジェネリックソース関数が2つの具体的な関数本体になりました。 C++のテンプレートもこれを行います。テンプレートのインスタンス化中に、コンパイラは具体的な引数のセットごとに特殊化を作成します。同じ特殊化が複数のオブジェクトファイルに現れると、GCCの実装はすべてのコピーを出力し、リンカが重複を折りたたむようにします。 型消去 Javaは代わりに1つの実装を保持します。Box<String>とBox<Integer>は両方とも同じBoxクラスとして実行されます。無制限のTはObjectに消去されるため、Tとして宣言されたフィールドはバイトコードではObjectとして格納されます。コードがBox<String>からそのフィールドを読み取ると、javacはStringへのキャストを挿入します。T extends Numberのような境界付きパラメータは、代わりにNumberに消去されます。 消去されたクラスには、実行時に具体的な型引数は利用できません。消去は、型パラメータが参照型のみを受け入れることも意味します。intをTが期待される場所に渡すと、JavaはそれをIntegerとしてボックス化します。ボクシングはヒープ割り当てと間接参照を伴います。これらのキャストとボックスは、特殊化されたバージョンが決して行わない実行時の作業です。 GCシェイプステンシリング Goのジェネリクス提案では、実装戦略はオープンなままでした。出荷されたのはGCシェイプステンシリングです。ここにGoでの同じアイデンティティ関数があります。 ```go package main import "fmt" type User struct{} type Order struct{} //go:noinline func identity[T any](value T) T { return value } func main() { fmt.Println(identity(42)) fmt.Println(identity(3.14)) fmt.Println(identity(&User{})) fmt.Println(identity(&Order{})) } ``` このプログラムは、int、float64、*User、および*Orderでidentityをインスタンス化します。どの呼び出しがコンパイル済みコードを共有できるかを決定するために、コンパイラは各型引数をそのGCシェイプにマッピングします。 GCシェイプとは、型がアロケータとガベージコレクタにどのように見えるか、つまりサイズ、アライメント、およびポインタを含む部分です。実際のルールはそれよりも厳格です。Go 1.18の実装ノートによると、2つの型は、1つの例外を除いて、同じ基盤型を持つ場合にのみGCシェイプを共有します。すべてのポインタ型は、*uint8という名前の単一のシェイプを共有します。 したがって、*Userと*Orderは同じグループに分類されます。例外はポインタ型のみをカバーします。map[string]intとchan intは実行時にはそれぞれ1つのポインタですが、どちらもポインタ型ではありません。それらは独自のシェイプを保持します。 コンパイラは各シェイプをTに置き換え、シェイプごとに1つのバージョンの関数をコンパイルします。その置換がステンシリングの部分です。上記の4つの呼び出しには、3つの本体しか必要ありません。int用、float64用、そして2つのポインタ型で共有される1つです。 この3番目の本体を共有すると情報が失われます。コンパイル済みコードはポインタを受け取ったことは知っていますが、呼び出しが*Userを使用したのか*Orderを使用したのかはわかりません。本体が正確な型を必要とする場合、Goは通常の引数と並んで渡される隠された辞書引数を通じてそれを供給します。 名前にもかかわらず、辞書はコンパイラが各具体的なインスタンス化のために生成し、バイナリの読み取り専用データに格納する固定テーブルです。内部には、実行時型記述子と、本体が必要とする可能性のあるその他の型固有のエントリが含まれています。identityは型に依存する何も行わないため、その本体は辞書を無視します。コンパイラはそれでもすべてのインスタンス化のために1つを出力します。 したがって、このプログラムは3つの関数本体と4つの辞書を生成する必要があります。//go:noinlineディレクティブは、コンパイラが呼び出しをインライン化するのを停止するため、identityシンボルはバイナリに残ります。main.goとして保存し、ビルドしてからシンボルテーブルをフィルタリングします。go tool nmはシンボルをリストします。rgはidentity本体と辞書を保持し、awkはアドレスを削除します。 ```bash go build -o /tmp/gcshape main.go go tool nm /tmp/gcshape \ | rg 'mainutter.identity butter.dict.identity butter[' \ | awk '{print $2, $3}' ``` Go 1.26.5 on darwin/arm64では、次のようになります。 ``` R main..dict.identity[*main.Order] R main..dict.identity[*main.User] R main..dict.identity[float64] R main..dict.identity[int] T main.identity[go.shape.*uint8] T main.identity[go.shape.float64] T main.identity[go.shape.int] ``` 最初の列は2つのグループを区別し、go tool nmのドキュメントはそれを説明しています。Rは読み取り専用データをマークします。最初の4行は、*Order、*User、float64、およびintの辞書です。Tはコードを保持するテキストセグメントをマークします。最後の3行はコンパイル済み本体です。intとfloat64はそれぞれ独自の本体を取得しました。ハイライトされたgo.shape.*uint8本体は両方のポインタ型で共有されているため、4つのインスタンス化で3つの本体しか生成されませんでした。 注 グループ化は基盤型ごとに行われるため、名前付き型は新しい本体を追加しません。type MyInt intを追加し、identity(MyInt(7))を呼び出します。本体の数は3のままです。MyIntはgo.shape.intを再利用し、独自の辞書を追加するだけです。 この共有には実行時のコストがかかります。共有本体の一部の操作は、正確な型を必要とします。型パラメータの値に対するメソッド呼び出し、インターフェースへの変換、型アサーションおよび型スイッチです。コンパイラは、これらの操作を辞書パスで書き換え、実行時に辞書から必要なものを読み取るようにします。完全にモナド化された本体は決してそうしません。 これらの辞書読み取りを除けば、共有本体は、提案のリスクセクションによると、完全にモナド化されたコードと同じアセンブリにほとんどコンパイルされるはずです。主な例外はメソッド呼び出しであり、コンパイル時に完全に解決できません。また、インライン化をブロックし、エスケープ分析をより保守的にする可能性があり、追加のヒープ割り当てを意味する可能性があります。 ジェネリクスは当初コンパイラを遅くしました。Go 1.18のリリースノートによると、コンパイル速度はGo 1.17よりも約15％遅くなる可能性があるとのことです。Go 1.20はビルド速度を最大10％改善し、Go 1.17と同水準に戻しました。両方の数値はステンシリングだけではなくコンパイラ全体をカバーしていますが、1.20のノートは、以前の低下の大部分をジェネリクスサポートに起因すると述べています。