深入探究 SmallVector::push_back

# 深入解析 SmallVector::push_back 来源：https://maskray.me/blog/2026-06-27-a-deep-dive-into-smallvector-push-back tl;dr 这篇博客介绍了一项针对近似平凡可复制元素类型的 `SmallVector::push_back` 的近期优化。`SmallVector` 是 LLVM 中使用最频繁的容器，而 `push_back` 是其热点操作。对于平凡可复制特化版本，快速路径应当做到足够快。 `` 123 `` `` #include <llvm/ADT/SmallVector.h> void f(llvm::SmallVectorImpl<int> &v, int x) { v.push_back(x); } `` `clang -S --target=x86_64 -O2 -DNDEBUG a.cc` 生成以下汇编： `` 1234567891011121314151617181920 `` `` push rbp # 保存调用者保存的寄存器 + 栈对齐， push rbx # 全部在快速路径上 push rax mov eax, [rdi + 8] # size cmp eax, [rdi + 12] # 与 capacity 比较 jae .Lgrow .Lstore: # 快速路径和 .Lgrow 分支都能到达 mov rcx, [rdi] mov [rcx + rax*4], esi inc dword ptr [rdi + 8] add rsp, 8 pop rbx pop rbp ret .Lgrow: mov rbx, rdi # 在调用期间保持 `this`/`x` 存活 mov ebp, esi call SmallVectorBase::grow_pod... jmp .Lstore `` `push_back` 先预留容量，*然后* 才存储，因此 `\.Lstore` 处的存储被不增长和增长后两条路径共享。在增长路径上，`this` 和 `x` 必须在 `grow_pod` 调用后仍然存活，这意味着它们被保存在调用者保存寄存器中，从而在函数序言中引入了 `push rbx` / `push rbp`。`push rbp` 是为了维持栈帧的 16 字节对齐。GCC 的输出同样低效： `` 12345 `` `` push rbp ; mov ebp, esi # x -> rbp，在入口块中 push rbx ; mov rbx, rdi # this -> rbx ... ; cmp ; jnb .Lslow .Lmerge: # 两条路径都到达，读取 rbx/rbp mov rdx, [rbx] ; mov [rdx+rax*4], ebp ; ... `` ## 收缩包装无法移除它们 收缩包装会重新定位调用者保存寄存器的保存/恢复操作；它从不复制基本块。为了将 `this`/`x` 通过条件性的 `grow_pod` 调用传递到快速路径也能到达的存储中，调用者保存寄存器必须从入口处就保持活跃。`clang -mllvm -debug-only=shrink-wrap` 报告 `No Shrink wrap candidate found`。GCC 的 `-fshrink-wrap-separate`（在 `-O2` 下开启）也无法优化这一点。真正有帮助的变换是尾复制——为慢速路径提供自己的存储副本，这样快速路径就可以将 `this`/`x` 保留在参数寄存器中。两个编译器在此处都没有这样做，而且这也不是收缩包装的职责。 ## 优化：对慢速路径进行尾调用 https://github.com/llvm/llvm-project/pull/206213 将增长并存储的操作移到行外，并使用尾调用： `` 12345678910111213 `` `` LLVM_ATTRIBUTE_NOINLINE void growAndPushBack(ValueParamT Elt) { T Tmp = Elt; this->grow(this->size() + 1); std::memcpy(reinterpret_cast<T*>(this->end()), &Tmp, sizeof(T)); this->set_size(this->size() + 1); } void push_back(ValueParamT Elt) { if (LLVM_UNLIKELY(this->size() >= this->capacity())) return growAndPushBack(Elt); std::memcpy(reinterpret_cast<T*>(this->end()), &Elt, sizeof(T)); this->set_size(this->size() + 1); } `` 现在快速路径生成的汇编是最优的： `` 1234567 `` `` mov eax, [rdi + 8] cmp eax, [rdi + 12] jae growAndPushBack # 尾调用 mov rcx, [rdi] mov [rcx + rax*4], esi inc dword ptr [rdi + 8] ret `` 从 14 条指令减少到 7 条，没有调用者保存寄存器，无需进行收缩包装。慢速路径现在位于行外函数中（使用 COMDAT 放在单独的节中），变得更慢。`noinline` 属性至关重要，否则 Clang 和 GCC 可能会将辅助函数内联回来，序言部分也会恢复。 `` 1234567 `` `` #include <llvm/ADT/SmallVector.h> void DecodeMOVDDUPMask(unsigned n, llvm::SmallVectorImpl<int> &v) { for (unsigned l = 0; l < n; l += 2) for (unsigned i = 0; i < 2; ++i) v.push_back(i); } `` `T Tmp = Elt` 处理 `Elt` 引用向量自身存储的情况。对于小型按值传递类型，这一步骤会被消除。将元素以引用方式传递给行外的 `growAndPushBack` 会导致元素被取地址/内存化（它必须在一个固定地址上跨另一个非内联调用可读），这会破坏大型元素类型的原地构造。不过，考虑到 `grow()` 必须复制 `size()` 个元素，这一点影响可以忽略。 ## 结果 `lld` 的 `.text` 段缩小了 40,512 字节；按 `const&` 传递元素类型收益最大，例如 `GotSection::addConstant` 从 167 字节缩减到 45 字节。 在 LLVM 编译时间追踪器（https://llvm-compile-time-tracker.com/）上，clang 构建在每种配置下 `instructions:u` 减少了 0.41–0.51%，同时二进制大小增加 0.13%。按相对大小排序，少数几个文件增长了约 13.8%——这些是 constexpr 字节码解释器（`Interp.cpp`、`EvalEmitter.cpp`）。更小的 `push_back` 很可能干扰了自底向上内联器在阈值附近的决策。 ## `std::vector::push_back` 在 libc++ 和 libstdc++ 中均较慢 两个库都需要为 `vector::push_back` 的快速路径分配栈帧。 https://godbolt.org/z/5h85M9Gr9 `` 123456789101112 `` `` #include <vector> #include <llvm/ADT/SmallVector.h> void pb_int(std::vector<int> &v, int x) { v.push_back(x); } void pb_int(llvm::SmallVectorImpl<int> &v, int x) { v.push_back(x); } struct T {int x[32];}; void pb_Tcreate(std::vector<T> &v, int x){ v.push_back(T{{x, 1}}); } void pb_Tcopy(std::vector<T> &v, const T &t){ v.push_back(t); } void pb_Tcreate(llvm::SmallVectorImpl<T> &v, int x){ v.push_back(T{{x, 1}}); } void pb_Tcopy(llvm::SmallVectorImpl<T> &v, const T &t){ v.push_back(t); } `` libc++ 的 `push_back` 转发到 `emplace_back`，后者通过 `std::__if_likely_else(cond, fast, slow)` 来路由增长决策。慢速路径被保留在行外，但作为一个按引用传递的 lambda，其闭包 `{&__end_, &__x, this}` 被分配到栈上，并且尾部的 `this->__end_ = __end` 是一个合并点。因此快速路径需要溢出闭包，并拥有一个 48 字节的栈帧： `` 123456789 `` `` push rbx sub rsp, 48 mov [rsp+12], esi # 溢出 x mov rax, [rdi+8] # __end mov [rsp+16], rax lea rcx, [rsp+16] ; mov [rsp+24], rcx # } 闭包 {&__end, lea rcx, [rsp+12] ; mov [rsp+32], rcx # } &x, this}，在快速路径上构建 mov [rsp+40], rdi # } jae .Lslow # else: 存储 x; this->__end_ = __end `` libstdc++ 更重：它的 `push_back` 内联了 `_M_realloc_insert`，将整个重新分配过程——`operator new`、`memcpy`、`operator delete` 以及 `length_error` 抛出——都拉入函数内。为了在这些调用期间保持状态存活，快速路径在 g++ 和 clang 下都需要保存六个调用者保存寄存器。一个直接接受 `(this, Elt)` 寄存器参数的脱机成员函数——即上面的 `growAndPushBack`——是让快速路径既无栈帧也无调用者保存寄存器的关键。 注意：许多 libc++ 构建默认启用了强化模式（https://libcxx.llvm.org/Hardening.html）。为了获得最佳性能，请禁用它（以及异常）： `` 1 `` `` -fno-exceptions -D_LIBCPP_HARDENING_MODE=_LIBCPP_HARDENING_MODE_NONE `` ## Boost 的 small_vector 也有相同的栈帧 `boost::container::small_vector::push_back` 的情况类似，无论内联容量 `N` 是多少（即使 `N == 0`）： `` 123456789 `` `` sub rsp, 24 # 快速路径上的栈帧 mov [rsp+12], esi # 溢出 x — 在快速路径上无用处 mov rax, [rdi+8] # size（64 位） lea rdx, [4*rax] ; add rdx, [rdi] ; cmp rax, [rdi+16] # end; 与 capacity 比较 je .Lgrow mov [rdx], esi ; inc rax ; mov [rdi+8], rax ; add rsp, 24 ; ret .Lgrow: lea r8, [rsp+12] # &x，用于 vector::priv_insert_... 的 insert_emplace_proxy call ... `` `x` 被溢出仅仅是为了让冷路径的增长操作能够将其地址传递给 emplace 代理，然而 `sub rsp, 24` 和溢出都落在了快速路径上（存储本身使用的是 `esi`）。Boost 还将 size 和 capacity 作为 `size_t` 存储，因此 `small_vector` 占用 24 字节——与 `std::vector` 一样，比 `SmallVector` 多 8 字节。 ## `absl::InlinedVector` 也有相同的栈帧 `absl::InlinedVector::push_back`，使用 `clang -O2 -DNDEBUG -fno-exceptions`，同样有栈帧故事，并且还多了两个分支： `` 123456789101112131415161718192021 `` `` push rax # 栈帧 mov [rsp+4], esi # 溢出 x — 此处无用；只有冷路径需要 &x mov rax, [rdi] # metadata = (size << 1) | is_allocated mov edx, 4 # 内联容量 N test al, 1 # is_allocated? (#1: 获取容量) je .L2 mov rdx, [rdi+16] # 堆容量 .L2: mov rcx, rax ; shr rcx # size = metadata >> 1 cmp rcx, rdx ; je .Lslow # 满了？ test al, 1 # is_allocated? (#2: 获取数据指针) je .L4 mov rdx, [rdi+8] # 堆指针 jmp .L6 .L4: lea rdx, [rdi+8] # &内联缓冲区 .L6: mov [rdx+4*rcx], esi # 存储 add rax, 2 ; mov [rdi], rax # size++（位于 bit 0 之上） pop rax ; ret .Lslow: lea rsi, [rsp+4] ; call ...EmplaceBackSlow ; pop rax ; ret `` `push rax` 和溢出再次重演了 libc++/Boost 的故事：冷路径的 `EmplaceBackSlow(const T&)` 通过地址接收元素，因此 `&x` 逃逸到了快速路径。两个 `test al, 1` 是新增的，来自于其布局。`absl::InlinedVector` 将 size 和一个 `is_allocated` 位打包到一个字中，并将内联缓冲区与 `{pointer, capacity}` 联合。由于没有存储数据指针，每次访问都需要从该位中重新推导 *容量* 和 *基地址*，因此需要两次测试。它的回报是更小的对象——`sizeof(absl::InlinedVector)` 为 24 字节，而 `SmallVector` 为 32 字节。 `SmallVector` 做出了相反的选择：它存储 `BeginX`（始终指向活动存储）以及单独的 `size`/`capacity`，因此 push_back 无条件加载指针和容量——热路径上没有 `is_allocated` 分支——小/堆测试只在 `grow()` 内部才相关。这花费了 8 字节，但 `SmallVector` 可以只有 16 字节（当 N=0 时），这是 `absl::InlinedVector` 无法表达的（它要求 `N >= 1`）。 ## 对立面：`push_back` 循环更喜欢 `std::vector` 尾调用的代价正是其优势的镜像。将慢速路径作为 `growAndPushBack(this)` 脱机，会将对象的地址传递给一个 `noinline` 函数。对于单次调用无所谓；但在循环中，这种逃逸会阻止优化器将字段保持在寄存器中跨迭代。 `` 123456 `` `` template <typename V> int drain(int n) { V c; for (int i = 0; i < n; ++i) c.push_back(i); int s = 0; while (!c.empty()) { s += c.back(); c.pop_back(); } return s; } `` `std::vector` 的增长被内联，`&v` 从未逃逸，因此 `end`/`cap` 可以保持在寄存器中： `` 12345 `` `` .Lloop: # std::vector mov [rax], r13d # *end = i add rax, 4 # ++end（寄存器） cmp r14, rax # end == cap?（寄存器） jne .Lloop # 每次迭代 1 次内存操作 `` `SmallVector` 每次迭代都需要重新加载所有三个字段： `` 1234567 `` `` .Lloop: # llvm::SmallVector mov eax, [rsp+0x10] # size 重新加载 cmp eax, [rsp+0x14] # capacity 重新加载 jae .Lgrow mov rcx, [rsp+0x8] # BeginX 重新加载 mov [rcx + rax*4], ebx # 存储 inc dword ptr [rsp+0x10] # ++size 读改写 `` 要将字段保持在寄存器中，需要一个慢速路径，它以 *值* 方式接收它们并且 *返回* 新的 `{BeginX, Capacity}`——这样就没有任何东西逃逸。但这样一来，`push_back` 必须在调用期间保持 `this`/`Elt` 存活以写回结果，而 PR #206213（https://github.com/llvm/llvm-project/pull/206213）移除的帧又回来了。 | 设计 | 单个 `push_back` | 循环 | |------|------------------|------| | 脱机成员 + 尾调用（已发布） | 无帧 ✅ | 元数据在内存中 ❌ | | 返回值增长 | 有帧 ❌ | 元数据在寄存器中 ✅ | ## 附注：“近似平凡可复制” `` 123 `` `` std::is_trivially_copy_constructible && std::is_trivially_move_constructible && std::is_trivially_destructible `` 这个谓词用于选择 `SmallVectorTemplateBase<..., true>` 特化版本，其中拷贝/移动构造优化为 `memcpy`，`destroy_range` 为空操作。该条件比 `is_trivially_copyable` 更宽泛，后者还要求平凡的赋值操作。动机案例是 `std::pair`：其构造函数是平凡的，但其赋值是用户提供的（为了支持 `pair`），因此 `is_trivially_copyable` 为 `false`。`SmallVector` 只通过构造将元素拷贝或移动到未初始化存储中（使用 `memcpy`），从不通过赋值，因此这种区分是不可观察的，使用 `memcpy` 是安全的——并且 `std::pair` 可以留在快速路径上。 该条件也比平凡可重定位（trivially relocatable）更强，后者仅要求 `is_trivially_move_constructible && is_trivially_destructible`。额外的 `is_trivially_copy_constructible` 是因为 `SmallVector` 在 *拷贝* 一个活动元素时也会调用 `memcpy`——例如 `push_back(const T&)`，或从另一个向量拷贝构造。 `` 1 `` `` is_pod ⊆ is_trivially_copyable ⊆ SmallVector 条件 ⊆ 平凡可重定位 `` ## 附注：五层类层次结构 `SmallVector` 是一个五层类层次结构的底层。层数看起来很多，但每一层只在一个轴向上变化： `` 12345 `` `` SmallVectorBase SmallVectorTemplateCommon SmallVectorTemplateBase SmallVectorImpl SmallVector `` - `SmallVectorBase` 持有三个成员（`BeginX`、`Size`、`Capacity`）以及脱机的 `grow_pod`/`mallocForGrow`。它只以大小类型为模板，因此这两个重量级函数在整个程序中只被实例化两次——一个用 `uint32_t`，一个用 `uint64_t`——而不是每种元素类型一次。 - `SmallVectorTemplateCommon` 添加了平凡和非平凡 `T` 都相同的内容：迭代器、`front`/`back`/`data`/`operator[]`，以及内部引用辅助函数。 - `SmallVectorTemplateBase` 是特化点。`true` 的一半使用 `memcpy` 和 `grow_pod`；`false` 的一半使用构造函数、`destroy_range` 和 `growAndEmplaceBack`。 - `SmallVectorImpl` 抹除了 `N`。一个 `SmallVectorImpl &` 参数可以接受任何内联容量，是传递 `SmallVector` 的规范方式。 - `SmallVector` 携带内联缓冲区。 `std::vector` 存储三个 8 字节成员。当 `sizeof(T) >= 4` 时，`SmallVector` 存储一个起始指针加上一个 32 位 size 和一个 32 位 capacity。 `` 1234 `` `` template <class Size_T> class SmallVectorBase { void *BeginX; Size_T Size, Capacity; }; `` 因此对于 `int`、指针和大多数结构体，其头信息只有 **16 字节**——比 `std::vector` 少 8 字节。使用 size 而不是 end 指针的代价是计算末尾地址（`begin + size * sizeof(T)`）时需要一次乘法，这在 `sizeof(T)` 不是 2 的幂时可见。 ## 要点 - 在调用后重新合并的快速/慢速路径会将调用者保存寄存器的溢出引入热路径，并且收缩包装无法将其移除。 - 对慢速路径进行尾调用的脱机实现可以消除这种开销。 - 内联器的行为使得代码尺寸的影响不是单调的。