Generics, Monomorphization & Machine Code Generation

Generics allow software engineers to write reusable, abstract algorithms over placeholder types. While interpreted languages handle generics through dynamic dictionary lookups and Java uses type erasure with object boxing, Rust evaluates generics via Monomorphization.

Monomorphization produces zero runtime performance penalty, generating specialized machine code tailored directly to target CPU hardware registers.

1. The Monomorphization Engine#

During compilation, rustc analyzes the program call graph to discover every concrete type used with a generic function or struct. It then synthesizes an independent, specialized copy for each concrete type:

Mathematical Formalization#

Let $G(T)$ represent a generic function parameterized over type $T$, and let $C = \{T_1, T_2, \dots, T_k\}$ be the set of concrete types instantiated across the crate codebase. Monomorphization maps $G(T)$ into $k$ distinct specialized functions:

Because each specialized function $G_{T_i}$ is a concrete function with known types, calling it incurs zero runtime overhead:

2. Inlining and Compiler Vectorization#

Because concrete types and memory layouts are fixed at compile time, the LLVM optimizer can inline generic functions directly into the calling site:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// Generic scalar accumulator
fn sum_slice<T: std::ops::Add<Output = T> + Copy>(slice: &[T], initial: T) -> T {
    let mut acc = initial;
    for &item in slice {
        acc = acc + item;
    }
    acc
}

fn main() {
    let ints = [1, 2, 3, 4, 5];
    let floats = [1.1, 2.2, 3.3, 4.4, 5.5];

    // LLVM generates two distinct, fully vectorizable machine routines:
    let total_int = sum_slice(&ints, 0);       // Uses integer ALU instructions
    let total_float = sum_slice(&floats, 0.0); // Uses SIMD vector registers
}

3. The Trade-off: Binary Size Bloat#

While monomorphization delivers blistering execution performance, it presents an engineering trade-off: Executable Code Bloat.

The total binary size expansion $B$ scales with the number of unique type instantiations:

If a large generic function is instantiated across 50 different concrete types, the compiler produces 50 separate machine code copies. This increases compilation latency and can saturate the CPU's hardware Instruction Cache (I-cache), leading to instruction cache misses in extreme cases.

4. Concept Verification#

Test your understanding of generics and compiler monomorphization: