It Made My Day

Acutally, my whole life is just one big yak shaving exercise.

GoのGenerics の内部実装の設計：辞書 と Gcshape Stenciling

この設計書→Go 1.18 Implementation of Generics via Dictionaries and Gcshape Stenciling が最終的に採用されたもの（2022年3月までコミットされている）。 本記事はこの設計書の概要を極力わかりやすく説明し、読者がGo で Generics がどのような設計で実現されているか大枠を理解することを目的とする。そのため、詳細な設計や具体的な実装については（複雑になりすぎるため）割愛し、やや概念的な説明になっている。

型パラメータごとに異なるメソッドや演算をどう扱うか

Go の Genericsは、バイナリサイズを膨張させず、パフォーマンスも確保する方法として "辞書" と "Stenciling" のプロポーザルのハイブリッドな形式である、「辞書とGCShape Stenciling」 もしくは「GCShape Stenciling」と呼ばれる方式を採用した。

Generics のコンパイラ実装は、主に具体的な型を持つ引数で実行されるジェネリック関数およびメソッドのインスタンス化を行う。 ここで単純に型引数ごとに具象型を用いたコードを生成すると、コンパイル時間やバイナリサイズが増大してしまう。 そこで、純粋なステンシル処理を避け、辞書を使って1つの関数インスタンスを複数の型引数に対して実行できるようにし、コードサイズの節約とパフォーマンスの両立を実現している。

私がこの「ステンシル処理」という言葉の意味を正確に理解しているか怪しいのだが、 Stenciling のプロポーザル Generics implementation - Stenciling には「この手法では、ジェネリック関数の本体を、インスタンス化される型セットごとにインスタンス化することで、ジェネリック関数の複数の実装を生成する」と書かれており、つまり実際に利用できるコンポーネントを生成するような処理のことをステンシル処理と呼んでいると認識している（製図の分野では、同じ形を描くために使用する型をステンシルテンプレートと呼んでいるようだ）。

Genericsが具体的な型を把握するための方法は言語によって異なるため、他言語の方針について外部記事（Rustコンパイラ開発ガイド Monomorphization - Rust Compiler Development Guide など）から引用する。

例えば、Java などの一部の言語では、実行時まで値の最も正確な型がわからない場合がある。Java の場合、（ほぼ）すべての変数が参照値（つまり、ヒープに割り当てられたオブジェクトへのポインタ）であるため、これは問題ない。この柔軟性は、オブジェクトへのアクセスはすべてポインタを参照解除する必要があるため、パフォーマンスを犠牲にしている。 Rust は異なるアプローチを採用しており、すべてのジェネリック型をモノモーフィズム化する。つまり、コンパイラは必要な具体的な型ごとに、ジェネリック関数のコードの異なるコピーを作成する。例えば、コード内で Vec と Vec を使用すると、生成されるバイナリには Vec 用のコードが 2 つ含まれることになる。結果としてプログラムは高速になるが、コンパイル時間（すべてのコピーの作成には時間がかかる可能性がある）とバイナリサイズ（すべてのコピーが大量のスペースを占める可能性がある）が犠牲になる。 C++ におけるテンプレートのインスタンス化も実質モノモーフィゼーションであり、広く使われているがコードが肥大化するとして悪名高い。

辞書とGCShape Stenciling の概要

辞書

型引数に関する関連情報を提供し、これにより、単一の関数のインスタンス化を複数の異なる型引数に対して正しく実行できるようになる。 この辞書は、型のメソッドや演算子などの情報を含み、実行時に動的に参照される。 これにより、実行時に渡される型に応じた処理が可能となる。 実態は、ジェネリック関数/メソッドの具体的な型引数のリストやitab（interfaceの定義）などが含まれる。

GCShape Stenciling

型パラメータに対して、同じメモリレイアウト（GCShape）を持つ型同士でコードを共有する手法。 これにより、同じ GCShape を持つ型に対しては、同じコードを再利用できる。 上述したstencilingのプロポーザルでは「インスタンス化される型セットごと」に実装を生成する方針だったが、最終的にはこのGCShapeを用いることで、型セットよりも広い範囲で関数実装を再利用できるようにしている。

GCShapeは、型のサイズ、必要なアライメント、そして型のどの部分にポインタが含まれるかによって決まる（内部実装的にはshapeと呼ばれ、コンパイラの中間表現（IR）で指定される）。 GCShapeごとに単一のアセンブリチャンクが生成され、それぞれが引数として辞書を受け取る。 2 つの具象型が同じ GCShape グループに属するのは、それらの基底型が同じであるか、両方がポインタ型である場合のみ。

この実装方針における課題

ジェネリック型を使用した再帰関数

辞書はコンパイル時に作成されるため、ジェネリック型をネストした再帰関数を処理することができない（Issue#48018）。たとえば、このようなコード↓をGo1.25でビルドしようとしても失敗する。

package main

type Box[A any] struct {
    value A
}

func Nest[A any](b Box[A], n int) any {  // ERROR instantiation cycle
    if n == 0 {
        return b
    }
    return Nest(Box[Box[A]]{b}, n-1)
}

func main() {
    Nest(Box[int]{0}, 10)
}

Go Playground

ハイブリッドアプローチの恩恵はどの程度あったのか

また、Generics implementation - GC Shape Stenciling では、ハイブリッドなアプローチの成果もしくは課題として下記のような観点が挙げられているが、具体的にどの程度メリットがあるかについて言及されている記事などは見当たらない。

  • 完全にステンシル化した場合と比べて、辞書を使用した場合にコードサイズがどれくらい削減できるか、また実行時間がどれくらい遅くなるか。
  • GCシェイプが分かれば、ジェネリック型の項目を操作するコードはすべて単純化されるため、アセンブリコードはほとんどの場合、GCステンシル実装と完全ステンシル実装で同じになる。唯一の例外は、メソッド呼び出しがコンパイル時に完全に解決できないことであり、これはエスケープ解析で問題となる可能性がある。ジェネリック型で呼び出されるメソッドはすべて慎重に解析する必要があり、完全ステンシル実装よりもヒープ割り当てが増える可能性がある。
  • 完全ステンシル実装ではインライン化が行われるような状況でも、インライン化が行われない（コンパイラの最適化に関係すると思われる）。

参考記事