Erasure and Reification of Generic Types

A generic function is written once and applied at many types. The compiler must decide what the function looks like after translation: one machine-code body shared by all instantiations, or one per instantiation, or a body that carries type information at run time. Each choice determines what the program can ask about types, what it costs in code size, and which operations are legal inside a generic definition. Those three consequences are not separable, and languages that try to have all three pay for it in other ways.

Erasure: types exist only during checking

The erasure translation removes type parameters before generating code. A parameterized type List<T> becomes List, and every type argument is dropped. A generic method T id(T x) becomes a method taking and returning Object, with casts inserted at call sites.

// source
List<String> names = new ArrayList<String>();
names.add("x");
String first = names.get(0);

// after erasure
List names = new ArrayList();
names.add("x");
String first = (String) names.get(0);

The cast is the entire runtime effect of the type argument. The compiler knows, from the static type, that get(0) returns a String, and it inserts a checkcast so that a heap that has been corrupted by an unchecked operation fails at the point of use rather than silently producing a mis-typed reference.

The bridge method is the second artifact. When a class implements a generic interface and provides a method whose erased parameter type is more specific than the interface’s, the signatures do not match, and the compiler emits a synthetic bridge that delegates with a cast:

class StringBox implements Box<String> {
    public void put(String s) { ... }
}

// erased view
class StringBox implements Box {
    public void put(String s) { ... }          // the real method
    public void put(Object o) { put((String) o); }   // bridge, synthetic
}

The bridge exists so that a call through the interface’s erased signature reaches the real method. Its cost is one extra indirection and one cast on the dispatch path, and it appears in stack traces and in reflection output, which is a recurring source of confusion when a method seems to exist twice.

What erasure makes impossible

The erased representation is why new T[], instanceof List<String>, and T.class are not legal in Java. All three would require the type argument at run time, and erasure has removed it.

The array creation case is the sharpest. new T[n] cannot be compiled because the runtime must allocate an array whose element type is known to the garbage collector and to the array store check. A workaround exists — allocate Object[] and cast — but its runtime component type is Object, not the erased type parameter, so a subsequent store of any value through that array reference can succeed where a store into an array of the intended component type would have thrown ArrayStoreException. The unchecked warning the compiler emits at the allocation is the only indication that the type system’s guarantee has been weakened at that point.

The instanceof case is subtler. x instanceof List is legal and checks only the raw type. x instanceof List<String> is rejected because the check would have to compare type arguments that do not exist at run time. The consequence is that a generic method cannot dispatch on its type argument, so a generic algorithm that needs different behaviour for different element types must take a function or a strategy object rather than inspect the type.

Wildcards partially compensate. List<?> is a type whose argument is unknown, and it is legal because it requires no runtime information. The variance rules that come with wildcards — ? extends T for reading and ? super T for writing — are the use-site form of the variance annotations described in structural subtyping and variance. A wildcard is erased too, but the compiler records its bound and uses it for checking, so List<? extends Number> accepts reads as Number and rejects writes. The type argument is gone at run time, but the constraint it imposed survives in the checker.

Reification: types that survive translation

A reified type is one that exists at run time as a value the program can inspect. .NET’s runtime represents a generic instantiation as a constructed type object, so typeof(List<string>) is a distinct value from typeof(List<int>), and reflection can enumerate the type arguments.

Reification makes the three rejected operations legal. An array of a generic element type can be allocated because the runtime knows the element type — new T[n] is legal in C# precisely because the array’s component type is part of its runtime representation. An instanceof check can compare constructed types. A generic method can create instances of its type parameter if the parameter is constrained to have a constructor.

The cost is that the runtime must represent and manipulate type arguments. Each distinct instantiation of a generic type is a distinct runtime type, and each is initialized separately: static fields of a generic type are per-instantiation, so Counter<int>.count and Counter<string>.count are different variables. That is a semantic difference from erasure, not merely an implementation detail, and it is observable in programs that rely on shared static state.

Reification also makes generic code slower to start. The first use of List<SomeStruct> must construct the runtime type, lay out its fields for that element type, and compile or JIT any code specialized for it. For value types the layout is not shared with the reference-type instantiation: List<int> may hold its elements inline, as a struct field array rather than a reference, while a List<object> is an array of references, so the two cannot share one implementation of the element accessors and the runtime generates code per value-type instantiation.

