为什么 Vec::with_capacity 对于较小的最终长度比 Vec::new 慢？

Question

考虑这段代码。

type Int = i32;
const MAX_NUMBER: Int = 1_000_000;

fn main() {
    let result1 = with_new();
    let result2 = with_capacity();
    assert_eq!(result1, result2)
}

fn with_new() -> Vec<Int> {
    let mut result = Vec::new();
    for i in 0..MAX_NUMBER {
        result.push(i);
    }
    result
}

fn with_capacity() -> Vec<Int> {
    let mut result = Vec::with_capacity(MAX_NUMBER as usize);
    for i in 0..MAX_NUMBER {
        result.push(i);
    }
    result
}

两个函数产生相同的输出。一个使用Vec::new，另一个使用Vec::with_capacity。对于较小的 MAX_NUMBER 值（如示例中），with_capacity 比 new 慢。仅对于较大的最终向量长度（例如 1 亿），使用 with_capacity 的版本与使用 new.

一样快

100 万个元素的 Flamegraph

1 亿个元素的 Flamegraph

据我了解，如果知道最终长度，with_capacity 应该总是更快，因为堆上的数据分配一次，应该导致单个块。相比之下，具有 new 的版本将向量增长 MAX_NUMBER 次，从而导致更多分配。

我错过了什么？

编辑

第一部分是使用 debug 配置文件编译的。如果我在 Cargo.toml

中使用具有以下设置的 release 配置文件

[package]
name = "vec_test"
version = "0.1.0"
edition = "2021"

[profile.release]
opt-level = 3
debug = 2

对于 1000 万 的长度，我仍然得到以下结果。

Answer 1

我无法在综合基准测试中重现这一点：

use criterion::{criterion_group, criterion_main, BenchmarkId, Criterion};

fn with_new(size: i32) -> Vec<i32> {
    let mut result = Vec::new();
    for i in 0..size {
        result.push(i);
    }
    result
}

fn with_capacity(size: i32) -> Vec<i32> {
    let mut result = Vec::with_capacity(size as usize);
    for i in 0..size {
        result.push(i);
    }
    result
}

pub fn with_new_benchmark(c: &mut Criterion) {
    let mut group = c.benchmark_group("with_new");
    for size in [100, 1_000, 10_000, 100_000, 1_000_000, 10_000_000].iter() {
        group.bench_with_input(BenchmarkId::from_parameter(size), size, |b, &size| {
            b.iter(|| with_new(size));
        });
    }
    group.finish();
}

pub fn with_capacity_benchmark(c: &mut Criterion) {
    let mut group = c.benchmark_group("with_capacity");
    for size in [100, 1_000, 10_000, 100_000, 1_000_000, 10_000_000].iter() {
        group.bench_with_input(BenchmarkId::from_parameter(size), size, |b, &size| {
            b.iter(|| with_capacity(size));
        });
    }
    group.finish();
}

criterion_group!(benches, with_new_benchmark, with_capacity_benchmark);
criterion_main!(benches);

这是输出（移除了异常值和其他基准测试内容）：

with_new/100            time:   [331.17 ns 331.38 ns 331.61 ns]
with_new/1000           time:   [1.1719 us 1.1731 us 1.1745 us]
with_new/10000          time:   [8.6784 us 8.6840 us 8.6899 us]
with_new/100000         time:   [77.524 us 77.596 us 77.680 us]
with_new/1000000        time:   [1.6966 ms 1.6978 ms 1.6990 ms]
with_new/10000000       time:   [22.063 ms 22.084 ms 22.105 ms]

with_capacity/100       time:   [76.796 ns 76.859 ns 76.926 ns]
with_capacity/1000      time:   [497.90 ns 498.14 ns 498.39 ns]
with_capacity/10000     time:   [5.0058 us 5.0084 us 5.0112 us]
with_capacity/100000    time:   [50.358 us 50.414 us 50.470 us]
with_capacity/1000000   time:   [1.0861 ms 1.0868 ms 1.0876 ms]
with_capacity/10000000  time:   [10.644 ms 10.656 ms 10.668 ms]

with_capacity 的运行速度一直比 with_new 快。最接近的是在 10,000 到 1,000,000 个元素中运行，其中 with_capacity 仍然只用了大约 60% 的时间，而其他人只用了一半或更少的时间。

我突然想到可能会发生一些奇怪的常量传播行为，但即使使用具有硬编码大小的单个函数（playground 为简洁起见），行为也没有显着改变：

with_new/100            time:   [313.87 ns 314.22 ns 314.56 ns]
with_new/1000           time:   [1.1498 us 1.1505 us 1.1511 us]
with_new/10000          time:   [7.9062 us 7.9095 us 7.9130 us]
with_new/100000         time:   [77.925 us 77.990 us 78.057 us]
with_new/1000000        time:   [1.5675 ms 1.5683 ms 1.5691 ms]
with_new/10000000       time:   [20.956 ms 20.990 ms 21.023 ms]

with_capacity/100       time:   [76.943 ns 76.999 ns 77.064 ns]
with_capacity/1000      time:   [535.00 ns 536.22 ns 537.21 ns]
with_capacity/10000     time:   [5.1122 us 5.1150 us 5.1181 us]
with_capacity/100000    time:   [50.064 us 50.092 us 50.122 us]
with_capacity/1000000   time:   [1.0768 ms 1.0776 ms 1.0784 ms]
with_capacity/10000000  time:   [10.600 ms 10.613 ms 10.628 ms]

您的测试代码只调用每个策略一次，因此可以想象您的测试环境在调用第一个策略后发生了变化（潜在的罪魁祸首是注释中@trent_formerly_cl 所建议的堆碎片，尽管有可能是其他：cpu boosting/throttling、空间 and/or 时间缓存局部性、OS 行为等）。像 criterion 这样的基准测试框架通过多次迭代每个测试（包括预热迭代）来帮助避免很多这些问题。

为什么 Vec::with_capacity 对于较小的最终长度比 Vec::new 慢？

Why is Vec::with_capacity slower than Vec::new for small final lengths?

performance

vector

memory-management

rust

编辑