SmallVector::push_backの深掘り

2026-06-27 tl;dr このブログ記事は、ほぼ自明にコピー可能な要素型に対するSmallVector::push_backの最近の最適化について説明します。SmallVectorはLLVMで最も多く使用されているコンテナであり、push_backはそのホットな操作です。自明にコピー可能な特殊化の場合、高速パスは高速であるべきです。 ```c #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` は以下を生成します。 ```assembly push rbp # callee-saved spills + a stack realignment, push rbx # all on the fast path push rax mov eax, [rdi + 8] # size cmp eax, [rdi + 12] # vs capacity jae .Lgrow .Lstore: # reached from the fast path AND from .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 # keep `this`/`x` alive across the call mov ebp, esi call SmallVectorBase<unsigned>::grow_pod... jmp .Lstore ``` `push_back`は容量を確保してから格納するため、`.Lstore`での格納は、growなしパスとgrow後パスで共有されます。growパスでは、`this`と`x`が`grow_pod`呼び出し後も存続する必要があるため、呼び出し先保存レジスタに保存され、プロローグで`push rbx`/`push rbp`が発生します。`push rbp`はスタックフレームの16バイトアライメントを維持するために必要です。GCCの出力も非効率的です。 ```assembly push rbp ; mov ebp, esi # x -> rbp, in the entry block push rbx ; mov rbx, rdi # this -> rbx ... ; cmp ; jnb .Lslow .Lmerge: # reached by both paths, reads rbx/rbp mov rdx, [rbx] ; mov [rdx+rax*4], ebp ; ... ``` **シュリンクラッピングでは削除できない** シュリンクラッピングは、呼び出し先保存レジスタの保存/復元を再配置しますが、ブロックを複製することはありません。条件付きの`grow_pod`呼び出しを超えて、高速パスも到達するストアに`this`/`x`を渡すには、エントリから呼び出し先保存レジスタがライブでなければなりません。`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 は、growとストアをアウトオブラインに移動し、それをテール呼び出しします。 ```c LLVM_ATTRIBUTE_NOINLINE void growAndPushBack(ValueParamT Elt) { T Tmp = Elt; // in case Elt aliases storage that grow() invalidates 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); } ``` 生成されるアセンブリは高速パスに対して最適になります。 ```assembly mov eax, [rdi + 8] cmp eax, [rdi + 12] jae growAndPushBack # TAILCALL mov rcx, [rdi] mov [rcx + rax*4], esi inc dword ptr [rdi + 8] ret ``` 14命令ではなく7命令で、呼び出し先保存レジスタはなく、シュリンクラッピングするものもありません。アウトオブライン関数（COMDATを使用して別のセクション）になった低速パスは、さらに遅くなります。`noinline`は、そうでなければClangとGCCがヘルパーをインライン化し、プロローグが戻ってしまうため、重要です。 ```c #include <llvm/ADT/SmallVector.h> // noinline growAndPushBack is load-bearing for both Clang and GCC. 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コンパイル時間トラッカーでは、clangビルドはすべての構成で0.41〜0.51%少ない命令数になり、バイナリサイズは+0.13%です。相対サイズでソートすると、いくつかの外れ値が約13.8%成長します。これはconstexpr ByteCodeインタープリタ（`Interp.cpp`, `EvalEmitter.cpp`）です。より小さな`push_back`は、ボトムアップインライナの閾値に近い決定を乱す可能性があります。 **std::vector<T>::push_backはlibc++とlibstdc++の両方で遅い** 両方のライブラリは、`vector<int>::push_back`高速パスにスタックフレームを必要とします。https://godbolt.org/z/5h85M9Gr9 ```c #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++の`push_back`は`emplace_back`に転送され、これは`std::__if_likely_else(cond, fast, slow)`を介してgrowの決定をルーティングします。低速パスはアウトオブラインに保たれますが、参照渡しラムダとして、そのクロージャ`{&__end_, &__x, this}`がスタック上に実体化され、末尾の`this->__end_ = __end`はマージです。したがって、高速パスはクロージャをスピルし、48バイトのフレームで実行されます。 ```assembly push rbx sub rsp, 48 mov [rsp+12], esi # spill x mov rax, [rdi+8] # __end mov [rsp+16], rax lea rcx, [rsp+16] ; mov [rsp+24], rcx # } closure {&__end, lea rcx, [rsp+12] ; mov [rsp+32], rcx # } &x, this}, built mov [rsp+40], rdi # } on the fast path jae .Lslow # else: store x; this->__end_ = __end ``` libstdc++はさらに重く、その`push_back`は`_M_realloc_insert`をインライン化し、再割り当て全体（`operator new`、`memcpy`、`operator delete`、`length_error`スロー）を関数内に引き込みます。これらの呼び出しを超えて状態をライブに保つために、高速パスはg++とclangの両方で6つの呼び出し先保存レジスタを保持します。レジスタで`(this, Elt)`を受け取る直接アウトオブラインメンバー（上記の`growAndPushBack`）が、高速パスをフレームも呼び出し先保存レジスタも使用しないようにします。 注: 多くのlibc++ビルドはデフォルトでハーデニングを有効にしています。最高のパフォーマンスを得るには、それを（および例外を）無効にしてください: `-fno-exceptions -D_LIBCPP_HARDENING_MODE=_LIBCPP_HARDENING_MODE_NONE` **Boostのsmall_vectorも同じフレームを持つ** `boost::container::small_vector<int, N>::push_back`も同じ話で、インライン容量N（N == 0であっても）とは無関係です。 ```assembly sub rsp, 24 # frame on the fast path mov [rsp+12], esi # spill x — dead on the fast path mov rax, [rdi+8] # size (64-bit) lea rdx, [4*rax] ; add rdx, [rdi] ; cmp rax, [rdi+16] # end; vs capacity je .Lgrow mov [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`は、コールドなgrowパスがそのアドレスをemplaceプロキシに渡せるようにするためだけにスピルされますが、`sub rsp, 24`とスピルは高速パスに割り当てられます（ストア自体は`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`を使用しても同じフレームの物語を語り、さらに2つのブランチを追加します。 ```assembly push rax # frame mov [rsp+4], esi # spill x — dead here; only the cold path needs &x mov rax, [rdi] # metadata = (size << 1) | is_allocated mov edx, 4 # inline capacity N test al, 1 # is_allocated? (#1: pick the capacity) je .L2 mov rdx, [rdi+16] # heap capacity .L2:mov rcx, rax ; shr rcx # size = metadata >> 1 cmp rcx, rdx ; je .Lslow # full? test al, 1 # is_allocated? (#2: pick the data pointer) je .L4 mov rdx, [rdi+8] # heap pointer jmp .L6 .L4: lea rdx, [rdi+8] # &inline buffer .L6:mov [rdx+4*rcx], esi # store add rax, 2 ; mov [rdi], rax ```