Write fn largest<T>(list: &[T]) -> &T once and use it on integers and on characters. The source has one definition. The machine has no idea what a type parameter is. Somewhere between those two facts a compiler has to decide whether the running program contains one copy of that function or several, and that decision, made once at the language-design level, ripples out into binary size, compile time, inlining, and what your program can ask about its own types while it runs.
The theory of the abstraction lives in parametric polymorphism. This note is about the implementation fork underneath it.
The idea
There are two ways to compile a generic definition. Monomorphization generates a separate specialized copy for every concrete type the code is used at, which erases the abstraction before runtime and costs compile time and code size. Erasure keeps one copy by throwing the type parameters away and inserting casts, which costs runtime representation (the types are gone, so you cannot inspect them) and forbids specializing on them. Rust and C++ pay at build time; Java pays at run time. The non-obvious part is that this choice, not the syntax, is what determines whether generic code can be as fast as hand-written code and whether template libraries have to ship as headers.
Monomorphization: the compiler duplicates the code for you
Rust compiles generics by monomorphization, which the Book defines as the process of turning generic code into specific code by filling in the concrete types used when compiled. The compiler looks at every place generic code is called and generates code for the concrete types it is called with. The standard library’s Option<T> is the canonical demonstration: given one Some(5) and one Some(5.0), the compiler identifies two kinds of Option<T>, one at i32 and one at f64, and expands the generic definition into two specialized definitions, roughly as if Option_i32 and Option_f64 had been written by hand.
The payoff is the zero-cost claim, and it is a real one: because each instance specifies its type, there is no runtime cost for using generics, and the code performs as it would if you had duplicated each definition by hand. Every call is a direct call on a concrete type, so it inlines, and the optimizer sees ordinary non-generic code.
The bill arrives at build time. Each instantiation is real code that has to be compiled and stored, so a generic-heavy program grows in both compile time and binary size roughly with the number of distinct type instantiations, not the number of source definitions.
C++ templates: the same strategy, with the build system exposed
C++ templates are the older instance of the same idea, and cppreference makes the mechanics explicit. A template specialization is instantiated (the code for it is actually compiled) when it is referenced in a context requiring a complete object type or a function definition, unless it was already explicitly specialized or instantiated. Instantiating a class template does not instantiate its member functions unless they are also used, so you pay only for what you call. And at link time, identical instantiations generated by different translation units are merged, which is the linker cleaning up after the duplication the model creates.
The consequence C++ programmers feel most is architectural. The definition of a class template must be visible at the point of implicit instantiation, which is why template libraries typically ship all their definitions in headers, and why much of Boost is header-only. Templates break the ordinary declaration-in-header, definition-in-source split, because the compiler cannot generate a specialization from a declaration alone. C++ once had an export modifier meant to fix exactly this, letting files instantiate exported templates without including their definitions; cppreference records that implementations were rare and disagreed with each other on details. The feature is gone, and the header-only convention is what remains.
That is the deeper reason template-heavy C++ builds are slow. It is not compiler inefficiency, it is that the entire generic body is re-parsed and re-instantiated in every translation unit that uses it, and the redundancy is only collapsed at the very end, at link.
Erasure: keep one copy, drop the types
Java went the other way, for a reason that is not really about performance: it needed generics to arrive on a platform whose bytecode and existing libraries predated them. Its compiler applies type erasure, which the Java Tutorials describe as replacing all type parameters in generic types with their bounds, or with Object if the parameters are unbounded, so the produced bytecode contains only ordinary classes, interfaces, and methods. Casts are inserted where needed to preserve type safety, and bridge methods are generated to preserve polymorphism in extended generic types.
The stated payoff is direct: type erasure ensures that no new classes are created for parameterized types, so generics incur no runtime overhead. Note carefully what “no runtime overhead” means here. It means no per-instantiation class explosion, not that a generic collection is as fast as a specialized one. It is a different sense of the same phrase Rust uses, which is exactly why the two communities can both claim zero cost while meaning opposite things.
What erasure gives up is the type at runtime. Once the parameter is Object in the bytecode, no operation can recover it, which is where the rule that you cannot ask a List<String> what its element type is comes from. Generic type information exists at compile time for checking and is not there afterward.
"Zero cost" always names a cost that has been moved, not removed
Monomorphization is zero cost at runtime and expensive at build time and in binary size. Erasure is zero cost in class count and pays in lost runtime type information and in the boxing and casting the single shared implementation needs. When a language advertises a zero-cost abstraction, the useful follow-up question is which resource absorbed the cost.
The third position
Dynamically typed languages sit off this axis rather than at one end of it, because there is no compile-time type parameter to either duplicate or erase; the garden covers that model under duck typing in parametric polymorphism and abstract data types. The same fork also shows up one level up in how a language resolves a generic constraint to an implementation, which is the dictionary-passing versus monomorphization contrast in type classes and traits.
Related Notes
- Parametric Polymorphism and ADTs - the theory of the abstraction these strategies implement
- Type Classes and Traits - dictionary passing versus monomorphization for constraint resolution
- Modules, Signatures, and Separate Compilation - the separate-compilation model templates break
- Build Systems and Dependency Management - where instantiation-driven build time actually shows up
- Compilation vs Interpretation - what “at compile time” buys and costs in general
Sources
- “Generic Data Types,” The Rust Programming Language (official book). https://doc.rust-lang.org/book/ch10-01-syntax.html . Supports monomorphization as turning generic code into specific code by filling in concrete types at compile time, the compiler generating code for every concrete type a generic is called with, the
Option<T>expansion intoi32andf64specializations, and the claim of no runtime cost because the result performs as if each definition had been duplicated by hand. - “Templates,” cppreference.com. https://en.cppreference.com/w/cpp/language/templates.html . Supports instantiation happening when a specialization is referenced in a context requiring a complete type or definition, member functions of a class template not being instantiated unless used, identical instantiations from different translation units being merged at link time, template definitions needing to be visible at the point of implicit instantiation (hence header-only libraries such as most of Boost), and the removed
exportmodifier being rarely and inconsistently implemented. - “Type Erasure,” The Java Tutorials (Oracle). https://docs.oracle.com/javase/tutorial/java/generics/erasure.html . Supports erasure replacing type parameters with their bounds or
Objectwhen unbounded, the resulting bytecode containing only ordinary classes and methods, inserted casts preserving type safety, generated bridge methods preserving polymorphism, and the claim that no new classes are created for parameterized types so generics incur no runtime overhead.