Compute a dot product with eight accumulator lanes

Implement a dot product using eight separate accumulators and the exact addition order below. Use safe Rust without allocating inside dot.

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

Use only the common prefix of the two slices: let n = min(a.len(), b.len()) and m = n - n % 8. Ignore any unmatched elements in the longer slice.

Required calculation

1. Start eight f32 accumulators at positive zero.

2. For each index i from 0 up to m, excluding m, compute a[i] * b[i] as f32 and add it to accumulator i % 8. Preserve increasing index order within each lane.

3. Combine the lanes with this exact tree, using f32 additions:

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

4. Starting with that total, add each remaining product for indices m through n - 1, in increasing order. Return the final f32 total.

Keep multiplication and addition separate. Do not replace them with mul_add or use f64 intermediates. Empty input, or either slice being empty, returns positive zero. With fewer than eight pairs, all pairs go through step 4. Input slices must remain unchanged.

For eight pairs of ones, every lane contains 1 and the result is 8. A ninth pair of ones is added after the tree, producing 9. Those simple inputs do not distinguish every possible grouping; rounded products and sums can.

Why addition order matters

Floating-point arithmetic rounds results. Consequently, regrouping additions can change the final value. This complete f32 example shows the difference:

fn main() {
    let a = 16_777_216.0_f32;
    let b = 1.0_f32;
    let c = -16_777_216.0_f32;
    assert_eq!(((a + b) + c).to_bits(), 0.0_f32.to_bits());
    assert_eq!((a + (b + c)).to_bits(), 1.0_f32.to_bits());
}

In the first expression, a + b rounds back to a before c is added. In the second, b + c is exactly representable and adding a gives 1. Regrouping is therefore part of this function's numerical behavior, not just its speed.

The starter sums every product into one running total. It agrees on some inputs but does not implement the required grouping. A wider accumulator or a more accurate summation algorithm would also change this exercise's result.

What the test wrapper does

The supplied wrapper accepts a nonnegative length n and builds two vectors:

a[i] = (i % 1000) as f32 * 0.001 + 0.5
b[i] = (i % 997) as f32 * 0.0007 + 0.25

These expressions use f32 constants and separate operations. The wrapper calls dot, then returns bits (the u32 representation from to_bits) and value (the f32 result converted to f64 for reporting). The fixed tests include empty input, incomplete blocks and one million pairs. Your dot function must still follow the slice contract, including unequal lengths.

The bits field makes rounding differences visible. Bit equality is distinct from float equality: positive and negative zero compare equal as floats but have different bits. Arithmetic NaN bit patterns are not generally portable or deterministic. The supplied generated test data avoids NaNs; fixed grouping is not a blanket guarantee of identical NaN bits on every target. See the f32 documentation.

How separate lanes can help performance

A single running sum depends on its previous value. Separate accumulators let the processor work on independent chains, and can help the compiler generate SIMD instructions that update several lanes together. The required grouping explicitly permits these independent updates while preserving the order within each lane.

Actual vectorization and speed depend on the compiler, optimization settings, target features and input size. Eight lanes are the specification here, not a universal best choice. Compare optimized builds on the same machine and inspect generated code before attributing a speedup to particular instructions.

as_chunks::<8>() exposes full blocks as arrays of eight elements and returns a remainder separately. Restrict both slices to the common prefix before splitting. A fixed array of eight accumulators needs no heap allocation. Iterating over paired blocks and lanes can also avoid needless index loops.

Passing requires the expected result, successful compilation and Clippy with warnings treated as errors. The tests do not require particular SIMD instructions or prove that an implementation is the fastest available.