Auto-vectorisation and why floating-point addition blocks it

This is the biggest measured win in the course that you can produce with safe, portable, allocation-free code — and getting it requires understanding, at the right depth, why floats are not real numbers.

The measurements

Summing a million f64s:

A dot product over a million f32s:

9.6× over naive, from safe code with no intrinsics, no unsafe, and no crates.

Why the naive loop is slow

let mut s = 0.0;
for (x, y) in a.iter().zip(b) { s += x * y; }

Every addition needs the result of the previous addition. That is a serial dependency chain: the CPU’s floating-point adder has a latency of three or four cycles, and it can start a new addition every cycle, so you are using roughly a quarter of one execution port and none of the vector units.

Why doesn’t LLVM fix it? Because it is not allowed to.

Vectorising a reduction requires the operation to be associative. For integers + is: (a + b) + c == a + (b + c) always, so LLVM freely splits an integer sum into lanes. For IEEE-754 floats it is not:

(1e20 + 1.0) - 1e20  ==  0.0
1e20 + (1.0 - 1e20)  ==  1.0

Regrouping changes the answer. Rust deliberately does not enable fast-math, so s += x over f64 compiles to a strictly serial chain and stays that way. Your compiler is not being unhelpful; it is refusing to change your program’s meaning behind your back.

The consequence is the point of this item: if you want the regrouping, you have to write it.

What to write

pub fn dot(a: &[f32], b: &[f32]) -> f32

The specification mandates the reduction order — this is not a suggestion, it is what the tests check.

Let n = min(a.len(), b.len()) and m = n - n % 8.

1. Eight accumulators, acc[0..8], all starting at 0.0.

2. For every element i in 0..m, in increasing i, add a[i] * b[i] to acc[i % 8].

3. Combine them in exactly this tree:

   ((acc0 + acc1) + (acc2 + acc3)) + ((acc4 + acc5) + (acc6 + acc7))

4. Then fold the remainder m..n into that total, left to right, in increasing i.

The tests assert the result’s exact bit pattern (f32::to_bits), not an approximation. A different grouping gives a different u32 and fails.

That is deliberate on two counts. It makes the problem deterministic, which a floating-point problem otherwise is not — and it forces the shape that goes fast, because the mandated order is the vectorisable one.

Why bit-exactness is achievable at all

Rust never contracts a * b + c into a fused multiply-add implicitly. FMA has a different rounding behaviour — one rounding instead of two — so a compiler that contracts silently would give different answers on different targets. f32::mul_add exists and is a different function with different results; reach for it when you want the extra precision, never assume you got it.

Because contraction is off and the order is pinned, this function produces the same bits on x86 and on aarch64. That is only true because the order is fixed. It is the whole reason the specification is written the way it is.

What eight lanes buys you at the hardware level

Eight independent chains means eight additions in flight, which saturates the adder’s latency. And once the loop body is eight independent lane updates, LLVM can see a 256-bit vector add (AVX2) or two 128-bit ones (NEON) and emit them — which is where the last factor of three comes from.

chunks_exact(8) is the idiomatic way to express it: the chunk length is a compile-time constant, so the inner work unrolls and the bounds checks fold away. The accumulator count must be a constant; a runtime w gives you none of this.

Why eight and not four or sixteen? Eight is a reasonable default for 32-bit lanes on current hardware. The right answer is measured, not derived, and it changes with the element type and the microarchitecture.

Related lints

manual_memcpy, needless_range_loop, and — in nursery/pedantic, so off by default but worth knowing — suboptimal_flops and imprecise_flops, which point at mul_add, hypot, ln_1p and friends. float_cmp warns about == on floats; comparing to_bits() as this problem’s harness does is the well-defined way to ask “is this the exact same value”.

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