深入解析 SmallVector 的 push_back 实现

背景

SmallVector 是 LLVM 项目中使用频率最高的容器，而 push_back 是其最热的操作。LLVM 近期对其 push_back 做了一项关键优化（PR #206213），核心思路是将慢路径（grow）以尾调用（tail call）方式移到函数外联（out-of-line），从而让热路径（fast path）的生成代码达到最优。这篇博客深入分析了该优化的动机、实现方式、效果，以及与 std::vector、boost::small_vector、absl::InlinedVector 等同类容器的横向对比。

核心内容

优化前的问题

对于"近似可平凡拷贝"（approximately trivially copyable）的元素类型，SmallVector::push_back 的热点路径逻辑很简单：先检查容量，容量够则直接写入；不够则扩容再写入。但问题在于，写入操作（store）在两条路径中共享：

push_back → 检查容量 → [够] → store（直接写入）
                      → [不够] → grow_pod → store（扩容后写入）

由于扩容路径需要调用 grow_pod，而该调用可能破坏 this 指针和元素 x，编译器必须将它们保存到被调用者保存寄存器（callee-saved register）中。这导致：

• 函数序言 中出现 push rbx / push rbp 等保存寄存器的指令
• push rbp 还用于维持栈帧 16 字节对齐
• 热路径被迫携带一个栈帧和额外的寄存器保存/恢复开销

Clang 生成的代码从理想的 7 条指令膨胀到 14 条。GCC 同样效率低下。

Shrink wrapping 无法解决此问题：Shrink wrapping 只能重定位 callee-saved 寄存器的保存/恢复位置，不会复制基本块。要让 this 和 x 跨越条件调用的 grow_pod 存活到共享的 store 处，callee-saved 寄存器必须从函数入口就存活——这恰恰是 shrink wrapping 无法消除的场景。Clang 的 shrink wrap 报告 No Shrink wrap candidate found，GCC 的 -fshrink-wrap-separate（在 -O2 下开启）也无能为力。

理论上，尾复制（tail duplication） 可以解决——给慢路径单独复制一份 store，让热路径的 this/x 留在参数寄存器中。但两个编译器在此处都没有做尾复制，且这也不是 shrink wrapping 的职责。

优化方案：尾调用慢路径

PR #206213 的做法是将 grow-and-store 逻辑整体移出函数体，改为尾调用一个独立的 growAndPushBack 辅助函数：

void growAndPushBack(T Elt);  // 外联、noinline、COMDAT section

优化后的热路径汇编达到最优：7 条指令（从 14 条减半），无 callee-saved 寄存器，无需 shrink wrapping。慢路径则因外联到独立函数（放在 COMDAT section 中）变得更慢——这是可接受的代价。

关键细节：

• noinline 是必不可少的，否则 Clang 和 GCC 可能将辅助函数内联回来，序言中的寄存器保存也随之回归。
• T Tmp = Elt 处理了 Elt 引用向量自身存储的情况（即自引用 push）。对于小 by-value 类型，此拷贝会被优化掉。
• 将元素以引用方式传给外联的 growAndPushBack 会导致元素被 address-taken / memory-material化（因为在另一个非内联调用中需要从固定地址读取），这对大元素类型会阻止就地构造（construct-in-place）。但由于 grow() 本身就需要拷贝 size() 个元素，这一代价可以忽略。

优化效果

• lld 的 .text 段缩小 40,512 字节；by-const& 元素类型受益最大，例如 GotSection::addConstant 从 167 字节降至 45 字节。
• 在 LLVM 编译时间追踪器上，clang 构建在所有配置下指令数（instructions:u）减少 0.41–0.51%，二进制体积增加 0.13%。
• 少数异常值（如 constexpr 字节码解释器 Interp.cpp、EvalEmitter.cpp）反而增长约 13.8%——可能因为更小的 push_back 改变了自底向上内联器在阈值附近的决策。

与 std::vector 的对比

libc++ 和 libstdc++ 的 std::vector<T>::push_back 热路径都较慢，两者都需要栈帧：

• libc++：push_back 转发到 emplace_back，后者的 grow 决策通过 std::__if_likely_else(cond, fast, slow) 路由。慢路径虽然保持外联，但是以 by-reference lambda 实现，其闭包 {&__end_, &__x, this} 被物化到栈上，且尾部的 this->__end_ = __end 是一个合并点。热路径因此溢出闭包并运行在 48 字节栈帧中。
• libstdc++ 更重：push_back 内联了 _M_realloc_insert，将整个重分配逻辑（operator new、memcpy、operator delete、length_error 抛出）拉入函数。为保持状态跨越这些调用存活，热路径在 g++ 和 clang 上都持有 6 个 callee-saved 寄存器。

相比之下，直接外联一个以寄存器传递 (this, Elt) 的成员函数（即上述 growAndPushBack），才是让热路径同时免除栈帧和 callee-saved 寄存器的关键。

注意：许多 libc++ 构建默认启用了 hardening。禁用它（以及异常）可获得最佳性能。

与 boost::small_vector 的对比

boost::container::small_vector<int, N>::push_back 讲述了同样的故事——无论内联容量 N 是多少（甚至 N == 0）：x 被溢出到栈上，仅是为了让冷路径能将其地址传给 emplace proxy，但 sub rsp, 24 和溢出指令落在了热路径上（store 本身用 esi）。

Boost 还将 size 和 capacity 存为 size_t，因此 small_vector<int, 0> 是 24 字节——和 std::vector 一样，比 SmallVector<int, 0> 多 8 字节。

与 absl::InlinedVector 的对比

absl::InlinedVector<int, 4>::push_back（clang -O2 -DNDEBUG -fno-exceptions）讲述了同样的栈帧故事，还额外多了两个分支：

• push rax 和溢出是 libc++/Boost 的翻版：冷的 EmplaceBackSlow(const T&) 按地址取元素，所以 &x 逃逸到热路径上。
• 两个 test al, 1 来自布局设计：absl::InlinedVector 将 size 和一个 is_allocated 位打包进一个字，并将内联缓冲区与 {pointer, capacity} 做 union。由于没有存储数据指针，每次访问都从该位重新推导 capacity 和基地址，因此被测试两次。

**设计取舍：