Compile-Time Specialization

Dynamic dispatch. A &dyn FeeModel is a fat pointer: a data pointer plus a pointer to a vtable, a static table generated per (type, trait) pair. In current rustc, the vtable starts with the drop function, size and alignment, followed by the trait's methods. That layout is an implementation detail, not a guarantee. A call loads the vtable pointer, loads the function pointer from it, and makes an indirect call. On x86-64 that typically looks like call qword ptr [rax + 24].

The indirect call itself isn't the main cost. When the target is predictable (one concrete type behind the pointer, called repeatedly), the CPU's branch target buffer predicts it and the call costs a few cycles more than a direct one. A misprediction costs a pipeline flush, roughly 15–20 cycles on recent x86 cores, the same as any mispredicted branch. The real cost is what the compiler can't do across an opaque call: inline the body, propagate constants into it, hoist loop-invariant work out of it, keep values in registers across it, or vectorise a loop that contains it.

Static dispatch. A generic fn total<M: FeeModel>(m: &M, …) is monomorphised: the compiler makes a separate copy for every concrete M it's used with. Inside each copy the call is direct, almost always inlined, and the loop body becomes plain arithmetic the optimiser can work on. You pay with code size (one copy per type) and compile time.

Enum dispatch. When the set of types is closed and known (three fee models, two book implementations), an enum with a match gives you one copy of the calling code with direct, inlinable calls in each arm. The match compiles to a compare chain or a jump table on the discriminant. For a small set this is often nearly as fast as generics, with no code multiplication. The catch is that adding a type means editing the enum.

Dispatch microbenchmarks mislead in two predictable ways.

The compiler devirtualises. If the concrete type behind a &dyn is visible at the call site (you built the Box three lines up), LLVM can turn the indirect call into a direct one and inline it, and your "dyn" benchmark measures static dispatch. Hide the type: pass the trait object through std::hint::black_box, construct it in a separate #[inline(never)] function, or select it from runtime input.

The predictor is perfect. A loop that calls the same dyn method on the same object a million times is a monomorphic call site. The indirect branch is predicted every time, so all you measure is the lost inlining. Real engines often have polymorphic call sites: different order types, different instruments' policies. Modern indirect-branch predictors use history and can learn short repeating patterns, but data-dependent sequences defeat them. Measure both cases.

In the drill you'll implement three fee models (the kind of per-fill calculation an exchange or a broker runs millions of times a day) and total them through static dispatch, a monomorphic dyn call, a polymorphic dyn call and an enum. The harness checks correctness and reports nanoseconds per fill. On one x86-64 machine in release mode, the static loop came in around 3 ns per fill, monomorphic dyn around 5, polymorphic dyn around 12, and the polymorphic enum around 3.4. Your numbers will differ. In debug mode, which is the Playground's default, everything collapses to the same slow speed, because nothing is inlined anywhere. Run it both ways if you can, and explain the gaps before you move on.

pub trait FeeModel {
    fn fee(&self, qty: u64, px: u64) -> u64;
}

/// Fixed fee per fill.
pub struct Flat(pub u64);

/// Basis points of notional (qty * px), rounded down. Notional can exceed
/// u64::MAX: compute it in u128.
pub struct Bps(pub u64);

/// `low` bps when notional <= cutoff, `high` bps above it.
pub struct Tiered {
    pub cutoff: u64,
    pub low: u64,
    pub high: u64,
}

impl FeeModel for Flat {
    fn fee(&self, _qty: u64, _px: u64) -> u64 {
        todo!()
    }
}

impl FeeModel for Bps {
    fn fee(&self, qty: u64, px: u64) -> u64 {
        todo!()
    }
}

impl FeeModel for Tiered {
    fn fee(&self, qty: u64, px: u64) -> u64 {
        todo!()
    }
}

/// A closed set of models: dispatch by `match`, which the compiler can inline.
pub enum AnyFee {
    Flat(Flat),
    Bps(Bps),
    Tiered(Tiered),
}

impl FeeModel for AnyFee {
    fn fee(&self, qty: u64, px: u64) -> u64 {
        todo!()
    }
}

/// Static dispatch: monomorphised per model, `fee` inlinable into the loop.
pub fn total_static<M: FeeModel>(m: &M, fills: &[(u64, u64)]) -> u64 {
    todo!()
}

