vector - 为什么通过替换默认值填充 Vec 比填充具有预设容量的东西快得多？

Question

前言:我一般不是优化师。

大多数时候，在用 Rust 解决编码难题时，我使用 Vec::with_capacity 来初始化我的向量，然后通过 push 将它们插入向量.对于大多数用途来说，这很好，但我最近遇到了一个需要更快程序的难题，这激发了我重新思考我的方法。

因为我知道向量的容量恰好是某个数字，所以我决定比较我常用的 with_capacity 和 push 方法的结果，以创建一个充满0 并替换它们。这是我用来对这两个操作进行基准测试的代码:

#![feature(test)]

extern crate test;

#[cfg(test)]
mod tests {
    use test::Bencher;

    // Create a vector with a capacity of 10,000 u16s
    // and populate it by pushing.
    #[bench]
    fn push_fill(b: &mut Bencher) {
        b.iter(|| {
            let mut v: Vec<u16> = Vec::with_capacity(10000);
            for i in 0..10000 as u16 {
                v.push(i);
            }
        })
    }

    // Create a vector of 10,000 u16s, initialize them
    // to 0, and then replace them to populate the vector.
    #[bench]
    fn replace_fill(b: &mut Bencher) {
        b.iter(|| {
            let mut v: Vec<u16> = vec![0u16; 10000];
            for i in 0..10000 {
                v[i] = i as u16;
            }
        })
    }
}

