为何map+collect创建的Vec<bool>哈希速度远慢于push方式？

环境信息 #

• 编译器：rustc 1.74.1 (a28077b28 2023-12-04)
• 运行命令：cargo run --release

问题摘要 #

通过.iter().map(..).collect()创建的Vec<bool>，哈希速度比通过for .. { v.push(..); }创建的慢约10倍。

慢代码示例 #

// Slow
let valve_states: Vec<bool> = valves.iter().map(|valve| valve.rate == 0).collect();

快代码示例 #

// Fast
let mut valve_states = Vec::with_capacity(valves.len());
for valve in valves {
    valve_states.push(valve.rate == 0);
}

上下文 #

我在解决Advent of Code 2022第16天第一部分的问题，为实现缓存使用了以State为键的HashMap，State包含一个valve_states: Vec<bool>，用于表示阀门的开启状态，初始时将流量为0的阀门视为已开启。

使用map+collect创建valve_states时，整体耗时比push方式多约30%。通过profile-bpfcc分析后发现，哈希操作是性能瓶颈，具体来说，core::hash::sip::Hasher<S> as core::hash::Hasher>::write函数的采样频率是另一种方式的10倍。

问题 #

为何会出现这种差异？两种方式创建的Vec长度和容量均相同（len == 62，cap == 62），且State::new仅调用一次，其他需要哈希的状态都是克隆而来的。

原因分析 #

这是因为Vec<bool>是Rust中的特殊类型——它是位向量（bit vector），而非普通的Vec（每个元素占1字节）。两种创建方式导致了向量内部内存布局的关键差异：

1. push方式：
   提前用with_capacity分配了刚好容纳所有位的内存空间，每次push都会直接把布尔值按位写入对应位置。整个过程完成后，底层字节中未使用的剩余位会被初始化为0，内存布局干净紧凑。

2. collect方式：
   collect处理Vec<bool>时，内部会先将结果临时存储，再复制到最终的向量中。这个过程可能会留下未初始化的脏数据在底层字节的剩余位里。

而哈希Vec<bool>时，哈希函数会遍历其底层的所有字节（包括未被使用的填充位）。如果collect创建的向量底层存在脏数据，哈希函数需要额外处理这些无意义的字节，导致计算量暴增——这就是哈希操作耗时差10倍的核心原因。

即使向量的长度和容量完全相同，62个布尔值需要8个字节（64位）存储，剩余2位如果是脏数据，哈希时也会被纳入计算；而push方式的剩余位是干净的0，不会增加哈希计算量。

内容的提问来源于stack exchange，提问作者Donghyeon Lee