HN 日本語サマリー

← 一覧へ戻る
プログラミング

SmallVector::push_backの深掘り

A deep dive into SmallVector:push_back (maskray.me)

21 pointsby mariuz3 コメント

要約

このブログ記事では、LLVMで最も頻繁に使用されるコンテナであるSmallVectorの`push_back`操作に関する最近の最適化について詳しく説明しています。特に、ほぼ自明にコピー可能な要素型に対する高速パスのパフォーマンス向上に焦点を当てています。GCCとClangにおける既存の実装の非効率性を指摘し、テール呼び出し最適化を用いた新しいアプローチが、高速パスにおいて命令数を削減し、スタックフレームや呼び出し先保存レジスタの使用を排除する方法を解説しています。

全文翻訳

SmallVector::push_back の詳細な分析

tl;dr このブログ記事では、ほぼ自明にコピー可能な要素型に対する SmallVector::push_back の最近の最適化について説明します。

SmallVector は LLVM で最も使用されているコンテナであり、push_back はそのホットな操作です。自明にコピー可能な特殊化では、高速パスは高速であるべきです。

#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 が生成するコードは以下の通りです。

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 での格納は、容量が増えないパスと増えた後のパスで共有されます。容量が増えるパスでは、this と x は grow_pod の呼び出しを生き延びる必要があるため、callee-saved レジスタに保存され、プロローグに push rbx/push rbp が発生します。push rbp はスタックフレームの16バイトアラインメントを維持するために必要です。

GCC の出力も非効率的です。

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 ; ...

シュリンクラッピングでは除去できない

シュリンクラッピングは、callee-saved レジスタの保存/復元を移動させますが、ブロックを複製することはありません。条件付きの grow_pod 呼び出しを越えて、高速パスからも到達する格納処理に this/x を渡すには、エントリから callee-saved レジスタがライブである必要があります。clang -mllvm -debug-only=shrink-wrap は No Shrink wrap candidate found と報告します。GCC の -fshrink-wrap-separate (-O2 で有効) もこれをうまく最適化しません。

助けになる変換は、テイルデュプリケーション(tail duplication)です。スローパスに格納処理の独自のコピーを与えることで、高速パスは this/x を引数レジスタに保持できます。どちらのコンパイラもここではそれを行っておらず、それはシュリンクラッピングの仕事ではありません。

最適化:スローパスへのテイルコール

https://github.com/llvm/llvm-project/pull/206213 は、grow-and-store をインライン化せず、テイルコールします。

LLVM_ATTRIBUTE_NOINLINE void growAndPushBack(ValueParamT Elt) {
  T Tmp = Elt;  // Elt が grow() で無効になるストレージを参照する場合のため
  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);
}

生成されるアセンブリは、高速パスにおいて最適化されました。

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命令で、callee-saved レジスタもなく、シュリンクラッピングするものもありません。

インライン化されない(out-of-line)関数になったスローパス(COMDAT を使用して別のセクションに配置)は、さらに遅くなります。

noinline は負荷を担っています。そうでなければ、Clang と GCC はヘルパー関数をインライン化し、プロローグが戻ってきてしまいます。

#include <llvm/ADT/SmallVector.h>
// noinline growAndPushBack は Clang と 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 に渡すと、アドレスが取られメモリ上に展開される(別の非インライン化呼び出し全体で固定アドレスから読み取れる必要がある)ため、大きな要素型ではインプレース構築(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% 増加しました。

