最速のブランチレス二分探索

 (mhdm.dev)
1 ポイント 投稿者 GN⁺ 2023-08-13 | 1件のコメント | WhatsAppで共有
  • sb_lower_bound は std::lower_bound と同じインターフェースを保ちながら、比較分岐が 条件付き移動 (cmov) にコンパイルされる場合、通常の二分探索より最大 2 倍高速という結果を示した
  • 二分探索の比較結果は探索位置を事前に予測できないため、分岐予測ミス が起こりやすく、x86 では clang -mllvm -x86-cmov-converter=false オプションがこれを減らすのに役立つ
  • この実装はループごとに length を半分にし、比較結果に応じて first だけを更新することで命令数を減らし、2^k <= n < 2^(k+1) の範囲で常に k+1 回比較する
  • clang -cmov ベンチマークでは平均実行時間が std::lower_bound 61.30ns、sb_lower_bound 33.24ns、bb_lower_bound 32.73ns で、幾何平均もそれぞれ 39.17ns、19.81ns、21.33ns と差が大きかった
  • 比較関数が遅い 8 バイト文字列探索では std::lower_bound がわずかに上回る場合があり、大きな配列では プリフェッチ を加えた変種が std::lower_bound より平均で約 2.3 倍高速だった

sb_lower_bound の基本構造

  • sb_lower_bound は std::lower_bound と同じ形の C++ 関数
    • 入力は first, last, value, comp
    • 戻り値は比較が最初に失敗する位置のイテレータで、すべての要素が条件を満たすなら last を返す
  • 核心のループでは length を半分にし、comp(first[length], value) が真のときだけ first を前に進める
  • ここでいう “branchless” は if が消えることではなく、その if が 条件付きジャンプ の代わりに cmov のような条件付き移動命令へコンパイルされる場合を指す
  • clang では -mllvm -x86-cmov-converter=false オプションを使うと、この形が条件付き移動にコンパイルされうる

std::lower_bound が遅くなる箇所

  • 一般的な二分探索は中央要素と value を比較した後、左側または右側の区間を選ぶ
  • 探索対象の位置が分からない状況では、if (comp(first[half], value)) は 予測しにくい分岐 になりやすい
  • CPU は分岐予測によって次の命令を先に実行するが、予測が外れると進めた作業を破棄しなければならない
  • 条件付き移動を使えば、比較結果に応じて値を選びつつ条件付きジャンプを減らせる
  • clang -cmov は std::lower_bound の一部の if/else も条件付き移動に変換でき、約 25% 高速化した
  • gcc には同じ状況で条件付き移動を強制する有効なオプションがなく、sb_lower_bound も現状では最適化レベルに関係なくブランチレスコードを出力しない

比較回数という観点での「最適」探索

  • ここでの「最適」とは 比較回数 が最小の二分探索を意味する
  • サイズ n のリストで std::lower_bound の取りうる結果は、要素位置 n 個と末尾位置 1 個を合わせた n+1 個
  • リストサイズが 2^k - 1 なら取りうる結果は 2^k 個で、各比較が真/偽 1 ビットの情報を与えるため、最適な比較回数は k 回になる
  • 長さが 2^k - 1 という「都合のよい」場合には、非常に短いループで最適探索が可能
  • 長さが合わないと、[0, 1, 2, 3, 4, 5] で value が 4 のときのように 範囲外アクセス が発生しうる

sb_lower_bound の性能特性と制約

  • sb_lower_bound は長さが偶数の区間を分けるとき、比較結果が真でも場合によっては十分な数の要素を飛ばさない
  • 2^k <= n < 2^(k+1) の範囲では常に k+1 回比較する
  • 同じ範囲で std::lower_bound は k 回または k+1 回比較し、平均では約 log2(n+1) 回比較する
  • 比較回数は多くなりうるが、ループ内の命令数が大幅に少ないため、全体の実行時間はむしろ速くなる
  • 比較関数が非常に遅い場合は、k+1 回と log2(n+1) 回の差が性能に影響しうる
  • gcc で条件付き移動を強制するには x86 専用のインラインアセンブリで cmov を使う方法があるが、単純な方法では命令数が増え、代替案では型ごとに別のアセンブリを書く必要がある

