vault

Generics Implementation Stenciling vs Dictionaries

14 min read

Generics Implementation Stenciling vs Dictionaries

When the Go team added type parameters in Go 1.18 (released 22 March 2022, per the release notes), they faced a question every generics implementation must answer: how do you turn one generic function written against an abstract type parameter into machine code that operates on concrete types? The two textbook answers — full monomorphization (stamp out a separate compiled copy per concrete type, like C++ templates and Rust) and full boxing (compile one copy that operates on uniformly heap-boxed values through a runtime dictionary, like Java erasure) — sit at opposite ends of a code-size-versus-speed trade-off. Go’s gc compiler chose neither extreme. It implements GC Shape Stenciling: it stamps out one compiled copy per distinct GC shape — a coarse equivalence class of types that share size, alignment, and pointer layout — and passes every generic function an extra hidden argument, a runtime dictionary, that carries the per-instantiation type information the shared code cannot bake in. This is the middle ground, and understanding it explains why generic Go code sometimes allocates or fails to inline where the equivalent hand-specialized code would not.

Mental Model

Think of a generic function as a recipe written with a blank ingredient. Full monomorphization photocopies the recipe once per ingredient and writes the ingredient’s name into each copy — fast to cook from, but you end up with a thick stack of nearly identical recipe cards. Full boxing keeps exactly one recipe card and, every time you cook, hands the cook a small index card (“today’s ingredient is X, here is how to measure it, here is how to compare two of it”) — one card, but every measurement is an indirection.

Go’s GC Shape Stenciling photocopies the recipe once per kind of ingredient — all powders share a card, all liquids share a card — because the parts of the recipe that depend only on physical handling (how much it weighs, where the lumps are) are identical within a kind. For the parts that genuinely differ between two powders (flour versus sugar behave differently when you taste them, not when you pour them), the cook is still handed an index card: the dictionary.

graph TD
    subgraph "Full monomorphization (C++, Rust)"
      G1["generic Min[T]"] --> M1["Min_int"]
      G1 --> M2["Min_float64"]
      G1 --> M3["Min_string"]
      M1 -.->|"fast, no indirection"| C1["large binary"]
    end
    subgraph "Full boxing (Java erasure)"
      G2["generic Min[T]"] --> B1["one Min, all args boxed"]
      B1 -.->|"every op indirect"| C2["tiny binary, slow"]
    end
    subgraph "GC Shape Stenciling (Go 1.18+)"
      G3["generic Min[T]"] --> S1["Min<ptr-shape>"]
      G3 --> S2["Min<8-byte-no-ptr-shape>"]
      S1 -->|"+ dictionary arg"| D1["dict for *User"]
      S1 -->|"+ dictionary arg"| D2["dict for *Order"]
      S2 -->|"+ dictionary arg"| D3["dict for int64"]
    end

Diagram: the three implementation strategies for one generic function Min[T]. Monomorphization produces one copy per concrete type (fast, large). Boxing produces one copy for everything (small, slow). GC Shape Stenciling produces one copy per GC shape and feeds each call a per-instantiation dictionary — the insight is that *User and *Order reuse the same compiled Min because both are pointer-shaped, while still being told apart at runtime by their dictionaries.

What a GC Shape Is

The design document — “Generics implementation - GC Shape Stenciling” in the golang/proposal repository — defines the term precisely: “The GC shape of a type means how that type appears to the allocator / garbage collector. It is determined by its size, its required alignment, and which parts of the type contain a pointer” (gcshape design doc).

Unpack the three components. Size is the number of bytes the type occupies (unsafe.Sizeof). Alignment is the byte boundary the type must start on. Pointer layout — often called the pointer map or ptr/scalar bitmap — is the per-word record of which words inside the type hold pointers; the garbage collector consults exactly this map when it scans a value (see Struct Memory Layout and Alignment and Tricolor Mark and Sweep).

Two consequences follow. First, every pointer type collapses into a single shape: *int, *User, *[]byte, chan int, map[string]int, and func() are all one machine word, word-aligned, and “the word is a pointer.” To the allocator and collector they are indistinguishable, so the compiler stencils one copy of a generic function for the entire pointer-shaped family. This is the single biggest code-size win of the scheme: a generic container instantiated with fifty different pointer element types shares one compiled body.

Second, value types are not so lucky. int64 and float64 are both 8-byte, 8-aligned, pointer-free — but they do not share a stencil, because the compiler’s actual grouping rule is narrower than the abstract “same (size, alignment, pointer-map)” definition. The implemented rule, read straight from the compiler, is: two concrete types share a GC shape if and only if they have exactly the same underlying type, or they are both (non-array-pointed) pointer types. The cmd/compile/internal/typecheck.Shapify function is explicit — its doc comment says it “takes a concrete type and a type param index, and returns a GCshape type that can be used in place of the input type and still generate identical code,” and the rule it implements is that “for now, two types are considered to have the same shape if they have exactly the same underlying type or they are both pointer types” (Shapify, cmd/compile/internal/typecheck).

