51、Resizing（内存再分配）

Resizing

之前了解了，Vec是一种可以“生长”的vector类型，但这意味着什么？如果我们尝试将一个元素插入到已经达到最大容量的Vec时，会发生什么？

let mut numbers = Vec::with_capacity(3);
numbers.push(1);
numbers.push(2);
numbers.push(3); // Max capacity reached 达到了最大容量
numbers.push(4); // What happens here? 这里会发生什么

事实上，什么错误也没有发生，首先代码是正常运行的。

因为Vecresize itself（自行调整了大小）。

它会要求分配器提供新的（更大的）堆内存，将元素复制过去，然后取消分配旧的内存。

这一操作的代价可能很高，因为它涉及到新的内存分配和复制所有现有元素。

Vec::with_capacity

如果我们要想对Vec中存储元素的数量又有一个大致的了解，可以使用Vec::with_capacity方法预先分配足够的内存。

这可以避免在Vec增长时重新分配内存，但如果高估内存实际用量，那就会造成较多的浪费。

练习

这次的练习很有趣，让我们猜动态数组重新分配内存的大小，程序肯定是有逻辑的，肯定有代码明确的写了，先看一下题目：

fn main() {
    let mut v = Vec::with_capacity(2);
    v.push(1);
    v.push(2); // max capacity reached
    assert_eq!(v.capacity(), 2);

    v.push(3); // beyond capacity, needs to resize

    // Can you guess what the new capacity will be?
    // Beware that the standard library makes no guarantees about the
    // algorithm used to resize the vector, so this may change in the future.
    // 请注意，标准库并未对向量调整大小所使用的算法做出任何保证，因此这可能会在将来发生变化。
    assert_eq!(v.capacity(), /* TODO */);
}

于是我查看源代码，找到了关键的一个函数：

fn grow_amortized(
        &mut self,
        len: usize,
        additional: usize,
        elem_layout: Layout,
    ) -> Result<(), TryReserveError> {
        // This is ensured by the calling contexts.
        debug_assert!(additional > 0);

        if elem_layout.size() == 0 {
            // Since we return a capacity of `usize::MAX` when `elem_size` is
            // 0, getting to here necessarily means the `RawVec` is overfull.
            return Err(CapacityOverflow.into());
        }

        // Nothing we can really do about these checks, sadly.
        let required_cap = len.checked_add(additional).ok_or(CapacityOverflow)?;

        // This guarantees exponential growth. The doubling cannot overflow
        // because `cap <= isize::MAX` and the type of `cap` is `usize`.
        let cap = cmp::max(self.cap.as_inner() * 2, required_cap);
        let cap = cmp::max(min_non_zero_cap(elem_layout.size()), cap);

        let new_layout = layout_array(cap, elem_layout)?;

        let ptr = finish_grow(new_layout, self.current_memory(elem_layout), &mut self.alloc)?;
        // SAFETY: finish_grow would have resulted in a capacity overflow if we tried to allocate more than `isize::MAX` items

        unsafe { self.set_ptr_and_cap(ptr, cap) };
        Ok(())
    }

其中的let cap = cmp::max(self.cap.as_inner() * 2, required_cap);吸引了我的注意，那我就试一下4吧，没想到还真对了！

接下来认真分析一下代码，我们的push方法的源代码是：

#[cfg(not(no_global_oom_handling))]
#[inline]
#[stable(feature = "rust1", since = "1.0.0")]
#[rustc_confusables("push_back", "put", "append")]
#[track_caller]
pub fn push(&mut self, value: T) {
    // 告诉编译器：在调用 grow_one() 期间，self.len 的值不会发生变化。
    // 这是一个优化提示，帮助编译器更好地进行指针分析与内联优化。
    let len = self.len;
    // 如果当前长度等于容量，则必须扩容：
    // - 若分配内存超过 isize::MAX 字节，将 panic 或终止程序；
    // - 若为零大小类型（ZST），且长度已达 usize::MAX，增一操作会溢出，也将 panic。
    if len == self.buf.capacity() {
        // 此处的 grow_one() 负责动态扩展缓冲区，确保后续写入安全。
        self.buf.grow_one();
    }
    
    // 安全地将 value 写入到 Vec 的末尾位置
    unsafe {
        // 计算新元素应写入的位置：当前起始指针 + 当前长度（即最后一个有效元素之后）
        let end = self.as_mut_ptr().add(len);
        
        // 使用 ptr::write 安全地将 value 移动到目标内存中
        // → 不触发 Copy/Clone，直接构造 T 类型对象
        // → 必须在 unsafe 块中执行，因为操作未初始化内存
        ptr::write(end, value);
        
        // 更新 Vec 的长度计数，表示新增了一个有效元素
        // 注意：必须在 write 之后更新，否则访问时会认为长度不一致
        self.len = len + 1;
    }
}

