Rust如何为向量分配更多空间？

Question

请查看以下代码：

fn main() {
  let mut vec: Vec<u8> = Vec::new();
  vec.push(0);
  vec.push(1);
  vec.push(2);
  vec.push(3);
  vec.push(4);
  vec.push(5);
  vec.push(6);
  vec.push(7);
  vec.push(8);
}

当调用Vec::new()时，Rust 不知道需要分配多少内存，每次需要为向量分配更多空间时，它都会使用新的大小调用malloc ，然后将所有数据从堆中的旧位置克隆到新位置，是这样吗？

Rust 是如何确定要分配的新大小的策略呢？

例如，是否像这样每次向向量推送元素时就进行分配？

[]
[0]
[0, 1]
[0, 1, 2]
[0, 1, 2, 3]
etc...

看起来这很低效。也许Rust可以像这样做：

[]
[0, <empty>]
[0, 1] 
[0, 1, 2, <empty>, <empty>, <empty>, <empty>, <empty>]
[0, 1, 2, 3, <empty>, <empty>, <empty>, <empty>]
[0, 1, 2, 3, 4, <empty>, <empty>, <empty>]
etc...

- D. Pardal

Answer 1

Vec的文档中说：这里：

Vec在重新分配满时并不保证任何特定的增长策略，也不保证调用reserve时增长的方式。当前策略是基本的，可能会使用非常数增长因子更好。无论使用什么策略，都将保证摊销后push的时间复杂度为O(1)。

摊销的O(1) push保证了Rust不会在每次push时重新分配空间。它看起来更像你描述的第二种情况，即分配额外的容量以留出空间供其他元素推入。

如果我们深入探究Rust标准库的源代码，就会发现在这种情况下（一次推入一个元素），Vec的当前实现实际上会将其容量加倍。当然，这个确切的策略没有规定，并且在未来的实现中可能会发生变化。

如果您从一开始就知道您的Vec需要多大，您可以使用Vec::with_capacity来构建它，以避免任何重新分配的需要。

- Brent Kerby

Answer 2

Vec 有长度和容量。容量是指 Vec 可以在不重新分配内存的情况下所能存储的元素数量。当元素数量超过当前容量时，再添加新的元素会导致容量增加并且 Vec 会重新分配内存。

具体扩容策略未作规定，可能会在将来更改。当前策略是：在需要增加容量时将其加倍。但是有一种特殊情况：Vec::new() 不分配任何内存，但是第一次添加元素会分配足够空间以存储多达 8 个元素：

• 如果每个元素只有 1 字节大小（例如 bool 或 u8），则容量设置为 8，即 64 位
• 如果元素大小在 2 字节到 1 KiB 之间，则容量设置为 4
• 否则，容量设置为 1

请注意，这是一项实现细节，可能会发生变化。实际上，在最近已经发生了更改。

- Aloso

Answer 3

任何支持动态可增长容器的语言都面临着相同的问题。它们几乎总是一次性分配块以最小化分配和重定位。

实际上，Vec 的文档也如此说明。例如，reserve 方法：

保留足够的容量，以便在给定的 Vec 中插入至少 additional 个元素。为了避免频繁的重新分配，该集合可能会保留更多的空间。

实际使用的算法没有在 std 文档中记录（至少我没有找到），但您可以在 std 库源代码的 raw_vec 模块的 grow_amortized 函数中看到其实现。在大多数情况下，每次需要扩展向量时都会将其大小加倍。

如果您提前知道 Vec 需要的大小，可以通过调用 Vec::with_capacity 来避免重新调整大小的开销。

顺便说一下，Vec 说明了 Rust 安全规则的重要性。如果您引用了 Vec 中的一个元素，并且在持有该引用时触发了重新分配，则该引用将指向旧位置，因此无效。由于借用检查器以及如果您有一个可变借用 Vec，则不能有任何其他借用，编译器不会让您犯这个错误。

- harmic