GC shape stenciling in Go generics
While going through the Go generics proposal, I got curious about how the compiler implements it. Compilers usually handle generics in one of two ways:
With full monomorphization, the compiler turns generic code into concrete, type-specific code. It generates a separate version for every set of type arguments the program uses. Rust works this way, and so do C++ templates.
With type erasure, the compiler keeps one shared version of the generic code and replaces the type parameters with a common type. Java erases them to Object or to their declared bounds.
Full monomorphization gives the compiler exact types for every generated function. It can optimize each one like ordinary code, and the generic abstraction adds no runtime overhead. The drawback is that every distinct set of type arguments can add another function body, which increasescompile time and binary size. Erasure is at the opposite end of the spectrum. There is only one body to compile, but the concrete types are gone at runtime. The program needs casts and boxing instead.
Go sits between the two with an approach called GC shape stenciling. It monomorphizes, but only down to a type’s GC shape. Types with the same shape share one compiled body.
Full monomorphization #
A small Rust program shows how full monomorphization generates all the concrete functions. It calls the generic identity function once with a u32 and once with a u64:
#[inline(never)] fn identity < T > ( value: T ) -> T { value }
fn main () { println! ( " {} {} ", identity ( 42_ u32 ), identity ( 42_ u64 )); }
Save it as mono.rs. rustc’s --emit option writes the LLVM intermediate representation to mono.ll. The-C flags select optimization level zero, a single codegen unit, and v0 symbol mangling. Then rg keeps only the generated identity functions:
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|^--