Static vs dynamic dispatch, measured

“dyn is slow.” You have heard it. It is folklore, and the folklore is wrong twice over — once by overstating the cost, and once by naming the wrong cause.

Here are three measurements taken with this toolchain, rustc -O, on the same machine, median of several runs.

Identical. Both times. The optimiser saw exactly one implementor at each call site, devirtualised the call, inlined it, and the dyn disappeared before a single instruction was emitted.

Now the same experiment with the implementation chosen from data the compiler cannot see:

3.6×. So the rule is not “dyn is slow”. The rule is:

An unpredictable indirect call inside a hot loop is slow.

Unpredictable, because the CPU’s indirect-branch predictor must guess the target; inside a loop, because that guess is paid per element; and indirect, because a vtable load stands between the call and its destination. Remove any one of those three words and the cost mostly evaporates. Being able to say that precisely is the difference between repeating folklore and knowing the machine.

Why this problem is shaped the way it is

pub fn apply_pipeline(ops: &[String], data: &[u64]) -> Vec<u64>

The operation names arrive as input. The compiler therefore cannot know which operation runs, cannot devirtualise, and cannot inline — the opacity is real, not simulated. Any problem about dispatch cost that does not force opacity through its input will measure nothing at all.

Each String in ops is "name:arg":

• add:n → x.wrapping_add(n)
• mul:n → x.wrapping_mul(n)
• xor:n → x ^ n
• rotl:k → x.rotate_left(k % 64)
• shr:k → x >> (k % 64)
• anything else → identity

Apply the ops left to right to every element of data, independently, and return the results in order. n is parsed as a u64; a malformed argument parses as 0. An empty ops list returns data unchanged.

Note the arithmetic is wrapping_*. This is compiled with -O, so overflow checks are off and plain + would silently wrap anyway — but saying wrapping_add says you meant it, and keeps the code correct if it is ever compiled in debug.

What “fast” looks like here

A Vec<Box<dyn Fn(u64) -> u64>> is a perfectly correct answer and it is the slow one: one heap allocation per op, a vtable pointer chased per element per op, and no inlining. The reference resolves the names once into a small enum and matches it inside the loop. The match arms are all visible to the optimiser, so it can hoist, unroll and even vectorise them.

You will not be able to observe the gap in the small test cases. The last case runs two million elements through four operations; that is where it shows.

Two lints worth knowing before you start

• borrowed_box. &Box<dyn Trait> is a pointer to a pointer to a pointer. Use &dyn Trait. Measured, in this exact microbenchmark: &Box<dyn Trait> 0.0710 ms versus &dyn Trait 0.0589 — a genuine 20% for deleting one word.
• ambiguous_wide_pointer_comparisons (a rustc lint; clippy’s old vtable_address_comparisons was renamed into it and uplifted). Comparing two &dyn Trait with == compares both halves of the fat pointer, and vtable addresses are not stable — the same type can have two vtables, and two types can share one. Use std::ptr::eq on thin pointers instead.

And the other side of the ledger

dyn has a genuine compile-time benefit: one copy of the code instead of one copy per instantiated type. Generics are fast to run and slow to build. The trade is not one-directional, and the next two items are about exactly that.

Remember the grade is compile + tests + clippy -D warnings.