Why is this functional version faster than my for loop?

211 points serdnad

I've recently found that rewriting loops into an equivalent functional form (e.g. \map().collect()\\) will sometimes cause small, but nonzero speedups in microbenchmarks. I'm trying to build an intuition for what makes for fast Rust code, but this time I got a way bigger speedup than I expected or can explain.

This is the original code, using a for loop to read a u8 2 bits at a time.

/// Deserialize bools from a custom compressed format.
pub fn deserialize(raw: &[u8]) -> Vec<Option<bool>> {
    let mut values = Vec::with_capacity(raw.len() * 4); // 4 bools per byte

    for &b in raw {
        for i in 0..4 {
            let val = match (b << i * 2) & 0b1100_0000 {
                0b1100_0000 => Some(true),
                0b1000_0000 => Some(false),
                _ => None,
            };
            values.push(val);
        }
    }

    values
}

This is the functional version, using map.

        values.extend((0..4).map(|i| {
            match (b << i * 2) & 0b1100_0000 {
                0b1100_0000 => Some(true),
                0b1000_0000 => Some(false),
                _ => None,
            }
        }));

Using Criterion to benchmark the two different versions, I get a speed up of \~7% for an input vector of 8 items, and 30% for 4,000 items. The only other difference I made besides replacing the for loop is using extend instead of push*, but even if the compiler can't optimize away the difference there, could that really cause a 30% speedup - particularly when I'm preallocating?

edit: formatting

edit 2: \*had initially written \append\\ here instead of \push\\ by accident