动态数组：针对开发者的内存和性能优化

动态数组优化：开发者内存管理策略

动态数组是核心数据结构，但内存管理不当往往导致性能瓶颈。主要问题是重分配，将 O(1) 插入操作变成 O(n)。我们来深入探讨实用优化策略，从增长因子到容量预留和小向量优化。

重分配问题与指数增长

朴素的动态数组实现，每次溢出只增长一个元素，会导致灾难性性能。插入 1000 个元素需要 1000 次重分配，复制 500,500 个元素。解决方案？采用指数容量增长，通常翻倍。

void add_message(log_buffer_t *buf, const char *msg) {
    if (buf->size >= buf->capacity) {
        buf->capacity = buf->capacity ? buf->capacity * 2 : 16;
        buf->messages = realloc(buf->messages, 
                               buf->capacity * sizeof(char*));
    }
    buf->messages[buf->size++] = strdup(msg);
}

1000 个元素的结果：

• 重分配次数：7 次（对比 1000 次）。
• 复制元素数：约 2000 个（对比 500,500 个）。
• 加速比：60 倍。

过度分配策略用于降低延迟，在各系统中广泛应用：

• 字符串构建器（如 StringBuilder）避免 O(n²) 串联。
• TCP 网络缓冲区减少系统调用。
• 内存分配器使用大小类别对抗碎片化。
• 数据库日志预分配块以最小化磁盘 I/O。

增长因子实现与分析

基本的 C 动态数组包含数据指针、大小和容量。关键的 vector_push 函数检查是否需要重分配。

选择增长因子需平衡速度与内存使用：

• 2× 增长：标准（std::vector、Python 列表）。速度快（位移友好），最小化重分配，但浪费高达 50% 内存。
• 1.5× 增长：某些库使用（如 folly）。内存效率更高（约 33% 浪费），但重分配更多。
• φ (1.618)：理论最优点。

基准测试增长到 100 万元素：

• 1.5×：34 次重分配，峰值内存 1.5 MB，12 ms。
• 2×：20 次重分配，峰值内存 2 MB，8 ms。

推荐：内存充足时用 2× 以获最佳速度。

容量收缩与预留

删除时自动收缩可能导致性能抖动，如果大小徘徊在阈值附近。size < capacity / 2 时收缩会触发频繁重分配。

最佳实践：

• 迟滞机制：仅当 size < capacity / 4 时收缩，提供缓冲区。
• 显式收缩：提供 shrink_to_fit 供手动控制。

如果知道最终大小，提前预留可完全跳过重分配。

vector_reserve(&v, 1000);
for (int i = 0; i < 1000; i++) {
    vector_push(&v, i); // 无重分配
}

基准测试（1000 个元素）：

• 无预留：7 次重分配，45 µs。
• 有预留：1 次重分配，12 µs（加速 3.75 倍）。

小向量优化

对于微小向量，堆分配开销占主导。解决方案：小向量优化——前 N 个元素内联存储。

#define SMALL_SIZE 16
typedef struct {
    int small_data[SMALL_SIZE]; // 内联存储
    int *data;                  // 溢出时堆指针
    size_t size;
    size_t capacity;
} small_vector_t;

优点：

• ≤16 个元素零分配。
• 更好的缓存局部性。
• 小集合处理极快。

缺点：

• 结构体更大。
• 转堆时复制开销。

核心要点

• 指数增长（2× 因子）将均摊插入成本从 O(n) 降至 O(1)。
• 预留已知大小可消除重分配，大幅提升速度。
• 自动收缩往往有害；优先迟滞或手动方法。
• 小向量优化消除微小集合的分配开销。
• 增长因子选择在速度与内存效率间权衡。

— Editorial Team