arrays - 为什么在使用240个或更多元素循环数组时会产生很大的性能影响?




performance rust (2)

当在Rust中的数组上运行求和循环时,我注意到当 CAPACITY > = 240时性能下降很大 CAPACITY = 239大约快80倍。

是否有特殊的编译优化Rust正在为“短”数组做什么?

rustc -C opt-level=3 编译。

use std::time::Instant;

const CAPACITY: usize = 240;
const IN_LOOPS: usize = 500000;

fn main() {
    let mut arr = [0; CAPACITY];
    for i in 0..CAPACITY {
        arr[i] = i;
    }
    let mut sum = 0;
    let now = Instant::now();
    for _ in 0..IN_LOOPS {
        let mut s = 0;
        for i in 0..arr.len() {
            s += arr[i];
        }
        sum += s;
    }
    println!("sum:{} time:{:?}", sum, now.elapsed());
}

除了Lukas的回答,如果你想使用迭代器,试试这个:

const CAPACITY: usize = 240;
const IN_LOOPS: usize = 500000;

pub fn bar() -> usize {
    (0..CAPACITY).sum::<usize>() * IN_LOOPS
}

感谢@Chris Morgan关于范围模式的建议。

优化的组装 非常好:

example::bar:
        movabs  rax, 14340000000
        ret

总结 :在240以下,LLVM完全展开内循环,让它注意到它可以优化重复循环,打破你的基准。


您找到了一个魔术阈值,高于该阈值LLVM停止执行某些优化 。 阈值是8字节* 240 = 1920字节(您的数组是 usize 的数组,因此假设x86-64 CPU,长度乘以8字节)。 在这个基准测试中,一个特定的优化 - 仅对长度239执行 - 是造成巨大速度差异的原因。 但让我们慢慢开始:

(此答案中的所有代码都是使用 -C opt-level=3 编译的)

pub fn foo() -> usize {
    let arr = [0; 240];
    let mut s = 0;
    for i in 0..arr.len() {
        s += arr[i];
    }
    s
}

这个简单的代码将大致产生一个人们期望的组件:一个循环添加元素。 但是,如果将 240 更改为 239 ,则发出的组件会有很大差异。 在Godbolt Compiler Explorer上看到它 。 这是装配的一小部分:

movdqa  xmm1, xmmword ptr [rsp + 32]
movdqa  xmm0, xmmword ptr [rsp + 48]
paddq   xmm1, xmmword ptr [rsp]
paddq   xmm0, xmmword ptr [rsp + 16]
paddq   xmm1, xmmword ptr [rsp + 64]
; more stuff omitted here ...
paddq   xmm0, xmmword ptr [rsp + 1840]
paddq   xmm1, xmmword ptr [rsp + 1856]
paddq   xmm0, xmmword ptr [rsp + 1872]
paddq   xmm0, xmm1
pshufd  xmm1, xmm0, 78
paddq   xmm1, xmm0

这就是所谓的 循环展开 :LLVM粘贴循环体一堆时间,以避免必须执行所有那些“循环管理指令”,即递增循环变量,检查循环是否已经结束以及跳转到循环的开始。

如果你想知道: paddq 和类似的指令是SIMD指令,它允许并行地汇总多个值。 此外,并行使用两个16字节SIMD寄存器( xmm0xmm1 ),以便CPU的指令级并行性基本上可以同时执行这些指令中的两个。 毕竟,他们是彼此独立的。 最后,将两个寄存器相加,然后水平求和到标量结果。

现代主流x86 CPU(不是低功耗Atom)在L1d缓存中实际上每个时钟可以执行2个向量加载,并且 paddq 吞吐量每个时钟至少2个,在大多数CPU上有1个周期延迟。 请参阅 https://agner.org/optimize/ 以及有关多个累加器的 问答, 以隐藏延迟(针对点积的FP FMA)和吞吐量的瓶颈。

LLVM在未 完全 展开时会展开 一些 小循环,并且仍使用多个累加器。 通常,即使没有完全展开,前端带宽和后端延迟瓶颈对于LLVM生成的循环也不是一个大问题。

但是,循环展开不对因子80的性能差异负责! 至少不是单独循环展开。 让我们看看实际的基准测试代码,它将一个循环放在另一个循环中:

const CAPACITY: usize = 239;
const IN_LOOPS: usize = 500000;

pub fn foo() -> usize {
    let mut arr = [0; CAPACITY];
    for i in 0..CAPACITY {
        arr[i] = i;
    }

    let mut sum = 0;
    for _ in 0..IN_LOOPS {
        let mut s = 0;
        for i in 0..arr.len() {
            s += arr[i];
        }
        sum += s;
    }

    sum
}

在Godbolt Compiler Explorer上

CAPACITY = 240 的程序集看起来很正常:两个嵌套循环。 (在函数的开头有一些代码只是用于初始化,我们将忽略它。)然而,对于239,它看起来非常不同! 我们看到初始化循环和内循环已展开:到目前为止如此预期。

重要的区别是,对于239,LLVM能够弄清楚内部循环的结果不依赖于外部循环! 因此,LLVM发出的代码基本上首先只执行内部循环(计算总和),然后通过多次加 sum 模拟外部循环!

首先,我们看到几乎与上面相同的程序集(代表内部循环的程序集)。 之后我们看到了这个(我评论说明了汇编;带 * 的评论特别重要):

        ; at the start of the function, `rbx` was set to 0

        movq    rax, xmm1     ; result of SIMD summing up stored in `rax`
        add     rax, 711      ; add up missing terms from loop unrolling
        mov     ecx, 500000   ; * init loop variable outer loop
.LBB0_1:
        add     rbx, rax      ; * rbx += rax
        add     rcx, -1       ; * decrement loop variable
        jne     .LBB0_1       ; * if loop variable != 0 jump to LBB0_1
        mov     rax, rbx      ; move rbx (the sum) back to rax
        ; two unimportant instructions omitted
        ret                   ; the return value is stored in `rax`

正如你在这里看到的那样,内循环的结果被采用,就像外循环运行然后返回一样。 LLVM只能执行此优化,因为它了解内部循环独立于外部循环。

这意味着运行时从 CAPACITY * IN_LOOPS 更改为 CAPACITY + IN_LOOPS 。 这是造成巨大性能差异的原因。

另外一个注意事项:你能对此做些什么吗? 并不是的。 LLVM必须具有这样的魔术阈值,如果没有它们,LLVM优化可能需要永远完成某些代码。 但我们也同意这段代码非常人为。 在实践中,我怀疑会发生如此巨大的差异。 在这些情况下,由于完整循环展开的差异通常不是因子2。 所以不必担心真实的用例。

作为关于惯用Rust代码的最后一个注释: arr.iter().sum() 是一种更好的方法来总结数组的所有元素。 在第二个示例中更改此设置不会导致发出的组件有任何显着差异。 您应该使用简短版本和惯用版本,除非您测量它会损害性能。







llvm-codegen