さらに高速な変種 bb_lower_bound

  • bb_lower_bound は長さが 2^k - 1 の形になるまで別の方法で区間を分け、その後で高速な第 2 ループで探索する
  • length & (length + 1) は長さが 11..1 形、つまり 2^k - 1 かどうかの判定に使われる
  • 不規則な長さでは auto step = length / 8 * 6 + 1 という MAGIC 値を使い、「都合のよい」区間に素早く近づける
  • step は概ね length / 2 以上である必要があり、そうでないと高速ループへ移行しにくいが、length に近すぎると二分探索の利点を失う
  • break のため、bb_lower_bound は分岐を含む形になる
  • すべての長さに対して最速の step を事前計算したテーブルを使う方法は、まだ探索されていない方向として残っている

完全ブランチレス実装はさらに速くはならなかった

  • 64 ビットマシンでは sb_lower_bound のループは最大 64 回反復するため、switch と意図的な fall-through を使って length チェックまで消した「完全ブランチレス」版を作れる
  • この方式は std::bit_width(length) で必要な比較回数に応じたコード位置へジャンプする構造
  • 実際の性能はさらに速くならなかった
  • 最新の x86 CPU はループ条件のような予測しやすい分岐をうまく処理できるため、length チェックをなくす利点がなかった
  • テンプレート、マクロ、64 ケースのコピペ修正を避けられる点でも、通常のループのほうが優れていると判断された

ベンチマーク結果

  • 平均実行時間 (ns) の clang -cmov 基準の結果は次のとおり
    • std::lower_: 61.30
    • branchless_lower_: 43.43
    • asm_lower_: 54.32
    • sb_lower_: 33.24
    • sbm_lower_: 35.54
    • bb_lower_: 32.73
  • 幾何平均実行時間 (ns) でも sb_lower_ が最も低かった
    • std::lower_: 39.17
    • branchless_lower_: 25.14
    • asm_lower_: 31.21
    • sb_lower_: 19.81
    • sbm_lower_: 20.91
    • bb_lower_: 21.33
  • sbm_lower_bound は if の代わりに first += comp(first[length], value) * (length + rem) という形を使い、gcc が条件付き移動を生成するよう促した変種
  • この最適化は次の gcc バージョンで消える可能性があるため、コメントと注意が必要
  • ベンチマークコマンドには g++-10, clang++-10, clang++-10 -mllvm -x86-cmov-converter=false を使い、-march=haswell を付けた
  • -march=native または -march 未指定でも順位には大きな影響がなく、テストは Intel i7 Kaby Lake で行われた

分岐予測ミスの測定

  • perf で測定した通常の clang 実行では約 69.4 億 branches と約 12.0 億 branch-misses が記録され、branch-misses 比率は 17.34% だった
  • clang -cmov 実行では約 40.7 億 branches と約 3,595 万 branch-misses が記録され、branch-misses 比率は 0.88% まで下がった
  • -cmov は約 29 億個の分岐と約 12 億個の分岐予測ミスを除去した
  • 除去された分岐は約 41% の確率で予測ミスしていた分岐だった
  • これは完全に予測不可能な分岐で期待される 50% に近い値

遅い比較関数では結果が変わる

  • 比較関数がさらに遅い状況を見るため、8 バイト文字列探索をテストした
  • 平均実行時間 (ns) では std::lower_bound が sb_lower_bound よりわずかに速いか同等だった
    • gcc: std::lower_ 160.01, sb_lower_ 165.66
    • clang: std::lower_ 157.71, sb_lower_ 162.68, bb_lower_ 157.22
    • clang -cmov: std::lower_ 156.06, sb_lower_ 164.71, bb_lower_ 157.48
  • この場合、std::lower_bound が sb_lower_bound よりごくわずかだが一貫して速い
  • ライブラリはプリミティブ型に直接作用する場合は sb_lower_bound を使い、それ以外では std::lower_bound を使う形で最適性能を狙える