/// Dynamic dispatch: one indirect call per fill through the vtable.
pub fn total_dyn(m: &dyn FeeModel, fills: &[(u64, u64)]) -> u64 {
    todo!()
}

/// Fill i is charged by models[i % models.len()]: a polymorphic call site.
pub fn total_dyn_mixed(models: &[Box<dyn FeeModel>], fills: &[(u64, u64)]) -> u64 {
    todo!()
}

/// Same, through the closed enum.
pub fn total_enum_mixed(models: &[AnyFee], fills: &[(u64, u64)]) -> u64 {
    todo!()
}

struct Ring<T, const N: usize> { buf: [T; N], … } makes the capacity part of the type. Three things improve at once:

1. Storage is inline. [T; N] lives inside the struct: no heap allocation, no pointer to chase, and the ring can sit in a cache-aligned struct next to its indices (or on the stack).
2. Arithmetic becomes immediate. i & (N - 1) compiles to and with a constant. A runtime i % cap compiles to a hardware div. Agner Fog's instruction tables list 64-bit division latency at tens of cycles on many x86 cores (roughly 35–90 cycles on Skylake-era Intel, much less on recent Intel and AMD cores). Even a constant that isn't a power of two is better than a runtime value: the compiler replaces % 1000 with a multiply by a magic reciprocal, a handful of cycles.
3. Bounds checks disappear. With N constant, the compiler can prove i & (N - 1) < N, so self.buf[i & Self::MASK] needs no bounds check. With a Vec and a runtime mask, it can't, and the compare-and-branch to the panic path stays in your hot loop.

You can also enforce invariants at compile time. An associated constant that asserts is evaluated when the type is instantiated, so Ring<u64, 6> stops compiling instead of misbehaving at runtime:

impl<T: Copy + Default, const N: usize> Ring<T, N> {
    const MASK: usize = {
        assert!(N.is_power_of_two(), "Ring capacity must be a power of two");
        N - 1
    };
}
// Since Rust 1.79 an inline `const { assert!(...) }` block in a function works too.

This is a post-monomorphisation error: it fires only when a function that uses MASK is instantiated with a bad N. That's why the drill's new touches Self::MASK explicitly.

The limits are real. Const generics can't (on stable) be computed from other const parameters in type positions (no [T; N * 2] in a struct field), every distinct N is another copy of the code, and a capacity chosen from configuration at start-up can't be a const generic at all. For those, enforce a power of two at runtime and keep a runtime mask. You get most of the arithmetic win, and you keep the bounds check.

/// Fixed-capacity FIFO whose capacity is part of the type.
pub struct Ring<T: Copy + Default, const N: usize> {
    buf: [T; N],
    head: usize, // free-running read index
    tail: usize, // free-running write index
}

impl<T: Copy + Default, const N: usize> Ring<T, N> {
    /// Evaluated once per instantiation, at compile time: Ring<u64, 6>
    /// fails to build as soon as a method that uses MASK is instantiated.
    const MASK: usize = {
        assert!(N.is_power_of_two(), "Ring capacity must be a power of two");
        N - 1
    };

    /// Touch Self::MASK here so a bad N fails even if push/pop are unused.
    pub fn new() -> Self {
        todo!()
    }

    pub const fn capacity() -> usize {
        N
    }

    pub fn len(&self) -> usize {
        todo!()
    }

    pub fn is_empty(&self) -> bool {
        self.len() == 0
    }

    /// Err(v) hands the value back when full.
    pub fn push(&mut self, v: T) -> Result<(), T> {
        todo!()
    }

    pub fn pop(&mut self) -> Option<T> {
        todo!()
    }
}

/// The same queue with its capacity chosen at runtime (any value >= 1).
/// Change the fields if you prefer another representation.
pub struct DynRing<T: Copy + Default> {
    buf: Vec<T>,
    head: usize,
    len: usize,
}

impl<T: Copy + Default> DynRing<T> {
    pub fn new(cap: usize) -> Self {
        todo!()
    }

    pub fn capacity(&self) -> usize {
        self.buf.len()
    }

    pub fn len(&self) -> usize {
        todo!()
    }

    pub fn push(&mut self, v: T) -> Result<(), T> {
        todo!()
    }

    pub fn pop(&mut self) -> Option<T> {
        todo!()
    }
}

LLVM's inliner decides most inlining with a cost model. Your levers:

