Pangram verdict · v3.3
We believe that this document is primarily human-written, with some AI-generated content detected
AI likelihood · overall
MixedArticle text · 1,445 words · 7 segments analyzed
tl;dr This blog post describes a recent SmallVector::push_back optimization for approximately trivially copyable element types. SmallVector is LLVM's most-used container, and push_back its hot operation. For the trivially-copyable specialization the fast path should be fast. 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 generates: 1234567891011121314151617181920push rbp # callee-saved spills + a stack realignment,push rbx # all on the fast pathpush raxmov eax, [rdi + 8] # sizecmp eax, [rdi + 12] # vs capacityjae .Lgrow.Lstore: # reached from the fast path AND from .Lgrowmov rcx, [rdi]mov [rcx + rax*4], esiinc dword ptr [rdi + 8]add rsp, 8pop rbxpop rbpret.Lgrow:mov rbx, rdi # keep `this`/`x` alive across the callmov ebp, esicall SmallVectorBase<unsigned>::grow_pod...jmp .Lstore push_back reserves capacity and then stores, so the store at .Lstore is shared between the no-grow and post-grow paths. On the grow path this and x must survive the grow_pod call, which means they are saved in callee-saved registers, leading to push rbx/push rbp in the prologue. push rbp is needed to maintain the 16-byte alignment of the stack frame.
GCC's output is also inefficient: 12345push rbp ; mov ebp, esi # x -> rbp, in the entry blockpush rbx ; mov rbx, rdi # this -> rbx... ; cmp ; jnb .Lslow.Lmerge: # reached by both paths, reads rbx/rbpmov rdx, [rbx] ; mov [rdx+rax*4], ebp ; ... Shrink wrapping can't remove it Shrink wrapping relocates the save/restore of callee-saved registers; it never duplicates a block. To carry this/x across the conditional grow_pod call into a store the fast path also reaches, a callee-saved register must be live from entry. clang -mllvm -debug-only=shrink-wrap reports No Shrink wrap candidate found. GCC's -fshrink-wrap-separate (on at -O2) does not optimize this as well. The transformation that would help is tail duplication — give the slow path its own copy of the store so the fast path keeps this/x in their argument registers. Neither compiler does it here, and it is not shrink-wrapping's job. Optimization: tail calling the slow path https://github.com/llvm/llvm-project/pull/206213 moves the grow-and-store out of line and tail calls it: 12345678910111213LLVM_ATTRIBUTE_NOINLINE void growAndPushBack(ValueParamT Elt) { T Tmp = Elt; this->grow(this->size() + 1); std::memcpy(reinterpret_cast<void *>(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<void *>(this->end()), &Elt, sizeof(T)); this->set_size(this->size() + 1);} The generated assembly is now optimal for the fast path: 1234567mov
eax, [rdi + 8]cmp eax, [rdi + 12]jae growAndPushBack # TAILCALLmov rcx, [rdi]mov [rcx + rax*4], esiinc dword ptr [rdi + 8]ret 7 instructions instead of 14, no callee-saved registers, nothing to shrink-wrap. The slow path, now in an out-of-line function (in a separate section using COMDAT), becomes even slower. noinline is load-bearing, otherwise Clang and GCC may inline the helper back and the prologue returns. 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 handles Elt referencing the vector's own storage. It is elided for small by-value types. Passing the element by reference to the out-of-line growAndPushBack makes it address-taken / memory-materialized (it must be readable at a fixed address across another non-inlined call), which defeats construct-in-place for large element types. However, this is insignificant given that grow() has to copy size() elements. Results lld .text shrinks 40,512 bytes; by-const& element types win most, e.g. GotSection::addConstant goes 167 → 45 bytes. On the LLVM compile-time tracker the clang build is 0.41–0.51% fewer instructions:u across every configuration, for +0.13% binary size. Sorted by relative size, a few outliers grow ~13.8% — the constexpr ByteCode interpreter (Interp.cpp, EvalEmitter.cpp). A smaller push_back likely perturbs the bottom-up inliner's near-threshold decisions.
std::vector<T>::push_back is slow in both libc++ and libstdc++ Both libraries need a stack frame for their vector<int>::push_back fast path. https://godbolt.org/z/5h85M9Gr9 123456789101112#include <llvm/ADT/SmallVector.h>#include <vector>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++'s push_back forwards to emplace_back, which routes the grow decision through std::__if_likely_else(cond, fast, slow). The slow path is kept out of line, but as a by-reference lambda, so its closure {&__end_, &__x, this} is materialized on the stack and the trailing this->__end_ = __end is a merge. The fast path therefore spills the closure and runs with a 48-byte frame: 123456789push rbxsub rsp, 48mov [rsp+12], esi # spill xmov rax, [rdi+8] # __endmov [rsp+16], raxlea rcx, [rsp+16] ; mov [rsp+24], rcx # } closure {&__end,lea rcx, [rsp+12] ; mov [rsp+32], rcx # } &x, this},
builtmov [rsp+40], rdi # } on the fast pathjae .Lslow # else: store x; this->__end_ = __end libstdc++ is heavier still: its push_back inlines _M_realloc_insert, pulling the whole reallocation — operator new, memcpy, operator delete, and the length_error throw — into the function. To keep state live across those calls the fast path holds six callee-saved registers, on both g++ and clang. A direct out-of-line member taking (this, Elt) in registers — the growAndPushBack above — is what keeps the fast path free of both a frame and callee-saved registers. Note: many libc++ builds enable hardening by default. Disable it (and exceptions) for the best performance: 1-fno-exceptions -D_LIBCPP_HARDENING_MODE=_LIBCPP_HARDENING_MODE_NONE Boost's small_vector has the same frame boost::container::small_vector<int, N>::push_back tells the same story, independent of the inline capacity N (even N == 0): 123456789sub rsp, 24 # frame on the fast pathmov [rsp+12], esi # spill x — dead on the fast pathmov rax, [rdi+8] # size (64-bit)lea rdx, [4*rax] ; add rdx, [rdi] ; cmp rax, [rdi+16] # end; vs capacityje .Lgrowmov [rdx], esi ; inc rax ; mov [rdi+8], rax ; add rsp, 24 ; ret.Lgrow:lea r8, [rsp+12] # &x, for vector::priv_insert_…'s insert_emplace_proxy<const int&>call ... x is spilled only so the cold grow path can pass its address to the emplace proxy, yet the sub rsp, 24 and the spill land on the fast path (the store itself uses esi).
Boost also keeps size and capacity as size_t, so small_vector<int,0> is 24 bytes — like std::vector, 8 more than SmallVector<int,0>. absl::InlinedVector has the same frame absl::InlinedVector<int, 4>::push_back, with clang -O2 -DNDEBUG -fno-exceptions, tells the same frame story and adds two branches on top: 123456789101112131415161718192021push rax # framemov [rsp+4], esi # spill x — dead here; only the cold path needs &xmov rax, [rdi] # metadata = (size << 1) | is_allocatedmov edx, 4 # inline capacity Ntest al, 1 # is_allocated? (#1: pick the capacity)je .L2mov rdx, [rdi+16] # heap capacity.L2:mov rcx, rax ; shr rcx # size = metadata >> 1cmp rcx, rdx ; je .Lslow # full?test al, 1 # is_allocated? (#2: pick the data pointer)je .L4mov rdx, [rdi+8] # heap pointerjmp .L6.L4: lea rdx, [rdi+8] # &inline buffer.L6:mov [rdx+4*rcx], esi # storeadd rax, 2 ; mov [rdi], rax # size++ (it lives above bit 0)pop rax ; ret.Lslow:lea rsi, [rsp+4] ; call …EmplaceBackSlow ; pop rax ; ret The push rax and the spill are the libc++/Boost story once more: the cold EmplaceBackSlow(const T&) takes the element by address, so &x escapes onto the fast path. The two test al, 1 are new and come from the layout.
absl::InlinedVector packs the size and an is_allocated bit into one word and unions the inline buffer with {pointer, capacity}. With no stored data pointer, each access re-derives both the capacity and the base address from the bit, so it is tested twice. The reward is a smaller object — sizeof(absl::InlinedVector<int,4>) is 24 vs SmallVector<int,4>'s 32. SmallVector makes the opposite trade: it stores BeginX (always pointing at live storage) plus separate size/capacity, so push_back loads the pointer and capacity unconditionally — no is_allocated branch on the hot path — and the small-vs-heap test only matters inside grow(). That costs 8 bytes at <int,4>, but SmallVector<int,0> is 16 bytes, the storage absl::InlinedVector can't express (it requires N >= 1). The dual: a push_back loop prefers std::vector The tail-call's cost is the mirror of its win. Out-of-lining the slow path as growAndPushBack(this) passes the object's address to a noinline callee. Free for a single call; not in a loop, where the escape stops the optimizer from keeping the fields in registers across iterations. 123456template <class 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's grow is inlined and never escapes &v, so end/cap stay in registers: 12345.Lloop: # std::vector<int> mov [rax], r13d # *end = i add rax, 4 # ++end (register) cmp r14, rax # end == cap? (