对于这道题，我们先不关注其他的细节，只关注重新分配内存的部分。

很明显，当len == self.buf.capacity()满足时，就会触发内存扩容，我们继续看内部的代码：

#[cfg(not(no_global_oom_handling))]
#[inline(never)]
#[track_caller]
pub(crate) fn grow_one(&mut self) {
    // 调用底层内存管理器进行一次扩容，传入元素布局信息
    // T::LAYOUT 提供 size 和 alignment，用于安全分配内存
    self.inner.grow_one(T::LAYOUT)
}

继续查看：

#[cfg(not(no_global_oom_handling))]
#[inline]
#[track_caller]
fn grow_one(&mut self, elem_layout: Layout) {
    // 尝试按 amortized 策略（摊销扩容）增加 1 个元素容量
    // - 如果内存分配失败（如 OOM 或溢出），返回 Err
    // - 此处使用 `grow_amortized` 而非直接 `grow`，是为了支持分批增长策略（如翻倍）
    if let Err(err) = self.grow_amortized(self.cap.as_inner(), 1, elem_layout) {
        handle_error(err);// 触发 panic，调用栈位置由 #[track_caller] 保证
    }
}

上面这个代码就比较触及到核心了grow_amortized方法应该就是再分配内存的最终方法，我们继续查看。

代码如下：

fn grow_amortized(
    &mut self,
    len: usize,
    additional: usize,
    elem_layout: Layout,
) -> Result<(), TryReserveError> {
    // 确保调用者已保证 additional > 0，防止无效扩容
    debug_assert!(additional > 0);

    if elem_layout.size() == 0 {
       	// ZST（零大小类型）无法安全分配超过 isize::MAX 的容量 → 返回 Overflow 错误
        return Err(CapacityOverflow.into());
    }

    // 计算所需最小容量 = 当前长度 + 需新增数量
    // 若溢出（usize 范围超限），触发 CapacityOverflow
    let required_cap = len.checked_add(additional).ok_or(CapacityOverflow)?;

    // 采用「摊销增长策略」：新容量 = max(翻倍当前容量, 所需容量)
    // - 双倍增长确保 O(1) 均摊时间复杂度
    // - 保证不会因频繁 realloc 导致性能下降
    let cap = cmp::max(self.cap.as_inner() * 2, required_cap);
    // 确保容量至少为最小非零值（避免极端情况，如 layout size=8 时 cap=0 不合法）
    let cap = cmp::max(min_non_zero_cap(elem_layout.size()), cap);

    // 尝试分配新内存布局（注意：数组格式，会检查总大小是否溢出）
    let new_layout = layout_array(cap, elem_layout)?;

    // 实际分配内存并完成迁移（转移旧数据到新地址）
    let ptr = finish_grow(new_layout, self.current_memory(elem_layout), &mut self.alloc)?;
    
    // 安全设置新的指针和容量（unsafe 部分有保证：capacity overflow 已在 layout_array 中检查）
    unsafe { self.set_ptr_and_cap(ptr, cap) };
    
    Ok(())//成功扩容
}

据此，我们可以看到最核心的代码的的确确就是这一行：let cap = cmp::max(self.cap.as_inner() * 2, required_cap);

预期再分配逻辑就是原数组大小扩容到原来的两倍，但是要确保最小的扩容大小为1，也就是上一层封装传进来的参数1，我觉得这可能是为了处理可用大小为0的情况，以免0*2=0的情况发生。

额，AI说我的说法有点错误，其实这行代码的意义是：以翻倍为优先策略，但不能低于实际所需的最小容量；

真正的判零操作在let cap = cmp::max(min_non_zero_cap(elem_layout.size()), cap);这一行，不太确定对不对，之后再来重新审查。

那这一节的学习就先到这了。