对于较小的最终长度，为什么 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 万个元素的火焰图

1 亿个元素的火焰图

我的理解是，with_capacity如果知道最终长度，那么应该总是更快，因为堆上的数据被分配一次，这应该会产生一个块。相反，版本new增加了向量MAX_NUMBER时间，这导致了更多的分配。

我缺少什么？

编辑

第一部分是用debug配置文件编译的。如果我使用release具有以下设置的配置文件Cargo.toml

[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);

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

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_capacity始终比 快with_new。最接近的运行在 10,000 到 1,000,000 个元素的运行中，with_capacity仍然只花费了约 60% 的时间，而其他运行则只花费了一半或更少的时间。

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

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]

您的测试代码仅调用每个策略一次，因此可以想象您的测试环境在调用第一个策略后发生了更改（潜在的罪魁祸首是堆碎片，如 @trent_forming_cl 在评论中所建议的，尽管可能还有其他原因：cpu 提升/节流，空间和/或时间缓存位置、操作系统行为等）。像这样的基准测试框架criterion可以通过多次迭代每个测试（包括预热迭代）来帮助避免许多此类问题。