アセンブリで見える違い

  • std::lower_bound の clang -cmov ホットループには cmova, cmovbe などの条件付き移動が含まれるが、長さと位置の更新に複数の命令を使う
  • sb_lower_bound のホットループは半分の長さ、余り、移動先ポインタを計算した後、cmova で first を更新する
  • branchless_lower_bound のアセンブリは非常に短くきれいだが、性能テストでは sb_lower_bound のほうが低オーバーヘッドでより良い結果を出した

アップデート: さらに短くなった sb_lower_bound

  • orlp.net author のコメント以後、sb_lower_bound はホットループのアセンブリ命令数を 9 個から 8 個に減らせるようリファクタリングできることが分かった
  • 核心は length - half が half + length % 2 と等しい点
  • リファクタリング後の形では half = length / 2 を計算し、比較が真なら first += length - half を行った後、length = half に更新する
  • clang -cmov では平均実行時間が約 33ns から約 32ns へわずかに改善した

大きな配列ではプリフェッチが効果的

  • コメントで提案された プリフェッチ は、必要なメモリを事前に L1/L2 キャッシュへ持ち込み、実際のアクセス時の遅延を減らす方法
  • 例としての遅延時間は L1 約 4 サイクル、L2 約 12 サイクル、L3 約 40 サイクル、メモリ約 200 サイクル
  • gcc と clang はどちらも __builtin_prefetch() をサポートする
  • length / 4 の位置をプリフェッチすると 2 回に 1 回は無駄になり、length / 8 まで追加すると 6 回中 5 回が無駄になる
  • プリフェッチ位置の計算や呼び出し自体にもオーバーヘッドがあり、短く作られたホットループではこのコストが重要
  • 複数のプリフェッチ戦略は 256KB 未満の配列では役に立たなかった
  • 256KB 以上ではプリフェッチを加えた sbp_lower_bound が、最大約 400 万エントリ、つまり 16MB までのテストで平均実行時間を約 32ns から約 26ns に改善した
  • その後、約 1 億 2,800 万エントリ、つまり 512MB まで拡張したテストでは、プリフェッチ版が std::lower_bound 比で平均時間ベース約 2.3 倍高速だった
    • 比較基準は std::lower_bound 約 161ns、プリフェッチ版約 71ns

大規模データセットでの観察と代替案

  • 非常に大きなサイズでは、clang -cmov が生成したブランチレス std::lower_bound は分岐あり版より遅かった
  • 最新 CPU は予測された分岐に従いながらメモリロードと投機実行を進められ、これは事実上プリフェッチのように働くことがある
  • sbpm_lower_bound は sbm_lower_bound にプリフェッチを加えた版で、ブール乗算によって gcc がブランチレスコードを生成するよう促す
  • 100 万〜1,000 万要素の間で性能グラフに跳ねがあり、理論的にはさらに高速な実装の余地がある
  • ただしプリフェッチコードは次第に複雑になり、マジック定数も増えるため、gcc/libstdc++ や llvm/libc++ へ貢献できる可能性は複雑さが増すほど低いと考えられる
  • std::lower_bound の制約を破る代替として Eytzinger Binary Search があり、入力配列を二分の中央値ヒープ形式に再配置してキャッシュ効率よく探索する
  • Sergey Slotin at CppCon 2022 の int 16-ary tree テストでは、std::lower_bound より 7 倍〜15 倍高速という結果が出た