So int64 and float64 differ (different underlying type), string differs from []byte, and a struct{a, b int} differs from both — each named distinctly. The design doc’s abstract size/alignment/pointer-map definition is the intuition; the compiler’s conservative “same underlying type” test is the implementation, and it is stricter — two pointer-free 8-byte types with different underlying types get separate stencils even though they are GC-indistinguishable. The pointer collapse is the one place the implementation is generous: all pointer types (excluding pointer-to-array, handled specially) map to a single shape named after a representative *uint8, so the shape names of the pointer family are go.shape.*uint8_0, go.shape.*uint8_1, and so on (the trailing index distinguishes the first vs. second type parameter of an instantiation, not the concrete type). Non-pointer shapes are named after their underlying type, e.g. go.shape.string_0 (Shapify source; the shape package is declared as go.shape in cmd/compile/internal/types/type.go, which marks any type from that package with the typeIsShape flag — “represents a set of closely related types, for generics”).

Why Not Just Monomorphize, or Just Box?

The Go team wrote three design documents on this. The first, the stenciling doc, describes full monomorphization. The second, the dictionaries doc, describes full boxing-by-dictionary. The third, the GC Shape Stenciling doc, is the implemented compromise; Go 1.18 shipped with the compromise.

Full monomorphization is the fastest at run time — each copy knows its concrete type statically, so field offsets, method calls, arithmetic, and comparisons are all direct, and the compiler’s escape analysis and inlining see ordinary concrete code. Its cost is binary size and compile time: a generic function used at twenty types becomes twenty compiled functions, and large generic libraries (sort, slices, maps, container packages) explode. C++ “template bloat” and slow C++ builds are the canonical warning.

Full boxing is the smallest — exactly one compiled copy regardless of how many types instantiate it. Its cost is speed: because the one copy must handle any type, every value is referenced uniformly (typically via a pointer), and every type-dependent operation — even reading a struct field or doing x + y — becomes an indirect call through the dictionary. It also pressures the allocator, because uniform representation usually forces values onto the heap.

GC Shape Stenciling keeps the stack layout and pointer maps statically known — which monomorphization needs and pure boxing sacrifices — by stenciling on GC shape, while keeping code size bounded by collapsing the (typically large) pointer-shaped family into one stencil. The design doc states the goal plainly: it is “a hybrid scheme that mixes some of the stenciling approach with some of the dictionary approach.”

The Runtime Dictionary

A stencil shared across many concrete types cannot know everything. Min[*User] and Min[*Order] run the same machine code, but if Min calls a method on T, or allocates a T, or compares two T values for a map[T]V, the code needs the actual type. That information arrives in the dictionary.

The design doc describes the dictionary as a compile-time-computed, read-only structure: “All dictionaries will reside in the read-only data section, and will be passed around by reference,” and “Because the dictionary is completely compile time and read only, it does not need to adhere to any particular structure. It’s just an array of bytes.” It is emitted into the binary’s read-only data segment, one per instantiation (per concrete type-argument tuple), and passed to the generic function as a hidden leading argument — analogous to how a method receives its receiver.

The doc enumerates the dictionary’s contents:

  • The instantiated types — pointers to the runtime._type descriptor (the same descriptor an interface value carries) for each type argument. This is what reflect, new(T), and type switches inside the generic body consult.
  • Derived types — runtime._type descriptors for any types the generic body constructs from its parameters, e.g. inside f[T] the type []T or map[string]T. The body needs a real type descriptor to make a slice or map of these.
  • Subdictionaries — when a generic function calls another generic function (or constructs a generic closure), the callee needs its own dictionary; that callee dictionary is computed at compile time and stored as a sub-entry of the caller’s dictionary.
  • Helper functions / itabs — entries needed to dispatch operations the shared code cannot do directly, such as the interface method tables (itabs) used when a type parameter is constrained to an interface and the body calls a method on it.

A worked sketch. Consider:

func Keys[K comparable, V any](m map[K]V) []K {
    r := make([]K, 0, len(m))   // line A
    for k := range m {          // line B
        r = append(r, k)        // line C
    }
    return r
}
  • Line A — make([]K, 0, len(m)) needs the runtime._type for []K, a derived type. The compiler precomputes a []K descriptor for each instantiation and stores it as a dictionary entry; the stencil reads the dictionary slot to call the allocator.
  • Line B — ranging a map[K]V requires the map’s type descriptor so the runtime map iterator knows key/value sizes and hash functions; that descriptor comes from the dictionary (K is comparable, so a hash and equality function for K are reachable through it).
  • Line C — append to []K again needs the []K descriptor and K’s size to copy elements; same dictionary slot as line A.