令我惊讶的是，当我运行 cargo +nightly bench 时，替换解决方案比 with_capacity 解决方案好一个数量级。

   Compiling benchmarks v0.1.0 (file:///C:/Users/CEUser/Documents/Programs/rustprojects/benchmarks)
    Finished release [optimized] target(s) in 10.75 secs
     Running target\release\deps\benchmarks-0b553bf1dfb7e9a4.exe

running 2 tests
test tests::push_fill    ... bench:      26,756 ns/iter (+/- 4,046)
test tests::replace_fill ... bench:       1,902 ns/iter (+/- 802)

test result: ok. 0 passed; 0 failed; 0 ignored; 2 measured; 0 filtered out

我对时间上的差异感到惊讶，特别是考虑到我预计 replace 版本需要更长的时间(假设它必须创建一个充满填充的向量，然后然后 用实际数据替换填充数据)。

replace_fill 比 push_fill 快那么多有什么直观原因吗？这两个函数的作用有何区别？

Answer 1

如有疑问，请检查装配!

您可以使用 godbolt或 Playground ；尽管我在这里更喜欢 godbolt，因为它使用突出显示将程序集部分与源代码相匹配，从而更容易探索。

---

在上面的链接中，replace_fill 函数被优化为:

example::replace_fill:
  push rbp
  mov rbp, rsp
  sub rsp, 48
  lea rdx, [rbp - 24]
  mov edi, 20000
  mov esi, 2
  call __rust_alloc_zeroed@PLT
  test rax, rax
  je .LBB3_4
  movdqa xmm0, xmmword ptr [rip + .LCPI3_0]
  mov ecx, 32
  movdqa xmm1, xmmword ptr [rip + .LCPI3_1]
  movdqa xmm2, xmmword ptr [rip + .LCPI3_2]
  movdqa xmm3, xmmword ptr [rip + .LCPI3_3]
  movdqa xmm4, xmmword ptr [rip + .LCPI3_4]
  movdqa xmm5, xmmword ptr [rip + .LCPI3_5]
.LBB3_2:
  movdqu xmmword ptr [rax + 2*rcx - 64], xmm0
  movdqa xmm6, xmm0
  paddw xmm6, xmm1
  movdqu xmmword ptr [rax + 2*rcx - 48], xmm6
  movdqa xmm6, xmm0
  paddw xmm6, xmm2
  movdqu xmmword ptr [rax + 2*rcx - 32], xmm6
  movdqa xmm6, xmm0
  paddw xmm6, xmm3
  movdqu xmmword ptr [rax + 2*rcx - 16], xmm6
  movdqa xmm6, xmm0
  paddw xmm6, xmm4
  movdqu xmmword ptr [rax + 2*rcx], xmm6
  paddw xmm0, xmm5
  add rcx, 40
  cmp rcx, 10032
  jne .LBB3_2
  mov esi, 20000
  mov edx, 2
  mov rdi, rax
  call __rust_dealloc@PLT
  add rsp, 48
  pop rbp
  ret
.LBB3_4:
  mov rax, qword ptr [rbp - 24]
  movups xmm0, xmmword ptr [rbp - 16]
  movaps xmmword ptr [rbp - 48], xmm0
  mov qword ptr [rbp - 24], rax
  movaps xmm0, xmmword ptr [rbp - 48]
  movups xmmword ptr [rbp - 16], xmm0
  lea rdi, [rbp - 24]
  call __rust_oom@PLT
  ud2

后一部分 (LBB3_4) 是 OOM 处理，因此从未使用过。因此，执行流程为:

• example::replace_fill，执行分配 + 初始设置，
• .LBB3_2 这是循环。

注意事项有2个:

• 根本没有 Vec 代码出现，
• 这些是矢量指令。

---

另一方面，push_fill 有点复杂:

example::push_fill:
  push rbp
  mov rbp, rsp
  push r15
  push r14
  push rbx
  sub rsp, 40
  lea rdx, [rbp - 48]
  mov edi, 20000
  mov esi, 2
  call __rust_alloc@PLT
  mov rcx, rax
  test rcx, rcx
  je .LBB2_11
  mov qword ptr [rbp - 48], rcx
  mov qword ptr [rbp - 40], 10000
  mov qword ptr [rbp - 32], 0
  xor r15d, r15d
  lea r14, [rbp - 48]
  xor esi, esi
.LBB2_2:
  mov ebx, r15d
  add bx, 1
  cmovb bx, r15w
  jb .LBB2_3
  cmp rsi, qword ptr [rbp - 40]
  jne .LBB2_9
  mov rdi, r14
  call <alloc::raw_vec::RawVec<T, A>>::double
  mov rcx, qword ptr [rbp - 48]
  mov rsi, qword ptr [rbp - 32]
.LBB2_9:
  mov word ptr [rcx + 2*rsi], r15w
  mov rsi, qword ptr [rbp - 32]
  inc rsi
  mov qword ptr [rbp - 32], rsi
  movzx eax, bx
  cmp eax, 10000
  mov r15w, bx
  jb .LBB2_2
.LBB2_3:
  mov rsi, qword ptr [rbp - 40]
  test rsi, rsi
  je .LBB2_5
  add rsi, rsi
  mov rdi, qword ptr [rbp - 48]
  mov edx, 2
  call __rust_dealloc@PLT
.LBB2_5:
  add rsp, 40
  pop rbx
  pop r14
  pop r15
  pop rbp
  ret
.LBB2_11:
  movups xmm0, xmmword ptr [rbp - 40]
  movaps xmmword ptr [rbp - 64], xmm0
  movaps xmm0, xmmword ptr [rbp - 64]
  movups xmmword ptr [rbp - 40], xmm0
  lea rdi, [rbp - 48]
  call __rust_oom@PLT
  ud2
  mov rbx, rax
  lea rdi, [rbp - 48]
  call core::ptr::drop_in_place
  mov rdi, rbx
  call _Unwind_Resume@PLT
  ud2

更多的 block ，意味着更多的分支，在循环的每次迭代中检查是否超出容量，...

---

不过，以上示例都不是惯用的。

我会这样写:

#[inline(never)]
pub fn extend_fill() {
    let mut v = Vec::new();
    v.extend(0u16..10000);
}

此方法来自于实现 Extend trait .当与信任长度迭代器(如这个迭代器)一起使用时，它将在必要时执行单个“增长”步骤，然后推送而无需再次检查。

程序集不像 replace_fill 那样精简，但看起来仍然不错:

example::extend_fill:
  push rbp
  mov rbp, rsp
  sub rsp, 64
  mov qword ptr [rbp - 24], 2
  xorps xmm0, xmm0
  movups xmmword ptr [rbp - 16], xmm0
  lea rdx, [rbp - 48]
  mov edi, 20000
  mov esi, 2
  call __rust_alloc@PLT
  test rax, rax
  je .LBB4_7
  mov qword ptr [rbp - 24], rax
  mov qword ptr [rbp - 16], 10000
  xor ecx, ecx
  movdqa xmm0, xmmword ptr [rip + .LCPI4_0]
  movdqa xmm1, xmmword ptr [rip + .LCPI4_1]
  jmp .LBB4_2
.LBB4_6:
  movd xmm2, edx
  pshuflw xmm2, xmm2, 0
  pshufd xmm2, xmm2, 80
  movdqa xmm3, xmm2
  paddw xmm3, xmm0
  paddw xmm2, xmm1
  movdqu xmmword ptr [rax + 2*rcx + 32], xmm3
  movdqu xmmword ptr [rax + 2*rcx + 48], xmm2
  add rdx, 16
  mov rcx, rdx
.LBB4_2:
  movd xmm2, ecx
  pshuflw xmm2, xmm2, 0
  pshufd xmm2, xmm2, 80
  movdqa xmm3, xmm2
  paddw xmm3, xmm0
  paddw xmm2, xmm1
  movdqu xmmword ptr [rax + 2*rcx], xmm3
  movdqu xmmword ptr [rax + 2*rcx + 16], xmm2
  lea rdx, [rcx + 16]
  cmp rdx, 10000
  jne .LBB4_6
  mov qword ptr [rbp - 8], 10000
  mov rsi, qword ptr [rbp - 16]
  test rsi, rsi
  je .LBB4_5
  add rsi, rsi
  mov rdi, qword ptr [rbp - 24]
  mov edx, 2
  call __rust_dealloc@PLT
.LBB4_5:
  add rsp, 64
  pop rbp
  ret
.LBB4_7:
  movups xmm0, xmmword ptr [rbp - 40]
  movaps xmmword ptr [rbp - 64], xmm0
  movaps xmm0, xmmword ptr [rbp - 64]
  movups xmmword ptr [rbp - 40], xmm0
  lea rdi, [rbp - 48]
  call __rust_oom@PLT
  ud2

我鼓励您尝试一下，并在总体上熟悉 Rust 迭代器:甜美的代码、良好的性能，它们是您需要的工具。