コードと利用条件

  • 探索または比較がプログラム中で最も遅い部分で、プロセッサが比較結果を予測しにくいなら、x86 で clang の -mllvm -x86-cmov-converter=false オプションを試せる
  • さらに高速な二分探索が必要なら sb_lower_bound を試せ、gcc では sbm_lower_bound も選択肢になる
  • コードは MIT ライセンスで公開されている
  • コードとベンチマークは github.com/mh-dm/sb_lower_bound/ で確認できる

関連記事

1件のコメント

 
GN⁺ 2023-08-13
Hacker News のコメント

  • 人々が分岐の除去を試みているのを見るたびに、分岐予測ミスが長いパイプラインを止めてしまう構造は CPU アーキテクチャの必須要素ではない、という点を分かっているのか気になる
    パイプラインが長い理由は、実行直前に多くの解析と変換を行うためだが、状態依存性が大きいアルゴリズムでもないので、その大半は事前に済ませられる
    Transmeta Crusoe CPU はこのように動作していたし、分岐を気にしなくてよい世界を想像することもできる
    さらに深く見れば、すべての演算はビットの状態を見て結果を変える分岐だが、ALU 内部のこうした局所的な分岐はメインパイプライン上の分岐ではないため、性能を大きく損なわない

    • Dave ですか？ :-) 以前、スーパースカラ CISC とユニスカラ RISC を、時間あたりのスループットとクロックあたりの命令数の観点で比較した論文があった
      当時 srk にも、IPC とスループットのどちらの指標を選ぶかが、何を良し悪しと見るかに影響すると話した記憶がある
      IPC 側は、より高い IPC を作ればプロセス側でクロックを上げられ、皆が勝つと考える。一方スループット側は、ムーアの法則は死に、シリコンをより速く動かすと溶けるので、ISA を賢く設計する側が勝つという、より現実的なアプローチを取る
      この 20 年で両方に成功と挫折があり、最近 RISC-V が CPU アーキテクチャにおけるこうした問いへ戻ってきているのは興味深い
      命令セットの柔軟性を土台に、現代的なスーパースカラのアイデアがどのように追加されるのかを追うにもよい場所で、長期的にはこちらが勝つ気がする
    • これは完全に間違った考えだ
      Transmeta の変換が分岐コストをなくしてくれたわけではない
      Transmeta で働いていた Linus が comp.arch のスレッドで「CPU の仕事はキャッシュミスをできるだけ早く発生させること」に近いことを言っていたのを覚えている
      強制的なキャッシュミスは存在し、どんな JIT でもそれを取り除くことはできない
      現実世界では、今のように巨大なキャッシュがあっても容量ミスも避けられない
      Itanium も静的解析で分岐コストをなくせると見ていたが、結果がどうだったかを思い出せばいい
      プログラマーたちが、最新プロセッサより良いものを簡単に作れると自信満々に結論づける前に、コンピュータアーキテクチャの本を少し読んでほしい
      現行プロセッサに注ぎ込まれている知的努力の規模を、少なくとも7桁ほど過小評価していると思う
    • 状態がないことはあり得ても、コンパイル時点では分からない要素に大きく依存する
      その一つが処理される入力データだ
      二分探索がまさにその例で、コンパイラは結果がどの位置で見つかるかを知らない
      もう一つはマイクロアーキテクチャ、特にキャッシュ階層と実行ユニット構成だ
      現在の CPU のマイクロ演算に似た命令を持つ ISA に変えると、すべてのマイクロアーキテクチャごとに再コンパイルしなければならない
      ただしこれは、現在の GPU のようにプログラムをバイトコード形式（DXBC、SPIR-V、NVPTX）で配布し、ユーザーモード GPU ドライバが実際のハードウェア命令へ再コンパイルするような OS JIT なら、技術的には解決可能だ
      より大きな変数は、他の CPU スレッドが予測できないコードを実行するという点だ
      ハイパースレッディングをなくしてコアを独立させても、L3 キャッシュ、外部メモリ、I/O 帯域幅、電力と発熱のようにチップ全体で共有されるリソースは依然として残る
    • 核心は分岐という定義にあるのではないかと思う
      すべてを Branch™ と再定義すれば、実際の分岐ではないものまで含めて、一部の Branch™ は事前に計算できる
      しかし普通に言う分岐除去は、if/else のようなコードで実際に計算経路が分かれる場合を扱うものではないか
      そういう世界でも有用な最適化は可能だろうが、複数の未来の結果を同時に計算しようとする Branch™ に限られるだろう
    • パイプラインが長い理由は、プロセッサ内で同時に行える独立した作業が多いからだ、と言い換えることもできる
      独立して実行可能な演算があるたびに、それだけ同時に実行できる可能性が生まれる
      デコード、フェッチ、実行だけの話ではない
      独立した ALU とシフタがあれば、加算している間にシフトもできるし、専用の加算器と乗算器があれば、両方を同時に試せない理由はない
      これはつまり、複数の命令を同時に進行中にしておきたくなるということであり、処理速度より速く命令をフェッチしてデコードできなければならないという意味になる
      また、N 個の Add 命令が独立した Shift を見えなくしてしまわないよう、並べ替えたい状況へ自然につながる
      今の構造が必要以上に複雑だと考えることはできるし、それが間違いではない可能性もある
      それでも現在の構造を作るために膨大なエンジニアリングが投入されているので、こういう方式でなければはるかに速くできると思うなら、その主張がどれほど正確なのか深く掘り下げる必要がある

  • 「これを全部書ける、クリーンで高速なベアメタル言語があれば……」という箇所で、筆者は「BUT RUST..」と「BUT ZIG..」の脚注を入れているが、Nimはどうなのか気になる
    lowerBoundのネイティブライブラリ実装があるように見える: https://github.com/nim-lang/Nim/blob/version-2-0/lib/pure/al...
    厳密に言えば「ベアメタル」言語ではないが、CまたはC++にコンパイルされるので、ここでどんなコードにコンパイルされるのかを見ると面白そう
    それと、Cは何が問題なのかも気になる

  • これが依然としてlower_boundなのか、よく分からない
    コードを読み違えているのかもしれないが、重複があるときに最初の一致項目ではなく、任意の一致項目を返すように見える
    比較関数がオートコンプリートのために特定の文字列プレフィックスを探す場合なら、一意なリストでも複数の項目が一致し得るし、そのときはリスト内で最初の項目が欲しい

    • 一致するたびに残りの長さを半分にし、長さが0のときだけループを抜けるので、最初の項目を返すはず
    • より高速にしたくて、正確にどの一致項目かは気にしないという選択肢があるのは良さそう
    • 私には最初の一致項目を返しているように見える
      なぜそうではないと考えるのか気になる

  • すべてのブログ記事がこの記事のように始まってほしい。「お忙しいでしょうから、すぐ本題に入ります。ここに最速で、汎用的で、単純なC++二分探索実装があります」

  • Zig標準ライブラリは二分探索のためにC++を呼び出してはいない
    現在の二分探索はここにある: https://github.com/ziglang/zig/blob/b835fd90cef1447904d3b009...

  • よく理解できない
    二分探索と分岐の問題は、分岐そのものではなく、比較が終わるまで配列内の次にどのメモリ位置を取ってくるべきか分からないことにある
    分岐を使おうが別の何かを使おうが関係なく、結局はプロセッサに何をしてほしいのかが問題
    データ依存性がある
    中央のインデックスを読むまでは、上側の区間を探索するのか下側の区間を探索するのか分からない
    推測して両方の読み込みを発行することはでき、その場合は依存性は解消されるが、メモリトラフィックは増える
    これが正しいトレードオフかどうかが核心で、単に分岐を取り除くことが答えではない

    • 大きな配列ではプリフェッチが正しいトレードオフ
      記事の末尾で扱っている: https://mhdm.dev/posts/sb_lower_bound/#prefetching
    • その通り
      だから本当により高速な二分探索はEytzinger配列レイアウトを使う: https://algorithmica.org/en/eytzinger
    • 配列が完全にL1キャッシュに収まるなら、分岐予測ミスのコストはメモリ取得よりずっと大きいのでは？

  • 私のCascade Lakeプロセッサでは、-mllvm -x86-cmov-converter=falseが二分探索の性能をほぼ半分に下げる
    数字は100MBのuint32配列に対するbsearchあたりのナノ秒
    clang 15.0.7は、この特定のコード最適化ではgcc 13.2.1よりかなり劣るように見える
    アセンブリはここで見られる: https://godbolt.org/z/cbx5Kdjs6
    gccのアセンブリのほうがずっとすっきりして見える

    Benchmark gcc clang clang -cmov
    slow u32 23.4 46.7 45.8
    fast u32 18.1 19.8 31.4
    • それならhttps://mhdm.dev/posts/sb_lower_bound/#prefetchingを見ればいい
      100MBは十分に大きいので、分岐あり版が少し有利に出るが、より優れているからというより、x86の投機的実行の特性によるもの

  • 「BUT RUST」リンクは本来どこに行くはずだったのか、分かる人はいる？
    バージョン固定されていないので、すでに壊れているようだし、starts_withのドキュメントコメントの途中へ行くつもりだったのかもしれない

    • 記事公開の直前[1]と直後[2]のarchive.orgのキャプチャを見ると、現在は2779行目[3]になっているこのコード行を指すつもりだったようだ
      let mid = left + size / 2;

