紧凑向量的内存压缩设计

在嵌入式系统或对内存极度敏感的场景中，每个字节都至关重要。今天我们来分析一个工业级**紧凑向量（Compact Vector）**实现，看看设计者如何在空间与性能之间做出权衡。

核心问题

标准库的 vector 在空状态时通常占用 24 字节（三个指针：begin, end, capacity）。在需要大量创建空容器的场景中，这会造成严重的内存浪费。

设计方案：前置元数据

// vector that is 8 bytes when empty (TVector is 24 bytes)

template <typename T>
class TCompactVector {
private:
    struct THeader {
        size_t Size;
        size_t Capacity;
    };

    T* Ptr;  // 空状态仅占用 8 字节指针

    THeader* Header() {
        return ((THeader*)Ptr) - 1;  // 元数据存储在数据之前
    }
};

关键设计决策

空状态压缩：仅存储一个指针（8字节），元数据按需分配
前置元数据：Header 存储在数据指针之前，通过指针运算定位
复制式扩容：容量不足时创建副本并交换

权衡分析

优势

极致空间：空向量仅 8 字节 vs 标准 24 字节
缓存友好：元数据与数据连续，提高缓存命中率
简单接口：与标准 vector 兼容

代价

指针运算开销：每次访问需要计算真实地址
分配复杂性：需要额外处理头部内存
复制成本：Reserve 时使用复制而非移动

净室重构：Rust 实现

use std::alloc::{alloc, dealloc, Layout};
use std::ptr::NonNull;

pub struct CompactVector<T> {
    ptr: Option<NonNull<T>>,
}

struct Header {
    size: usize,
    capacity: usize,
}

impl<T> CompactVector<T> {
    pub fn new() -> Self {
        CompactVector { ptr: None }
    }

    fn header(&self) -> Option<&Header> {
        unsafe {
            self.ptr.map(|p| {
                let header_ptr = (p.as_ptr() as *mut Header).offset(-1);
                &*header_ptr
            })
        }
    }

    fn header_mut(&mut self) -> Option<&mut Header> {
        unsafe {
            self.ptr.as_mut().map(|p| {
                let header_ptr = (p.as_ptr() as *mut Header).offset(-1);
                &mut *header_ptr
            })
        }
    }

    pub fn size(&self) -> usize {
        self.header().map(|h| h.size).unwrap_or(0)
    }

    pub fn capacity(&self) -> usize {
        self.header().map(|h| h.capacity).unwrap_or(0)
    }

    pub fn push(&mut self, value: T) {
        self.reserve(self.size() + 1);
        
        unsafe {
            let ptr = self.ptr.unwrap().as_ptr();
            let idx = self.header_mut().unwrap().size;
            ptr.add(idx).write(value);
            self.header_mut().unwrap().size += 1;
        }
    }

    pub fn reserve(&mut self, new_cap: usize) {
        if new_cap <= self.capacity() {
            return;
        }

        let new_layout = Layout::new::<T>()
            .extend(Layout::new::<Header>())
            .unwrap()
            .0
            .pad_to_align();

        unsafe {
            let new_ptr = alloc(new_layout) as *mut T;
            let header_ptr = new_ptr.offset(-1) as *mut Header;
            
            // 移动现有数据
            if let Some(old_ptr) = self.ptr {
                let old_size = self.size();
                old_ptr.as_ptr().copy_to_nonoverlapping(new_ptr, old_size);
                
                // 释放旧内存
                let old_layout = Layout::new::<T>()
                    .extend(Layout::new::<Header>())
                    .unwrap()
                    .0
                    .pad_to_align();
                dealloc(old_ptr.as_ptr().offset(-1) as *mut u8, old_layout);
            }
            
            // 初始化新头部
            header_ptr.write(Header {
                size: self.size(),
                capacity: new_cap,
            });
            
            self.ptr = NonNull::new(new_ptr);
        }
    }

    pub fn get(&self, index: usize) -> Option<&T> {
        if index < self.size() {
            unsafe {
                Some(&*self.ptr.unwrap().as_ptr().add(index))
            }
        } else {
            None
        }
    }
}

impl<T> Drop for CompactVector<T> {
    fn drop(&mut self) {
        if let Some(ptr) = self.ptr {
            unsafe {
                // 调用析构函数
                for i in 0..self.size() {
                    ptr.as_ptr().add(i).drop_in_place();
                }
                
                // 释放内存
                let layout = Layout::new::<T>()
                    .extend(Layout::new::<Header>())
                    .unwrap()
                    .0
                    .pad_to_align();
                dealloc(ptr.as_ptr().offset(-1) as *mut u8, layout);
            }
        }
    }
}

总结

紧凑向量设计体现了空间换时间的经典权衡：

空状态压缩：从 24 字节到 8 字节，适合大量空容器场景
前置元数据：通过指针算术实现紧凑布局
复制式扩容：简化实现但有性能开销

这种设计在内存受限的嵌入式环境或需要创建大量容器的场景中非常有效。