GC shape stenciling in Go generics | Redowan's ReflectionsSkip to content

While going through the Go generics proposal, I got curious about how the compiler<br>implements it. Compilers usually handle generics in one of two ways:<br>With full monomorphization, the compiler turns generic code into concrete, type-specific<br>code. It generates a separate version for every set of type arguments the program uses.<br>Rust works this way, and so do C++ templates.

With type erasure, the compiler keeps one shared version of the generic code and<br>replaces the type parameters with a common type. Java erases them to Object or to their<br>declared bounds.

Full monomorphization gives the compiler exact types for every generated function. It can<br>optimize each one like ordinary code, and the generic abstraction adds no runtime overhead.<br>The drawback is that every distinct set of type arguments can add another function body,<br>which increases compile time and binary size. Erasure is at the opposite end of the<br>spectrum. There is only one body to compile, but the concrete types are gone at runtime. The<br>program needs casts and boxing instead.<br>Go sits between the two with an approach called GC shape stenciling. It monomorphizes, but<br>only down to a type&rsquo;s GC shape. Types with the same shape share one compiled body.<br>Full monomorphization #<br>A small Rust program shows how full monomorphization generates all the concrete functions.<br>It calls the generic identity function once with a u32 and once with a u64:<br>#[inline(never)]<br>fn identityT>(value: T) -> T {<br>value

fn main() {<br>println!("{} {}", identity(42_u32), identity(42_u64));

Save it as mono.rs. rustc&rsquo;s --emit option writes the LLVM intermediate<br>representation to mono.ll. The -C flags select optimization level zero, a single<br>codegen unit, and v0 symbol mangling. Then rg keeps only the generated identity<br>functions:<br>rustc mono.rs --emit=llvm-ir=mono.ll \<br>-C opt-level=0 \<br>-C codegen-units=1 \<br>-C symbol-mangling-version=v0

rg -A5 '; mono::identity' mono.ll | rg -v 'Function Attrs|^--$'

On Rust 1.96.1, the relevant output is:<br>; mono::identity::<br>define internal i32 @_RINvCs15VVTAbh19D_4mono8identitymEB2_(i32 %value) unnamed_addr #0 {<br>start:<br>ret i32 %value<br>; mono::identity::<br>define internal i64 @_RINvCs15VVTAbh19D_4mono8identityyEB2_(i64 %value) unnamed_addr #0 {<br>start:<br>ret i64 %value

The highlighted signatures show what happened. One function takes and returns i32. The<br>other uses i64. One generic source function became two concrete function bodies.<br>C++ templates do this too. During template instantiation, the compiler creates a<br>specialization for each concrete set of arguments. When the same specialization appears in<br>several object files, GCC&rsquo;s implementation emits every copy and leaves it to the linker to<br>collapse the duplicates.<br>Type erasure #<br>Java keeps one implementation instead. Box and Box both run as the same<br>Box class. An unbounded T erases to Object, so a field declared as T is stored as an<br>Object in bytecode. When code reads that field from a Box, javac inserts a<br>cast back to String. A bounded parameter like T extends Number erases to Number<br>instead.<br>The concrete type argument is not available at runtime to the erased class. Erasure also<br>means type parameters accept only reference types. Pass an int where a T is expected and<br>Java boxes it as an Integer. Boxing entails heap allocation and indirection. Those<br>casts and boxes are runtime work that a specialized version never does.<br>GC shape stenciling #<br>Go&rsquo;s generics proposal left the implementation strategy open. What shipped is GC shape<br>stenciling. Here is the same identity function in Go:<br>package main

import "fmt"

type User struct{}<br>type Order struct{}

//go:noinline<br>func identity[T any](value T) T { return value }

func main() {<br>fmt.Println(identity(42))<br>fmt.Println(identity(3.14))<br>fmt.Println(identity(&User{}))<br>fmt.Println(identity(&Order{}))

This program instantiates identity with int, float64, *User, and *Order. To decide<br>which calls can share compiled code, the compiler maps each type argument to its GC shape.<br>A GC shape is how a type appears to the allocator and the garbage collector: its size, its<br>alignment, and which parts of it contain pointers. The actual rule is stricter than that.<br>Per the Go 1.18 implementation notes, two types share a GC shape only when they have the<br>same underlying type, with one exception: all pointer types share a single shape named after<br>*uint8.<br>So *User and *Order end up in the same group. The exception covers pointer types only. A<br>map[string]int and a chan int are each one pointer at runtime, but neither is a pointer<br>type. They keep their own shapes.<br>The compiler substitutes each shape for T and compiles one version of the function per<br>shape. That substitution is the stenciling part. The four calls above need only three<br>bodies: one for int, one for float64, and one shared by the two pointer types.<br>Sharing that third body loses information. The compiled code knows it received a...