Understanding GC Shape Stenciling in Go Generics

While diving into the official proposal for Go generics, I became curious about the underlying compiler mechanics. How does Go actually handle generic types under the hood?

Typically, compilers employ one of two primary strategies for generics:

1. Full Monomorphization: The compiler generates a unique, concrete version of the function for every single type argument used in the program.
2. Type Erasure: The compiler maintains a single, shared version of the code, replacing specific type parameters with a generic "catch-all" type.

Comparing Implementation Strategies

---

1. Full Monomorphization

In this approach, the compiler treats generics like templates. If you call a function with three different types, you get three different functions in your binary.

Rust Example

Consider this simple Rust program (mono.rs) that uses a generic identity function:

#[inline(never)] 
fn identity<T>(value: T) -> T { 
    value 
}

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

To see what happens, we can emit the LLVM intermediate representation (IR) using rustc and filter for the 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|^--$'

The resulting output reveals two distinct functions:

• _RINvCs...mono8identitymEB2_ (for u32)
• _RINvCs...mono8identityyEB2_ (for u64)

Key Takeaway: One source function $\rightarrow$ Multiple concrete bodies. This allows for extreme optimization but increases binary size.

---

2. Type Erasure

Java takes the opposite route. Instead of creating new functions, it "erases" the type.

• Unbounded Types: A generic T is replaced by Object. A field of type T becomes an Object in the bytecode.
• Bounded Types: If you have T extends Number, the compiler erases T to Number.
• The Cost: Because the concrete type is gone, Java must insert casts when retrieving values (e.g., casting Object back to String). Furthermore, primitives must be "boxed" (e.g., int $\rightarrow$ Integer), adding runtime overhead.

---

3. Go's Hybrid: GC Shape Stenciling

Go implements a middle-ground strategy. It doesn't want the binary bloat of Rust, nor the runtime penalty of Java.

What is a "GC Shape"?

A GC shape describes how a type is viewed by the garbage collector and the memory allocator. It is defined by:

• The size of the type.
• The alignment requirements.
• The location of pointers within the type.

Mathematically, we can think of the mapping as: $\text{Type} \xrightarrow{f} \text{GC Shape} \xrightarrow{g} \text{Function Body}$

The Rules of Shaping:

• Types with the same underlying type share a shape.
• The Pointer Exception: All pointer types (regardless of what they point to) share a single, universal shape: *uint8.

How it Works in Practice

Consider this Go code:

package main
import "fmt"

type User struct{}
type Order struct{}

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

func main() {
    identity(int(0))
    identity(float64(0))
    identity(Order{})
    identity(User{})
}

The compiler follows these steps to generate the binary:

• Analyze all instantiations of identity.
• Map each type to its GC shape.
• Generate one function body per unique shape.
• Create a dictionary for every concrete type.

The Role of the Dictionary

Since multiple types (like *User and *Order) share one function body, the code needs a way to know the actual type for specific operations. Go passes a hidden dictionary argument—a read-only table containing runtime type descriptors.

Verifying the Binary

If we build the program and inspect the symbols using go tool nm, we can see this in action:

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

Example Output:

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]

• R (Read-only data): These are the four dictionaries.
• T (Text/Code): These are the three function bodies.

Because *User and *Order both map to go.shape.*uint8, they share a single implementation, effectively balancing performance and binary size.