[1] https://web.archive.org/web/20230602210213/https://doc.rust-...

[2] [https://web.archive.org/web/20230709221353/https://doc.rust-...](<https://web.archive.org/web/20230709221353/…;)

[3] [https://doc.rust-lang.org/src/core/slice/mod.rs.html#2779](<https://doc.rust-lang.org/src/core/slice/mod.rs.html#2779>;)

  • Rust の二分探索実装へリンクしようとしていたもの
    https://doc.rust-lang.org/1.71.1/src/core/slice/mod.rs.html#... に更新されている

  • より複雑な comp 比較関数では結果が維持されない点が興味深い
    記事では、ID、電話番号、アカウント、キーワードのように比較関数が遅い、やや現実的な二分探索シナリオを想定し、そのため 8 バイト文字列検索をテストしたとのこと
    この場合、std::lower_bound が sb_lower_bound よりごくわずかだが一貫して速く、常に最高の性能を得るには、ライブラリがプリミティブ型を直接扱うときは sb_lower_bound を、それ以外では std::lower_bound を使えばよいとのこと
    ここでの分析を見てみたい

    • 分岐予測のおかげで複数の比較を同時にパイプラインに載せられ、予測器が外れたときにロールバックできるため、このようなことが起きているのだと思う
      本当にランダムなデータと入力なら、予測はおおむね半分ほど外れる
      CMOV 方式は比較関数の後ろにあるデータ依存性で詰まる
      平均的には分岐方式は一度に 2 つの比較を実行し、CMOV は 1 つを実行するので、比較時間が分岐予測失敗のペナルティを上回ると逆転点が生じると予想される
    • この場合なら、プリミティブ型向けにははるかに優れた二分探索のバージョンがある可能性が高い
      以前 SIMD でざっくり作ってみたものは、メモリ帯域幅で頭打ちになるまで std::lower_bound より3倍速い: https://github.com/matthewkolbe/ThinkingInSimd/tree/main/alg...
    • 記事では、入力データ集合や検索キーの内容について「予測不可能だ」という表現以外には、どのような保証も見つけられなかった
      純粋にランダムだと仮定しているが、これらの 8 バイト文字列が純粋な情報でないなら、現代の分岐予測器は cmov より簡単に高い性能を出せる可能性がある

  • unpredictable 属性が今では cmov 変換パスに影響するように見える
    6月1日時点なので、おそらく clang 17/18 に入るはず: https://reviews.llvm.org/D118118