相対サイズでソートすると、いくつかの外れ値(~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

#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) を通じて容量増加の決定が行われます。スローパスはインライン化されませんが、参照渡しラムダとして扱われるため、そのクロージャ {&__end_, &__x, this} がスタック上に展開され、末尾の this->__end_ = __end がマージポイントとなります。したがって、高速パスはクロージャをスピルし、48 バイトのフレームで実行されます。

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 つの callee-saved レジスタを使用します。

レジスタで (this, Elt) を受け取る直接のインライン化されないメンバー関数(上記の growAndPushBack)は、高速パスをフレームと callee-saved レジスタの両方から解放します。

注: 多くの libc++ ビルドでは、デフォルトで harding が有効になっています。最高のパフォーマンスを得るには、それを無効にしてください(例外も無効にしてください)。

-fno-exceptions -D_LIBCPP_HARDENING_MODE=_LIBCPP_HARDENING_MODE_NONE

Boost の small_vector も同じフレームを持つ

boost::container::small_vector<int, N>::push_back も、インライン容量 N(N == 0 でさえ)に関係なく、同じ話です。

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 は、コールドパスの emplace プロキシにそのアドレスを渡すためだけにスピルされますが、sub rsp, 24 とスピルは高速パスに配置されます(格納自体は esi を使用します)。Boost はサイズと容量を size_t として保持するため、small_vector<int,0> は std::vector と同様に 24 バイトです。これは SmallVector<int,0> より 8 バイト大きいです。

absl::InlinedVector も同じフレームを持つ

absl::InlinedVector<int, 4>::push_back は、clang -O2 -DNDEBUG -fno-exceptions を使用すると、同じフレームの話になり、さらに2つの分岐が追加されます。

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  # size++ (it lives above bit 0)
pop    rax ; ret
.Lslow:
lea    rsi, [rsp+4] ; call …EmplaceBackSlow ; pop rax ; ret

push rax とスピルは、libc++/Boost の話と同じです。コールドパスの EmplaceBackSlow(const T&) は要素をアドレスで受け取るため、&x が高速パスにエスケープします。

2つの test al, 1 は新しく、レイアウトに由来します。absl::InlinedVector はサイズと is_allocated ビットを1つのワードにパックし、インラインバッファと {pointer, capacity} を共用します。データポインタが格納されていないため、各アクセスは容量とベースアドレスの両方をビットから再導出する必要があり、2回テストされます。その報酬は、より小さなオブジェクトです — sizeof(absl::InlinedVector<int,4>) は 32 バイトの SmallVector<int,4> に対して 24 バイトです。

SmallVector は逆のトレードオフを行います。BeginX(常にライブストレージを指す)と、sizeof(T) >= 4 の場合は個別の 32 ビットサイズと 32 ビット容量を格納します。これにより、プッシュバックはポインタと容量を無条件にロードします(ホットパスでは is_allocated ブランチなし)。そして、小容量かヒープかのテストは grow() の内部でのみ重要になります。これは <int,4> では 8 バイトのコストですが、SmallVector<int,0> は 16 バイトで、absl::InlinedVector が表現できないストレージです(N >= 1 が必要です)。

デュアル:push_back ループは std::vector を好む

テイルコールのコストは、その勝利の鏡像です。スローパスを growAndPushBack(this) としてインライン化しないことで、オブジェクトのアドレスが noinline カルリーに渡されます。単一の呼び出しでは無料ですが、ループ内では、エスケープによりオプティマイザはイテレーション全体でフィールドをレジスタに保持できなくなります。

template <class V> int drain(int n) {
  V c;                                            // a local
  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 はレジスタに保持されます。

.Lloop:                       # std::vector<int>
  mov  [rax], r13d            # *end = i
  add  rax, 4                 # ++end       (register)
  cmp  r14, rax               # end == cap? (register)
  jne  .Lloop                 # 1 memory op / element

SmallVector は各イテレーションで 3 つのフィールドすべてを再ロードします。

.Lloop:                       # llvm::SmallVector<int,0>
  mov  eax, [rsp+0x10]        # size      reload
  cmp  eax, [rsp+0x14]        # capacity  reload
  jae  .Lgrow
  mov  rcx, [rsp+0x8]         # BeginX    reload
  mov  [rcx + rax*4], ebx     # store
  inc  dword ptr [rsp+0x10]   # ++size    RMW

フィールドをレジスタに保持するには、値渡しで受け取り、新しい {BeginX, Capacity} を返すスローパスが必要です。そうすれば何もエスケープしません。しかし、その場合、push_back は書き戻すために呼び出し全体で this/Elt をライブに保つ必要があり、フレーム #206213 の削除は元に戻ってしまいます。

設計単一 push_backループ
インライン化されないメンバー + テイルコール(出荷済み)フレームなし ✅メタデータがメモリ上 ❌
値を返す growフレームなし ❌メタデータがレジスタ上 ✅

余談:「ほぼ自明にコピー可能」とは

  std::is_trivially_copy_constructible<T> &&
  std::is_trivially_move_constructible<T> &&
  std::is_trivially_destructible<T>

これは SmallVectorTemplateBase<..., true> 特殊化を選択する述語であり、コピー/ムーブ構築は memcpy に最適化され、destroy_range は何もしなくなります。

この条件は is_trivially_copyable よりも広範です。is_trivially_copyable は自明な代入も要求します。動機となるケースは std::pair<int,int> です。そのコンストラクタは自明ですが、代入演算子はユーザー提供です(pair<T&,U&> をサポートするため)。そのため is_trivially_copyable は false になります。SmallVector は要素を初期化されていないストレージにコピーまたはムーブする際に、代入ではなく常に構築(memcpy)を使用するため、この違いは観測不可能であり memcpy は安全です。そして std::pair<POD,POD> は高速パスに留まります。

この条件は、操作的な定義が is_trivially_move_constructible && is_trivially_destructible である自明な再配置可能性(trivial relocatability)よりも強力です。追加の is_trivially_copy_constructible は、SmallVector がライブ要素をコピーする場合(push_back(const T&)、または別のベクトルからのコピー構築)にも memcpy を呼び出すためです。

  is_pod  ⊆  is_trivially_copyable  ⊆  SmallVector condition  ⊆  trivially relocatable

余談:5クラス階層

SmallVector は 5 クラス階層の最下層です。クラス数は多いように見えますが、各レイヤーは正確に 1 つの軸で変化します。

SmallVectorBase<Size_T>               // T に依存しない
  SmallVectorTemplateCommon<T>        // T に依存するが、自明性には依存しない
    SmallVectorTemplateBase<T, bool>  // 近似的な自明コピー可能性で特殊化
      SmallVectorImpl<T>              // N に依存しない
        SmallVector<T, N>             // インラインバッファを追加
  • SmallVectorBase<Size_T> は 3 つのメンバー(BeginX、Size、Capacity)と、インライン化されない grow_pod/mallocForGrow を保持します。これはサイズ型でのみテンプレート化されているため、これらの 2 つのヘビー級関数はプログラム全体で 1 回ずつ(1 つは uint32_t 用、もう 1 つは uint64_t 用)生成され、要素型ごとに生成されるわけではありません。
  • SmallVectorTemplateCommon<T> は、自明な型と非自明な型の両方で同一のものを追加します。イテレータ、front/back/data/operator[]、および内部参照ヘルパーです。
  • SmallVectorTemplateBase<T, bool> は特殊化ポイントです。true の半分は memcpy と grow_pod を使用し、false の半分はコンストラクタ、destroy_range、および growAndEmplaceBack を使用します。
  • SmallVectorImpl<T> は N を消去します。SmallVectorImpl<T> & パラメータは任意のインライン容量を受け入れ、SmallVector を渡すための標準的な方法です。
  • SmallVector<T, N> はインラインバッファを保持します。

std::vector は 3 つの 8 バイトメンバーを格納します。SmallVector は、sizeof(T) >= 4 の場合、先頭ポインタに加えて 32 ビットのサイズと 32 ビットの容量を格納します。

template <class Size_T> class SmallVectorBase {
  void *BeginX;
  Size_T Size, Capacity;
};

したがって、int、ポインタ、およびほとんどの構造体の場合、ヘッダーは 16 バイトです。これは std::vector より 8 バイト少なくなります。サイズをエンドポインタの代わりに持つことのコストは、エンドアドレス(begin + size * sizeof(T))を計算するために乗算が必要になることで、sizeof(T) が2のべき乗でない場合に顕著になります。

まとめ

  • 呼び出し後に合流する高速/低速マージは、ホットパスに callee-saved レジスタのスピルを強制し、シュリンクラッピングではそれらを削除できません。
  • インライン化されないスローパスへのテイルコールにより、オーバーヘッドが除去されます。
  • インライナの動作により、サイズ効果は単調ではありません。