极简的代价：紧凑型向量（Compact Vector）的内存布局艺术

在系统编程中，每一字节都值得计较。标准库的 Vec<T> 虽然通用且强大，但它的内存布局对于某些极端场景来说过于“奢侈”了。

标准向量的“肥胖”问题

一个标准的 Vec<T>（或者 C++ 中的 std::vector）通常占用 24 字节（在 64 位系统上）：

指针（8 字节）
容量（8 字节）
长度（8 字节）

如果你有一个包含数百万个节点的图，每个节点都有一个邻接表（adjacency list）。如果这个图很稀疏，大部分节点的邻接表可能是空的。即便为空，每个节点也要为此付出 24 字节的代价。如果有 1 亿个节点，这就是 2.4 GB 的内存开销——仅仅是为了表示“空”。

紧凑型设计：Header Pre-allocation

为了解决这个问题，我们可以采用一种更紧凑的设计：将元数据（容量和长度）隐藏到堆内存的头部，栈上只保留一个指针。

这种设计被称为 Compact Vector 或 Slim Vector。

空状态：只有一个空指针（8 字节）。开销是标准向量的三分之一。
非空状态：指针指向堆内存块。这个内存块的头部存储了 capacity 和 len，紧接着才是真正的数据。

Rust 实现演练

要在 Rust 中实现这种结构，我们需要玩转 unsafe 和裸指针布局。

use std::alloc::{alloc, dealloc, realloc, Layout};
use std::ptr::{self, NonNull};
use std::marker::PhantomData;

// 隐藏在数据前面的头部信息
#[repr(C)]
struct Header {
    len: usize,
    cap: usize,
}

pub struct SlimVec<T> {
    // 指向 Header 的指针，数据紧随其后
    // 如果为 None，表示空向量
    ptr: Option<NonNull<Header>>,
    _marker: PhantomData<T>,
}

impl<T> SlimVec<T> {
    pub fn new() -> Self {
        Self { ptr: None, _marker: PhantomData }
    }

    pub fn push(&mut self, elem: T) {
        if let Some(header_ptr) = self.ptr {
            unsafe {
                let header = header_ptr.as_ptr();
                if (*header).len == (*header).cap {
                    self.grow();
                }
                // 写入数据
                let header = self.ptr.unwrap().as_ptr();
                let data_ptr = (header as *mut u8).add(std::mem::size_of::<Header>()) as *mut T;
                ptr::write(data_ptr.add((*header).len), elem);
                (*header).len += 1;
            }
        } else {
            self.allocate_initial(elem);
        }
    }

    // ... 省略了复杂的 grow, allocate_initial 和 Drop 实现 ...
}

// 仅仅为了演示布局大小
fn main() {
    println!("Standard Vec size: {}", std::mem::size_of::<Vec<i32>>());
    println!("SlimVec size:      {}", std::mem::size_of::<SlimVec<i32>>());
}

运行结果将是：

Standard Vec size: 24
SlimVec size:      8

代价是什么？

天下没有免费的午餐。虽然我们节省了内存，但付出了 CPU 指令的代价：

间接访问：获取长度或容量不再是直接读取栈变量，而是需要解引用指针访问堆内存（可能导致 Cache Miss）。
指针计算：每次访问元素，都需要先跳过头部（Header），这增加了一次加法运算。
分支判断：每次操作前都要检查指针是否为空。

结语

Compact Vector 是一种典型的“空间换时间”的反向操作——或者更准确地说，是“牺牲微小的访问延迟换取巨大的内存节省”。在图计算、DOM 树构建等拥有海量小对象的场景下，这种优化是值得的。它提醒我们：标准库是通用的最优解，但并非特定场景的唯一解。