Keys[string,int] and Keys[*User,int] may run different stencils (string and *User are different shapes), but Keys[*User,int] and Keys[*Order,bool] share the pointer-shaped-key stencil and differ only in their dictionaries.

Interface-Constrained Type Parameters and Dictionaries

The dictionary is what makes constraint methods work. When a type parameter is constrained to an interface with methods —

type Stringish interface{ String() string }
 
func Join[T Stringish](xs []T) string {
    var b strings.Builder
    for _, x := range xs {
        b.WriteString(x.String())   // method call through dictionary
    }
    return b.String()
}

— the stencil cannot bake in the address of String, because T varies. The Go 1.18 dictionaries design document spells the mechanism out: a method call on a type parameter “is implemented as a conversion of the receiver to the type bound interface, and hence is handled similarly to an implicit OCONVIFACE,” and the dictionary therefore carries “any specific itabs needed for conversion to a specific non-empty interface from a type param or derived type” (generics dictionaries design). In other words the compiler places the relevant itab (interface table — the (type, method-pointer-vector) pair described in Interface Internals) in the dictionary, and the x.String() call dispatches indirectly through that itab, exactly like an ordinary interface method call. This is precisely the cost: a constraint-method call in generic code is, by default, an indirect call, not the direct (and inline-able) call a monomorphized copy would emit. Later compilers can sometimes recover the direct call: when the IR proves the concrete type at a generic instantiation, the devirtualization pass can replace the itab dispatch with a direct (and then inline-able) call, so the indirection is an upper bound, not an inevitability.

Failure Modes and Common Misunderstandings

“Generics are zero-cost like C++ templates.” They are not, under the implemented scheme. The GC Shape Stenciling design doc is explicit about the price: “Any methods called on the generic type will need to be analyzed conservatively which could lead to more heap allocation than a fully stenciled implementation. Similarly, inlining won’t happen in situations where it could happen with a fully stenciled implementation.” Because a stencil is shared across types whose behavior differs, the compiler must analyze it conservatively — escape analysis cannot prove a value stays on the stack when the method it flows into is a dictionary indirection, so it spills to the heap; and an indirect call cannot be inlined. A tight generic loop can therefore allocate and run slower than the same loop written concretely. This is a real, measurable effect, not a theoretical one.

“There is exactly one copy of my generic function.” Wrong in the other direction — there is one copy per GC shape. A generic container used at int8, int16, int32, int64, string, [3]int, and a dozen struct types produces a dozen-plus stencils. Only the pointer-shaped instantiations collapse.

“The dictionary lives on the heap / costs an allocation per call.” No. Dictionaries are compile-time constants in the read-only data segment; passing one is passing a pointer, with no allocation. The allocations the doc warns about come from conservative escape analysis of the body, not from the dictionary itself.

Diagnosing it. Build with go build -gcflags='-m' to see escape-analysis decisions (see Compiler Optimization Diagnostics); a value that escapes only in the generic instantiation but not in a hand-written specialization is the signature of this trade-off. Benchmark the generic and concrete versions side by side before assuming generics are free.

Alternatives and When to Choose Them

If a hot path measurably suffers from generic conservatism, the honest alternatives are: write the concrete version by hand for the one or two types that matter (the standard library does exactly this — sort.Ints exists alongside generic slices.Sort); use code generation (go generate) to produce monomorphized copies at build time, trading binary size for speed deliberately; or accept the cost when the code is not hot. For the overwhelming majority of code, the GC Shape scheme is the right default — the conservatism cost is paid only where a method call or allocation sits inside a generic hot loop.

Production Notes

The Go standard library’s slices, maps, and cmp packages (generic since Go 1.21) are the highest-traffic users of this machinery and are themselves a reference for what compiles well: they favor operations on the type parameter that do not require dictionary indirection (copies, comparisons of comparable/Ordered constraints handled by compiler-known helpers) over heavy constraint-method dispatch. The Go team has stated the implementation is expected to improve release over release — later compilers added devirtualization of some constraint calls and better inlining of generic functions — so the conservatism described in the 2021 design doc is an upper bound on the cost, gradually being eroded, not a fixed tax. As of the Go 1.26 baseline (released 10 February 2026, per the release announcement), the GC Shape Stenciling scheme remains the implementation; no design document has superseded it.

See Also

Graph View

Backlinks