• #[inline] is a hint, but for non-generic functions it does something more important: it makes the function's body available to other crates so they can inline it. Without it (and without LTO), a small accessor in your book crate can't be inlined into engine. Generic functions don't need it, because they're instantiated in the calling crate anyway.
• #[inline(always)] is a strong request. It's usually honoured, but it isn't a guarantee (recursion, for example). Use it sparingly, on tiny functions you've measured.
• #[inline(never)] keeps cold code out of hot functions (next week's topic), gives benchmarks a stable boundary, and makes a function show up by name in the assembly and in profiles.
• LTO (lto = "fat" or "thin") and codegen-units = 1 in the release profile let LLVM see across crate and codegen-unit boundaries. They often give a measurable win for an engine split across crates, at the cost of build time.

Every monomorphised copy is real machine code. An engine generic over three parameters, instantiated with two types each, compiles its hot path up to eight times if all combinations are used. Measure it: cargo llvm-lines counts LLVM IR lines per generic function (a good proxy for compile-time cost), and cargo bloat shows bytes per function in the binary. A common fix is the "generic shell, concrete core" pattern: a thin generic function converts its argument and calls a non-generic inner function holding the bulk of the logic. The standard library does this in many places, for example functions that take impl AsRef<Path>.

Use Compiler Explorer for small experiments (pick rustc, add -C opt-level=3, and -C target-cpu=native if you deploy that way) and cargo asm (cargo-show-asm, from week 1) for real crates. Mark the function you're studying #[inline(never)] so it exists as a symbol. Then go through the checklist:

1. Calls. Are the trait methods and accessors you expected to inline gone? Any call left in the loop is a boundary the optimiser couldn't cross.
2. Indirect calls. call qword ptr [reg + offset] or call reg means dynamic dispatch survived, perhaps through a dyn you forgot about or a function pointer in a struct.
3. Bounds checks. A cmp followed by a jae or jb to a block that calls core::panicking::panic_bounds_check. One per loop (hoisted) is fine. One per element means the compiler couldn't prove your indices.
4. Divisions. div or idiv in a loop is tens of cycles each. Check whether a constant or power-of-two capacity would let it become a shift, an and or a multiply.
5. Vectorisation and spills. Packed instructions on xmm/ymm registers mean the loop vectorised. Lots of moves to and from [rsp + …] mean register pressure, often caused by a call in the loop.

Sketch the engine's type before you write it. A shape that works:

pub trait OrderBook { fn add(&mut self, o: &Order) -> AddResult; fn cancel(&mut self, id: OrderId) -> bool; /* ... */ }
pub trait RiskPolicy { fn check(&mut self, o: &Order) -> Result<(), Reject>; }

pub struct Engine<B: OrderBook, R: RiskPolicy, const MAX_EVENTS: usize> {
    book: B,
    risk: R,
    events: EventBuf<MAX_EVENTS>,
}

pub type ProdEngine = Engine<LadderBook, PreTradeRisk, 64>;   // what you ship
pub type DynEngine  = Engine<Box<dyn OrderBook>, Box<dyn RiskPolicy>, 64>; // the comparison

For the dyn twin to exist, both traits must be object-safe (dyn compatible): no generic methods, no Self by value in arguments or returns. Methods that need generics get where Self: Sized and stay off the object. Implement the traits for Box<dyn …> (forwarding impls) so one Engine definition serves both instantiations. That way the two versions differ only in dispatch.

The repo draws the line a little differently:

• Engine<B: OrderBook> has been generic over the book since week 7. The book crate implements OrderBook for Box<B>, so Engine<Box<dyn OrderBook>> already works.
• Guarded<B, R>. The risk policy goes in a wrapper instead of a third parameter on Engine. Guarded holds an Engine<B> and an R: RiskPolicy, so Engine's struct and constructors stay as earlier weeks left them. DynGuarded is Guarded<Box<dyn OrderBook>, Box<dyn RiskPolicy>>.
• RiskPolicy. check(&self, order, reference: Price) -> Result<(), RejectReason> is read-only. The hooks on_accept and on_event, which do nothing by default, keep a stateful policy in sync. A risk reject is the single event Rejected, and the order never reaches the engine, so it gets no engine sequence number.
• Policies. NoRisk, which compiles to nothing; MaxOrderQty<const MAX: u64>, one compare against an immediate; and week 15's risk::RiskEngine.