Monomorphization: one copy per instantiation

The third strategy duplicates the generic function at compile time, once per distinct set of type arguments, and lets the ordinary optimizer work on each copy. C++ templates and Rust generics both work this way, and so does the specialization path in many JITs.

Monomorphization gives the best code. Each copy sees concrete types, so field offsets are constants, calls are direct, and values of primitive type stay unboxed. A generic max over i32 compiles to the same instructions a hand-written max_i32 would.

The cost is code size, and it is unbounded in principle. A generic function applied at n distinct type arguments produces n copies. If the function is itself generic over a type that is generic, the number of instantiations is the product, and a deeply nested generic program can produce exponential code. Compilers mitigate this with heuristics: instantiate eagerly for types used directly, defer for types only reachable through other generics, and share copies when the layout is identical. Sharing is only sound when the emitted code does not depend on the type’s size or alignment, which holds for a family of instantiations that are all pointer-shaped and does not hold once a value type of a different size enters the family.

Monomorphization also interacts badly with separate compilation. A generic function’s body must be available at the instantiation site, so it must be shipped in a form the consumer can instantiate — a template definition in a header, or an intermediate representation in the object file. A language that compiles modules independently and links binaries must therefore either ship bodies or accept that instantiation happens at link time. Rust ships the generic function’s MIR in the library’s metadata and instantiates in the downstream crate; C++ ships the template body in the header. The alternative that avoids both the duplication and the header requirement is the dictionary translation, whose coherence conditions are covered in type classes as dictionary passing.

There is a diagnostic consequence too. A type error inside a generic function is reported at the instantiation site, with a call stack that points into the caller rather than the definition. The error message names the concrete types, which is often more useful than the abstract ones, but the location is misleading.

Dictionary passing as a middle path

A different strategy passes operations rather than types, as described in type classes as dictionary passing. The generic function is compiled once, with an extra parameter carrying the operations it needs, and the caller supplies the appropriate dictionary. This is what Haskell does for type classes and what Swift does for protocols with generic requirements. Go’s early generics implementation took a hybrid of this and monomorphization: the compiler emitted one specialized copy per GC shape — the coarse grouping of type arguments that the garbage collector treats alike, so that every pointer type and every distinct scalar size and alignment share a shape — and passed a dictionary supplying the operations the body needs, so distinct type arguments could share a single compiled body without a full instantiation each. Later versions of the toolchain add full monomorphization for the instantiations whose bodies it can see at the use site, keeping the shape-based copy as the fallback for the rest.

Code size is one copy per function rather than one per instantiation, so the exponential blowup disappears. The cost is an indirect call through the dictionary for every operation, which blocks inlining and specialization unless the compiler can see the dictionary at the call site. Compilers that do whole-module optimization can specialize when the dictionary is statically known, recovering much of what monomorphization would have given while keeping one copy for the general case.

The middle path also preserves separate compilation, because the function’s body is compiled once and the dictionary is an ordinary value, rather than the body being replicated into every monomorphized copy at the use site.

Choosing, and the consequences of mixing

The strategies are not interchangeable, and a language that mixes them must specify exactly where each applies.

Erasure cannot coexist with reification for the same type, because the runtime representation is either present or not. A language can erase some types and reify others — Java erases generic type arguments but reifies arrays and classes — and the boundary between the two is where unsoundness lives. Every unchecked cast in Java sits at that boundary.

Monomorphization can coexist with erasure if the monomorphized copies are only an optimization: the erased version is the semantics, and the specialized version must behave identically. That is the usual arrangement in a JIT, which compiles generic code once against the boxed representation and then emits type-specialized versions for the call sites it has observed, falling back to the general version when a new type arrives. It fails when specialization changes observable behaviour, which is exactly what happens when a program can ask about its own type arguments.

The practical rule is that the strategy is determined by what the language promises the programmer. If generic code can inspect type arguments, the representation must carry them. If it cannot, the cheapest representation is no representation, and the casts inserted by the compiler are the price of presenting a typed interface over an untyped runtime.