132. Generics and trait bounds

One function, or many?

Here is a generic function in TypeScript:

function first<T>(xs: T[]): T | undefined {
  return xs[0];
}
first([1, 2]);      // T = number
first(['a', 'b']);  // T = string

From chapter 13 you know what runs: the types are erased, and one JavaScript function serves numbers, strings and everything else. Rust has the same syntax and a different answer:

fn first<T>(xs: &[T]) -> Option<&T> {
    xs.get(0)
}

<T> declares a type parameter: first works for a slice of any T, and returns a borrowed T if there is one. Call it with &[1, 2] and T is i32; with &["a", "b"], T is &str. The types are checked exactly as in TypeScript. What happens next is not erasure.

Generic types you already use

Option<T>, Result<T, E>, Vec<T> and HashMap<K, V> from the last three chapters are all generic types: one definition, with type parameters. Your own structs can have them too:

struct Column<T> {
    data: Vec<T>,
}

impl<T> Column<T> {
    fn get(&self, i: usize) -> Option<&T> {
        self.data.get(i)
    }
}

impl<T> Column<T> reads “for every T, here are methods of Column<T>”. drip-rs uses this to make its handles safe. A Gc<T> is just a u32 index into the Vec of objects of type T, but the parameter keeps them apart: a Gc<ObjClosure> can’t be used to look up a class, because indexing the heap with it gives back an ObjClosure.

Bounds: what T can do

Try a generic function that compares:

fn top<T>(xs: &[T]) -> Option<&T> {
    let mut best = xs.get(0)?;
    for x in xs {
        if x > best {
            best = x;
        }
    }
    Some(best)
}

Rust 1.97 refuses (trimmed):

error[E0369]: binary operation `>`
  cannot be applied to type `&T`
help: consider restricting type
  parameter `T` with trait `PartialOrd`

Interestingly, the TypeScript version of this function passes tsc --strict: TypeScript lets > through for any T. Rust wants to know that T can be compared, and the fix is to promise that it implements the comparison trait: fn top<T: PartialOrd>(xs: &[T]). Inside the body you may now use >, and every caller must pass a type that implements PartialOrd. Calling top with a type that doesn’t is the E0277 you met in chapter 131.

Bounds can be combined with +, and long ones move into a where clause. A real one, from engine/rust/crates/core/src/builder.rs, where the SSA builder keeps variables in HashMaps keyed by K:

impl<K> FunctionBuilder<K>
where
    K: Clone + Eq + Hash,
{ ... }

HashMap needs keys that can be compared and hashed, so the builder says so once. For a single parameter there is also a short form: fn show(p: &impl Plugin) means the same as fn show<P: Plugin>(p: &P)^[1].

fn top<T: PartialOrd>(xs: &[T])
    -> Option<&T> {
    let mut best = xs.get(0)?;
    for x in xs {
        if x > best {
            best = x;
        }
    }
    Some(best)
}

struct Column<T> {
    data: Vec<T>,
}

impl<T> Column<T> {
    fn get(&self, i: usize)
        -> Option<&T> {
        self.data.get(i)
    }
}

fn main() {
    println!("{:?}", top(&[3, 9, 4]));
    println!("{:?}", top(&[0.5, -1.0]));
    println!("{:?}", top(&["vx", "x"]));
    let e: [i32; 0] = [];
    println!("{:?}", top(&e));
    let c = Column { data: vec![1.5] };
    println!("{:?}", c.get(0));
    // Try: remove ": PartialOrd" above.
}

One copy per type

Now the difference from TypeScript. Take the Layout trait from the last chapter’s exercise, and a generic sum over one field:

fn total<L: Layout>(l: &L, buf: &[f64],
    n: usize, f: usize) -> f64 {
    let mut s = 0.0;
    for i in 0..n {
        s += buf[l.slot(i, f)];
    }
    s
}

Called with an &Aos and an &Soa, plus a total_dyn that takes &dyn Layout, then compiled with Rust 1.97 using -C symbol-mangling-version=v0 (so symbol names show type parameters) and listed with nm -C, the program contains:

g3::total::<g3::Aos>
g3::total::<g3::Soa>
g3::total_dyn
<g3::Aos as g3::Layout>::slot
<g3::Soa as g3::Layout>::slot

Two totals, one per type. One total_dyn. Step through what each copy does at its call to slot:

total(&Aos { nf: 2 }, &b, n, 1);
total(&Soa { n: 3 }, &b, n, 1);
total_dyn(&Aos { nf: 2 }, &b, n, 1);
total_dyn(&Soa { n: 3 }, &b, n, 1);

Monomorphic by construction

You have seen this trade before, from the engine’s side. In chapter 64 an inline cache that has seen one shape is monomorphic, and Maglev turns such an access into one shape check and a plain load at a fixed offset^[3]. V8 has to discover that a site is monomorphic by watching it run, and must keep a check in case a new shape arrives.

Inside total::<Aos>, the call l.slot(i, f) can only ever reach Aos::slot. The site is monomorphic by construction, known before the program runs, so there is nothing to check and nothing to deoptimize. total_dyn is the other case. Its one call site sees whatever vtable it is handed, like a polymorphic site, and has no feedback to specialize on: it loads a function pointer and calls it^[2].

So which should you write? Generics give each type its own fast copy, at the cost of more machine code and one copy per type to compile. dyn gives one copy and lets one Vec hold many types, at the cost of an indirect call. A plugin registry, a list of GC roots or anything decided at run time wants dyn. A hot loop over one known type wants generics. This chapter hasn’t timed the two, so it makes no speed claim; chapter 142 shows how to measure such things properly.

Your turn

trait Layout {
    fn slot(&self, i: usize, f: usize)
        -> usize;
}

struct Aos {
    nf: usize,
}

struct Soa {
    n: usize,
}

impl Layout for Aos {
    fn slot(&self, i: usize, f: usize)
        -> usize {
        i * self.nf + f
    }
}

impl Layout for Soa {
    fn slot(&self, i: usize, f: usize)
        -> usize {
        f * self.n + i
    }
}

fn total<L>(l: &L, buf: &[f64],
    n: usize, f: usize) -> f64 {
    todo!()
}

fn argmax<T: PartialOrd>(xs: &[T])
    -> Option<usize> {
    todo!()
}

What you learned

• Generics put type parameters on functions, structs and impls. Option<T>, Vec<T> and HashMap<K, V> are generic types.
• A trait bound like T: PartialOrd lets the body use the trait, and makes callers supply it. Combine with +; move long ones to where.
• Monomorphization makes one copy per concrete type: nm showed total::<Aos> and total::<Soa>.
• Each copy’s calls are monomorphic by construction; a dyn call site takes whatever vtable it gets.
• Viscosity’s Rust compile is generic over P: LanguagePlugin; drip-rs mixes generic impls with &dyn Trace.