performance - 如何推理这两个非常相似的功能之间的巨大性能差异？

Question

以下两个函数calculate the same value。它们的区别仅在于减法，强制转换和在迭代器中用skip替换take。
它们的性能差异为 5.5倍。

fn lehmer_index(xs: [u8; 8]) -> u32 {
    const FACTORIALS: [u32; 8] = [1, 1, 2, 6, 24, 120, 720, 5040];
    (0..8).fold(0, |acc, i| {
        acc + FACTORIALS[7 - i] * xs.iter().skip(i + 1).filter(|&&x| x < xs[i]).count() as u32
    })
}

fn lehmer_index2(xs: [u8; 8]) -> u32 {
    const FACTORIALS: [u32; 8] = [1, 1, 2, 6, 24, 120, 720, 5040];
    (0..8).fold(0, |acc, i| {
        acc + FACTORIALS[7 - i] * ((xs[i] as u32) - xs.iter().take(i).filter(|&&x| x < xs[i]).count() as u32)
    })
}

基准:

lehmer_index            time:   [8.4142 ns 8.4796 ns 8.5542 ns]
lehmer_index2           time:   [46.726 ns 46.812 ns 46.921 ns]

在我的模拟中，我正在计算这万亿次，这是一个巨大的差异。我会使用第一个，但是第二个是一个通用版本，它使用较少需要的假设的输入。
为什么速度差？我如何得出这样的性能差异？

Answer 1

Looking at the assembly看起来第一个完全内联并展开了矢量化代码，而第二个则使优化器跳了起来，因此无法展开循环。
rust 代码没有任何真正的理由可以解释这一点，您需要提取生成的程序集以及对现代x86处理器的直觉。然后，只需尝试修改代码，直到优化器产生符合基准的内容即可。
在特定情况下(对于 rust 1.47)，通过将内部值分配给变量来简单地对表达式重新排序似乎会导致线性组装，这在基准测试中可能会被证明更好:

pub fn lehmer_index3(xs: [u8; 8]) -> u32 {
    const FACTORIALS: [u32; 8] = [1, 1, 2, 6, 24, 120, 720, 5040];
    (0..8).fold(0, |acc, i| {
        let a = xs[i] as u32;
        let b = xs.iter()
            .take(i)
            .filter(|&&x| x < xs[i])
            .count() as u32;
        let c = a - b;
        acc + FACTORIALS[7 - i] * c
    })
}