Static vs dynamic dispatch

Rust can call a trait method in two ways.

• Static dispatch. A generic function such as fn run<F: Op>(f: &F) is compiled separately for each concrete type it is used with (this is called monomorphization). Inside each copy the compiler knows exactly which method runs, so it can call it directly and usually inline it.
• Dynamic dispatch. A trait object such as &dyn Op or Box<dyn Op> is a fat pointer: a pointer to the value plus a pointer to a vtable, a table of function pointers for that type. A method call loads the function pointer from the vtable and calls through it. One compiled copy of the calling code works for every type.

"dyn is slow" is an oversimplification. The indirect call itself is usually cheap. The larger costs tend to come from what it prevents: the compiler generally cannot inline a function it cannot identify, so it also loses the optimizations that inlining enables, such as constant folding or vectorizing a loop. When the processor cannot predict which target an indirect call will jump to, mispredictions add further cost. In the other direction, when the optimizer can prove which concrete type is behind a trait object, it may devirtualize the call and turn it back into a direct one, so dyn in the source does not always mean an indirect call in the machine code. Which form runs faster in a given program is something to measure, not assume.

Generics have costs too. Each instantiation is compiled separately, which can increase build time and binary size. Trait objects avoid that duplication and let one collection hold values of different types.

The exercise

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

The operations are named in the input, so the compiler cannot know at compile time which ones will run. That is the situation where the choice between a trait object and a closed set of cases matters.

Each string in ops describes one operation. Split it at the first :. The text before the colon is the name and the text after it is the argument. If there is no colon, the whole string is the name and the argument is 0.

The argument n is parsed the way str::parse::<u64> parses it: an optional leading + followed by one or more ASCII decimal digits, with a value no larger than u64::MAX. Any other argument parses as 0. That includes an empty argument, surrounding spaces, a minus sign, 0x prefixes, underscores, a second colon (add:1:2 has the argument 1:2) and values that overflow.

Names are matched exactly and are case-sensitive:

"Anything else" includes the empty name, ADD, and names with spaces, such as " add". Apply the operations left to right to each element of data independently and return one result per element, in the original order. An empty ops list returns a copy of data, and an empty data returns an empty vector.

For example, with ops = ["add:7", "xor:255", "nope:3"] the element 1 becomes 1 + 7 = 8, then 8 ^ 255 = 247, and the unknown nope leaves it at 247.

Overflow and shift amounts

wrapping_add and wrapping_mul wrap around modulo 2^64 in every build. A plain + or * would panic on overflow when overflow checks are enabled (the default in debug builds) and wrap only when they are disabled, so the wrapping_* methods give the same answer everywhere.

>> by 64 or more is an overflow: it panics when overflow checks are enabled, and otherwise the shift amount is masked to its low six bits. Reduce the argument with % 64 while it is still a u64, then convert it to the u32 that rotate_left and >> expect. (rotate_left itself accepts any u32 and does not panic.)

What the tests check

Each test supplies ops, a length n and a seed. The harness generates n pseudo-random u64 values from the seed, calls your function, and reports the output length, the first four outputs and a checksum over all of them (acc * 31 + x with wrapping arithmetic, folded in order). A wrong value at any position, or a wrong order, almost certainly changes the checksum. The largest test has 2,000,000 elements and four operations.

Two ways to write it

A Vec<Box<dyn Fn(u64) -> u64>>, built once from ops and then called for each element, is a correct answer. Each element goes through one indirect call per operation, which the compiler usually cannot inline. Each closure that captures its argument also needs its own heap allocation (a closure that captures nothing is zero-sized, and boxing it does not allocate).

The reference solution instead parses each string once into a small enum and matches on it inside the loop. Every arm of the match is ordinary code the compiler can see and inline. The match is still a branch per operation per element, but on a pipeline that repeats the same pattern for every element it is typically easy for the processor to predict. Another option is to swap the loops: apply the first operation to the whole buffer, then the second, and so on. Each pass is then a simple loop with no branching on the operation, which can be easier for the compiler to optimize.

The harness also spends time generating the input and computing the checksum, so the dispatch strategy is only part of the total running time and the difference between these approaches may be small. Treat the exercise as practice in giving the optimizer code it can see through, not as proof that one form always wins.

Two lints about trait objects

Your submission must compile, pass the tests and pass cargo clippy -- -D warnings, which turns every warning into an error.

• clippy::borrowed_box (on by default) flags parameters such as &Box<dyn Trait>. That is a reference to a box, which in turn holds the fat pointer, so reaching the value takes an extra pointer hop, and the function only accepts values that are already boxed. Take &dyn Trait instead. A caller holding b: Box<dyn Trait> can pass &*b or b.as_ref().
• ambiguous_wide_pointer_comparisons is a rustc lint (on by default). Clippy's older vtable_address_comparisons lint has been renamed to it. Comparing two wide pointers such as *const dyn Trait with == compares the vtable pointers as well as the addresses. The same type can end up with more than one vtable for the same trait (for example, in different codegen units), and different types can share one, so that comparison can give surprising results. Use std::ptr::addr_eq(a, b) to compare only the addresses. std::ptr::eq on wide pointers also compares the metadata.