HN 日本語サマリー

← 一覧へ戻る
プログラミング

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

GC shape stenciling in Go generics (rednafi.com)

34 pointsby ingve6 コメント

要約

Goのジェネリクス実装は、完全なモナド化と型消去の中間に位置する「GCシェイプステンシリング」というアプローチを採用しています。これは、型がGC(ガベージコレクタ)から見た形状(サイズ、アライメント、ポインタの有無)に基づいてコンパイルコードを共有する仕組みです。これにより、コンパイル時間とバイナリサイズの増加を抑えつつ、ジェネリクスのオーバーヘッドを最小限に抑えています。

全文翻訳

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

Goのジェネリクス提案を調べているうちに、コンパイラがそれをどのように実装しているのか興味を持ちました。コンパイラは通常、ジェネリクスを2つの方法のいずれかで扱います。

  • 完全なモジュライズでは、コンパイラはジェネリクスコードを具体的な型固有のコードに変換します。プログラムが使用する型引数のセットごとに個別のバージョンを生成します。Rustはこの方法で動作し、C++のテンプレートも同様です。

  • 型消去では、コンパイラはジェネリクスコードの共有バージョンを1つ保持し、型パラメータを共通の型に置き換えます。Javaでは、これらをObjectまたは宣言された境界に消去します。

完全なモジュライズは、コンパイラに生成される各関数の正確な型を提供します。コンパイラは各関数を通常のコードのように最適化でき、ジェネリクスによる抽象化は実行時のオーバーヘッドを追加しません。欠点は、型引数の各異なるセットが別の関数本体を追加する可能性があり、コンパイル時間とバイナリサイズを増加させることです。消去はスペクトルの反対側にあります。コンパイルする本体は1つだけですが、実行時には具体的な型が失われます。プログラムは代わりにキャストとボクシングを必要とします。

Goは、GCシェイプステンシリングと呼ばれるアプローチで、この2つの中間に位置します。これはモジュライズを行いますが、型がGC上でどのように見えるか(GCシェイプ)に限定されます。同じ形状を持つ型は、1つのコンパイル済み本体を共有します。

完全なモジュライズ

小さなRustプログラムは、完全なモジュライズがすべての具体的な関数をどのように生成するかを示しています。ジェネリックなidentity関数をu32で一度、u64で一度呼び出します。

#[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は生成されたidentity関数のみを保持します。

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では、関連する出力は次のようになります。

; 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に消去されます。

具体的な型引数は、消去されたクラスでは実行時に利用できません。消去は、型パラメータが参照型のみを受け入れられることも意味します。Tが期待される場所にintを渡すと、JavaはそれをIntegerとしてボックス化します。ボクシングはヒープ割り当てと間接参照を伴います。これらのキャストとボックスは、特殊化されたバージョンでは決して行われない実行時の処理です。

GCシェイプステンシリング

Goのジェネリクス提案では、実装戦略はオープンなままでした。出荷されたのはGCシェイプステンシリングです。Goでの同じidentity関数は次のようになります。

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つのポインタ型で共有される本体です。

この3番目の本体の共有は情報損失を伴います。コンパイル済みコードは、ポインタを受け取ったことは知っていますが、呼び出しが*Userを使用したのか*Orderを使用したのかはわかりません。本体が正確な型を必要とする場合、Goは隠された辞書引数を通じてそれを供給します。この辞書は、通常の引数と一緒に渡されます。

辞書という名前にもかかわらず、コンパイラが各具体的なインスタンス化に対して生成し、バイナリの読み取り専用データに格納する固定テーブルです。内部には、実行時型記述子と、本体が必要とする可能性のあるその他の型固有のエントリが含まれています。identityは型に依存する操作を行わないため、その本体は辞書を無視します。コンパイラはそれでもすべてのインスタンス化に対して1つを出力します。

したがって、このプログラムは3つの関数本体と4つの辞書を生成するはずです。//go:noinlineディレクティブは、コンパイラが呼び出しをインライン化するのを防ぐため、identityシンボルはバイナリに残ります。これをmain.goとして保存し、ビルドしてシンボルテーブルをフィルタリングします。go tool nmはシンボルをリストします。rgはidentity本体と辞書を保持し、awkはアドレスを削除します。

go build -o /tmp/gcshape main.go
go tool nm /tmp/gcshape \
    | rg 'main\[(identity|\.dict\.identity)\['
    | awk '{print $2, $3}'

darwin/arm64上のGo 1.26.5では、次のようになります。

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のノートでは、以前の低下の大部分はジェネリクスサポートによるものだと述べています。