Peculiar performance variance with small arrays

Question

As part of a larger project (of N-body simulations) I started working with arrays of f32s using const generics to represent algebraic vectors. Those vectors can then be of any size, but I'm especially interested in the ones of length 2 and 3.

I noticed that performance with arrays of length 2 was worse (a lot worse!) compared to similarly sized arrays (length 1 or 3 for example) in a certain scenario I need for my project.

This is the scenario, or rather a shortened version of it:

fn fold(v: Vec>) -> Vec> {
    let result = v.iter().map(|a1| {
        v.iter().fold(Array::default(), |acc, a2| {
            let d = *a2 - *a1;

            acc + d
        })
    });

    result.collect()
}

The arrays are wrapped in a newtype called Array implementing operators for simplicity, but the results are the same without that wrapper.

Using criterion with Vecs lengthed from 10 to 500 of random arrays, I benched this function and generated the following graph for differently sized arrays:

As you can see performance is a lot worse for arrays of length 2 compared to the rest. I'm unable to understand why this specific scenario leads to such performance variance, so I'm hoping someone can help me figure this out because this has slowed down my progress significantly.

Edit

Interestingly, it seems like this is not the case using f64s, the results I shared were with f32s.

Here's the the full criterion setup as requested in a comment:

use criterion::{black_box, criterion_group, criterion_main, BenchmarkId, Criterion};
use rand::{thread_rng, Rng};

#[derive(Clone, Copy, Debug)]
pub struct Array(pub [f32; DIM]);

impl Default for Array {
    fn default() -> Self {
        Self([0.0; DIM])
    }
}

impl std::ops::Add for Array {
    type Output = Self;

    fn add(self, rhs: Self) -> Self::Output {
        let mut result = Array::default();
        for (i, val) in result.0.iter_mut().enumerate() {
            *val = self.0[i] + rhs.0[i];
        }
        result
    }
}

impl std::ops::Sub for Array {
    type Output = Self;

    fn sub(self, rhs: Self) -> Self::Output {
        let mut result = Array::default();
        for (i, val) in result.0.iter_mut().enumerate() {
            *val = self.0[i] - rhs.0[i];
        }
        result
    }
}

fn random_arrays(size: usize) -> Vec> {
    let mut rng = thread_rng();
    let mut gen = || rng.gen_range(-100.0..100.0);
    let mut v = Vec::new();
    for _ in 0..size {
        v.push(Array([0.0; N].map(|_| gen())));
    }
    v
}

fn fold(v: Vec>) -> Vec> {
    let result = v.iter().map(|a1| {
        v.iter().fold(Array::default(), |acc, a2| {
            let d = *a2 - *a1;

            acc + d
        })
    });

    result.collect()
}

fn criterion_benchmark(c: &mut Criterion) {
    let mut group = c.benchmark_group("Array fold");

    for i in (5000..=5000).step_by(10) {
        group.bench_with_input(BenchmarkId::new("Length 1", i), &i, |b, i| {
            b.iter(|| fold::<1>(black_box(random_arrays(*i))))
        });
        group.bench_with_input(BenchmarkId::new("Length 2", i), &i, |b, i| {
            b.iter(|| fold::<2>(black_box(random_arrays(*i))))
        });
        group.bench_with_input(BenchmarkId::new("Length 3", i), &i, |b, i| {
            b.iter(|| fold::<3>(black_box(random_arrays(*i))))
        });
        group.bench_with_input(BenchmarkId::new("Length 4", i), &i, |b, i| {
            b.iter(|| fold::<4>(black_box(random_arrays(*i))))
        });
        group.bench_with_input(BenchmarkId::new("Length 5", i), &i, |b, i| {
            b.iter(|| fold::<5>(black_box(random_arrays(*i))))
        });
    }

    group.finish();
}

criterion_group!(benches, criterion_benchmark);
criterion_main!(benches);

I also changed the graph's colors as the default ones were hard to distinguish.

Peculiar performance variance with small arrays

Edit

0 Answers