バイナリサーチには勝てる

• ソート済み配列のメンバーシップ検査は、教科書的なバイナリサーチよりも高速にでき、SIMD Quadはすべての測定条件でstd::binary_searchより速かった
• SIMD Quadは16ビット符号なし整数のソート済み配列を16要素ブロックに分割し、ブロック境界では4分木ではなく4分探索ベースの補間検索を、ブロック内部ではSIMD並列比較を行う
• 最新の64ビットARMとx64（Intel/AMD）は1命令で16ビット整数8個を比較できるため、一度に値を1つしか調べないバイナリサーチの構造をそのまま踏襲する必要は薄れている
• ベンチマークはサイズ2〜4096のソート済み配列100,000個と、メンバーシップ問い合わせ1,000万回で実施され、coldモードはキャッシュミス、warmモードはキャッシュヒットをシミュレーションする
• IntelではwarmキャッシュでSIMD Quadがバイナリサーチより2倍以上高速で、Appleではcoldキャッシュで2倍以上高速だった。Intelの大きな配列のcoldキャッシュでは、4分探索アプローチがメモリレベル並列性をよりうまく活用した

---

ソート済み配列メンバーシップ検査のボトルネック

• ソート済み配列に値が存在するかを確認する最も単純な方法は、値を1つずつなめる線形探索であり、C++ではstd::findで同じ効果を得られる
• 大きな配列ではバイナリサーチの方が高速で、検索区間の中央の値を基準に上半分または下半分を捨てる処理を、値が見つかるか空区間に到達するまで繰り返す
• C++のstd::binary_searchは、値の存在有無をブール値で返す
• Roaring Bitmap形式はサイズ1〜4096の16ビット整数配列を使い、値の存在確認にバイナリサーチを用いる

SIMD Quadの出発点

• 最新のプロセッサの多くはデータ並列命令であるSIMDを備えており、64ビットARMとx64（Intel/AMD）は1命令で16ビット整数8個を対象値と比較できる
• この特性により、バイナリサーチを8個未満のブロックまで延々と掘り下げる必要がなくなり、16個以上の要素も低コストで比較できる
• バイナリサーチは一度に1つの値を調べるが、近年のプロセッサは一度に複数の値をロードして検査でき、メモリレベル並列性も高い
• 配列を半分に分ける代わりに4分割する4分探索を試せる。命令数はやや増えても、ボトルネックが命令数そのものではない可能性が高い

SIMD Quadアルゴリズムの構造

• SIMD Quadは16ビット符号なし整数のソート済み配列向け検索アルゴリズムで、4分補間検索とSIMDを組み合わせる
• 配列を16要素の固定長ブロックに分割し、最後のブロックは例外になる場合がある
• 各ブロックの最後の要素を補間キーとして使い、対象値が存在する可能性の高い単一ブロックまで範囲を絞り込んだうえで、そのブロックの16要素をSIMDで同時に調べる
• 中核となる流れは、ブロック境界で補間検索により比較回数を減らし、ブロック内部でSIMDによる並列比較を行う階層型の探索である
• 動作手順は次のとおり
  • 要素数が16個未満なら、全体を単純な線形探索で調べる
  • cardinalityサイズの配列を16個連続要素のブロックに分割し、全ブロック数はnum_blocks = cardinality / 16である
  • 位置16-1、32-1などのブロック末尾要素をキーとして使い、現在の検索範囲の1/4地点群を対象posと比較してbaseを調整する
  • 補間結果に応じて適切なブロックインデックスloを選ぶ
  • 有効なブロックなら、ARMではNEON、x64ではSSE2で16要素をロードし、対象値との並列等値比較を行い、一致があればtrueを返す
  • 16要素ブロックに収まらない残りの要素は線形探索する

ベンチマーク方法

• ベンチマークでは、配列サイズ2〜4096それぞれについて、16ビット符号なし整数のソート済み配列100,000個を生成した
• 各サイズごとに、2つのモードでメンバーシップ問い合わせ1,000万回を実行した
  • coldモード: 各問い合わせが異なる配列を検索し、キャッシュミスをシミュレーションする
  • warmモード: 問い合わせを配列ごとにまとめ、同じ配列を100回連続で検索してキャッシュヒットをシミュレーションする
• 測定対象は平均問い合わせ時間で、比較アルゴリズムは線形探索（std::find）、バイナリサーチ（std::binary_search）、SIMD Quadである
• 測定システムはApple M4とApple LLVM、Intel Emerald RapidsプロセッサとGCCだった

測定結果

• 線形探索とバイナリサーチの比較では、配列が大きくなるとバイナリサーチが線形探索を上回る
• coldキャッシュでは、より多くのデータアクセスでキャッシュミスが増えるため、線形探索は相対的に不利になる
• バイナリサーチが全体として線形探索より優勢であることを確認したうえで、SIMD Quadと比較した
• IntelとAppleプラットフォームの結果は明確に異なっていた
  • Intelプラットフォームでは、warmキャッシュでSIMD Quadがバイナリサーチより2倍以上高速
  • Intelプラットフォームのcoldキャッシュでは、利得はより小さい
  • Appleプラットフォームでは逆に、coldキャッシュでSIMD Quadが2倍以上高速で、warmキャッシュでの利得はより限定的だった
• すべてのケースでSIMD Quadはバイナリサーチより高速だった
• SIMD部分は専用命令で処理量を減らし、命令数と分岐も少ないため、速度向上は理解しやすい

4分探索の効果

• SIMD最適化は維持したまま、4分補間検索を標準的なバイナリサーチに置き換えたSIMD binary版も比較した
• Appleプラットフォームでは、4分探索アプローチの効果は小さかった
• Intelプラットフォームでは、大きな配列のcoldキャッシュ状況で4分探索アプローチが有意な最適化だった
• Intelサーバーでは、4分探索がメモリレベル並列性をよりうまく活用していた

実装の要点

• simd_quad関数はuint16_t配列、要素数cardinality、探索対象の値posを受け取り、ブール値を返す
• gapは16に固定されており、cardinality < gapなら単純なループで値を探す
• ブロック探索ループでは、n > 3の間、1/4、2/4、3/4地点のブロック末尾値を読み、posより小さいかを比較し、3つの比較結果の合計でbaseを進める
• その後、n > 1の間は半分基準の比較を行って残り範囲を縮め、最後にloブロックを選択する
• 選択されたブロックは、ARM NEONのvceqq_u16またはx64 SSE2の_mm_cmpeq_epi16で、16要素を2組に分けて比較する
• 残り要素区間では、v >= posになる地点でv == posかどうかを返し、最後までなければfalseを返す

結論と資料

• 教科書的なバイナリサーチは悪くないアルゴリズムだが、実際の性能の面で意味のある形でもっと高速にできる
• 標準アルゴリズムは、現代のコンピュータの高い並列性を前提に設計されていないことが多い
• SIMD Quadは、メモリレベル並列性とデータ並列性の両方を活用しようとするアプローチである
• さらに優れたアルゴリズムが可能かもしれず、より創造的なアプローチが必要だ
• ソースコード
• Faster intersections between sorted arrays with shotgun

[GN⁺]

Hacker Newsのコメント

• Daniel Lemireの低レベルなハードウェア最適化の論点とは別に、binary searchやその実装バリエーションが最善なのは、データがソート済み／単調であること以外に何も分からない場合に限られる
  データ分布についての事前知識があれば、その情報を使ってはるかに高速なアルゴリズムを設計できる。たとえば紙の辞書では、人は純粋で理想的な binary search よりも速く、適切なページの塊へ飛ぶことができる
  数学的には、ソート済みリストの探索は単調関数を閉ループ制御アルゴリズムに逆変換することに近く、適切なコスト関数を作れば gradient descent やその加速版も使えるかもしれない
  より一般には、問題をより効率的に解くには、過度に抽象化された解法を持ち込むより、解きたい特定の問題についての情報をより多く使うのが最善だ。ハードウェアをうまく使って得る定数倍の改善よりも、スケーラブルな桁違いの高速化をもたらしうる
  • binary searchについてかなり考えてきたが、この実装には勝てなかった: https://github.com/protocolbuffers/protobuf/blob/44025909eb7...
    1. 密なリストかどうかを O(1) で確認、2) 上限確認、3) 固定反復回数 binary search を使う
       固定反復回数は branch predictor に優しく、コアループも乗算を避けつつ対象ハードウェア向けにかなりタイトに最適化されている。もっと賢くしようとした試みはすべてループを悪化させ、コストを回収できなかった。サイズ 12 の array-of-structs 形式で、N もたいてい小さいのでさらに難しい
  • 「解きたい特定の問題についての情報をより多く使うのがよい」というのは、当たり前でありながら深い。すでに持っている情報が多いほど、すでに持っている情報がさらに多いということでもある
  • treap についての記事を読んだ記憶があるが、木の平衡を取る代わりに重みで探索深さを Huffman encode し、アクセス頻度がばらばらなときに平均アクセス時間を減らす方式だった
    ブックマークしていなかったので、年に2回くらい探し直すことになる
  • その通りだが、肝心なのはデータについてそれ以上分からないことが多い点だ
    だからデータベースでは B-tree が標準になる。データは何でもあり得るし、新しい row を大量にまとめて取り込めば特性はいつでも大きく変わりうる
    gradient descent のようなアルゴリズムで lookup を高速化するよう設計することはできるが、B-tree はすでに非常に高速で、最悪時性能と I/O 要件が予測可能であり、range scan、ordered traversal、prefix 条件などの利点も多い
    特定のデータ分布に対してより効率的な lookup アルゴリズムを作ることはできても、重要な性質を失いがちだ。別のアルゴリズムがより近い初期推定を出しても、最終項目を見つけるのにはかえって遅いかもしれないし、平均は速くても最悪性能が悲惨で実運用しづらいこともある
    紙の辞書でも最初の推定の後はほぼ binary search を使っていて、それで減るのは数回の移動程度だ。正しい数ページまで来たら必要以上に線形探索をしてしまうが、厳密な binary search をすればもっと速いかもしれない一方で、ページをめくる時間とのバランスも必要だ
  • Fritz Hengleinは高速なソート／グループ化について興味深い仕事をしていた。中核論文は Generic Discrimination Sorting and Partitioning Unshared Data in Linear Time[1] のようだ
    Ed Kmett はそのアイデアを Haskell 向けの discrimination[2] ライブラリとして磨き上げ、関連する技術トーク[3]も非常に興味深かった
    [1]: https://dl.acm.org/doi/epdf/10.1145/1411203.1411220
    [2]: https://hackage.haskell.org/package/discrimination
    [3]: https://www.youtube.com/watch?v=cB8DapKQz-I
• 「quaternary」は、binary search ループを1段階 unrolling したものに近いのではないかと思う。項目があるパーティションを見つけるには、結局おおむね同じ回数の比較が必要で、一度に2個ではなく4個ずつ処理しているだけなので、loop unrolling でも似たようなことになりそうだ
  • それよりもう少し厄介だ。現代のプロセッサは speculative execution を行うので、比較結果を推測し、間違いだと分かるか内部限界に達するまで片方の branch を追い続ける
    外れたら推測作業を破棄し、数サイクルの penalty を払って別の開始点からやり直す
    つまりプロセッサ視点では、あらゆるループはすでにある程度 unroll されているとも言えるし、binary search の主コストはメモリやキャッシュからデータを取ってくることにある。したがって本当の勝負は、後で必要になるデータ要求をできるだけ早く発行して待ち時間を減らすことだ
    quad search やそれ以上の多分岐探索では、各 branch の片側だけを深く prefetch する代わりに、あり得るすべてのケースを浅く prefetch する。なので実際に必要になる prefetch は必ず発行しつつ、実際の実行経路で使わないデータに消費する bandwidth も少し減らせる
    「比較回数」は、実際の性能予測をするための探索アルゴリズム比較指標としてはほとんど役に立たない。ボトルネックは比較演算量ではなく、メモリとキャッシュ bandwidth を最大限活用することにある。現代プロセッサの branch 挙動まで考えるなら、loop unrolling と見なせなくもない
  • 多少の loop unrolling と見ることはできる。性能が良くなる理由は、命令数やメモリ読み取り数を大きく減らすからではなく、演算間の dependency を緩和して純粋な直列実行ではなくすためだ。branch の両側を speculative に実行するのと似たようなものとも言える
  • quaternary search は、現在の反復の比較と同時に、次の反復で起こり得る2つの比較を事実上並行して行う。単純な loop unrolling より少し複雑だ
    いずれにせよ、どちらの探索も O(log N) で違うのは定数だけだ。アルゴリズムの授業では定数はそれほど重要でないが、現実にはかなり重要になりうる
  • ある程度は正しいが、unroll した段階間の data dependency も取り除いている
  • プロセッサは、人が素朴に思っているような仕組みでは動いていないからだ
• 最近、Exponential Search[2] についての記事[1]も書いた。探索対象の要素群そのものがソート済みの配列で、binary search を繰り返さなければならないときに使える別のアルゴリズムだ
  私たちの workload では 8倍の高速化 になった
  [1] https://lalitm.com/post/exponential-search/
  [2] https://en.wikipedia.org/wiki/Exponential_search
  • Exponential search は、連番 ID でリソースをアドレス指定する REST API で、最後の ID が欲しいのに専用 endpoint がない場合に便利だ
    HEAD /users/1 -> 200 OK
    HEAD /users/2 -> 200 OK
    HEAD /users/4 -> 200 OK
    ...
    HEAD /users/2048 -> 200 OK
    HEAD /users/4096 -> 404 Not Found
    そのあと 2048 と 4096 の間を binary search すれば、最新 user と、ついでに user 数も分かる。競合 SaaS 企業を調べるときにかなり有用な情報だ
• CPU は常に cache line 64バイト 全体に一度にアクセスするのだから、cache line 全体を検索してもよい。データが CPU に入ってしまえば、実質的にはほぼ無料に近い
  だから「真ん中の cache line」にある全値を調べ、なければ左／右へ進むような「binary」search をしてみたくなる。cache line の検索は単一の 512bit SIMD 命令でできる
  cache line 1本は 64バイト、つまり 16-bit 整数 32個なので、この種の探索は単純な binary search よりほぼ32倍速いかもしれない。少なくともメモリアクセスは32分の1になり、多くの現実のプログラムではそこが支配的だ
  • sorted vector からなる binary search tree で、上位の cache line 全体を target と比較しても当たる可能性は低い。代わりに line 内の追加データを使って探索を減らす必要があり、そうすると B-Tree/B+tree につながる
    4バイト key と 4バイト child pointer または配列 index を使えば、internal node 1個は key 7個、child pointer 8個、next pointer 1個で 64バイト cache line をちょうど埋められる。100万 entries の tree depth は約20から約7に減り、上位の数 level は cache に残る可能性が高い
    ノード内部探索を速くするために SIMD を B-tree node に適用することもできるが、データ依存性はかなり強い
• 小さな配列なら、末尾に sentinel value を置いた linear search はすでにかなり倒しにくい。ただし「小さい」が曖昧すぎる限定なので、感覚的に伝わりにくいという点で、この主張自体が惜しい
  • この記事の優れた benchmark を見ると、linear search はだいたい 200〜400要素 あたりで遅れ始めるので、単純に正しいとは言えない
    全体としてこの記事は、以前からよく気になっていたことを有用な ablation study で徹底的に掘り下げていて良かった
• 小さな配列、16〜32項目で探索実験を少ししたことがあるが、binary search は branch が多く、最悪に近い方法の1つだった
  小配列で最速だったのは linear branchless search だった。ループを途中で抜けず、全要素をなめる方式だ。たとえば配列にある数が含まれるかだけ知りたいなら、全項目のチェック結果を論理 OR すればよい
  SIMD は使わなかったが、小配列では branch コストが非常に高く、branch なしですべての要素を単純に確認するほうが速い
  • prefetcher が好むパターンだから速いのか気になる
• アルゴリズムの説明が少し分かりにくかった
  SIMD の部分は、最後の16要素を探索する最終段階にしか出てこない
  Quad の部分は3箇所を調べて4経路を作るものだが、単に一致する key を探しているのではなく、一致する block を探している
  細部が少し面白くて、著者は quad search に各 block の最後の要素を使っている。各 block の最初の要素や任意の要素を使うとアルゴリズムがどう変わるのか気になる
• ここでの中核的な直感である、複数要素への SIMD 比較 は、最終段階だけでなくもっと大きなスケールでも使えそうだ
  概要としては、1) gather で等間隔な16地点から複数要素を取り出し、2) SIMD 命令で並列比較し、3) 正しい block に絞り込み、4) block が小さければ linear search に切り替え、そうでなければ gather/compare サイクルを繰り返す、というものになる
  gather 命令は非連続メモリを読み、通常の binary sort より多く読むが、multiway compare を可能にし、binary search の4段分をまとめて潰せるので、大きなテーブルでは有利かもしれない
  ただし、すべてのデータ型で完全な16-way比較ができるわけではない。float64 の探索は AVX-512 でも 8-way に制限されるが、int32 や float32 なら 16-way 比較が可能だ
  • gather は極端に遅い。効率を狙う人は gather を避けるだろう
    gather ベースの方式より binary search のほうが実際には速いと思う
• 古典的な計算機科学のアルゴリズムは、実質的に 並列性のない CPU を対象に「設計」されている。複数 core も Hyper-threading も SIMD 的な命令もなく、全メモリアクセス時間が等しく、L1/L2/L3 cache のようなレイテンシ差もないとみなすモデルだ。データも一般的でランダムだと仮定する
  こうした前提のどれか1つでも外れれば、より良い性能を得るための tweak がたくさん生まれる
  古典アルゴリズムの強みは、特定データの形や特定 CPU の特性／quirk をもっと知ったとき、さらに最適で効率的な解法を開発するための優れた出発点を与えてくれることだ
  最適化の最前線に行くほど、普通はデータがメモリにどう保存されどうアクセスされるか、そして改善のための変更が後段の処理に悪影響を与えないかを見るようになる。昔の職場で、誰かがコードの特定部分を長時間かけて最適化したが、その最適化のせいで後で必要な情報が cache から余計に追い出され、結果としてアプリケーション全体が遅くなったことがあった
  おそらく Rob Pike のプログラミング第5規則、さらに遡れば The Mythical Man Month の Fred Brooks の言葉の言い換えに近い。参考: https://www.cs.unc.edu/~stotts/COMP590-059-f24/robsrules.htm...
• 10代のころ、binary search が各段階で探索空間を半分にするのだから、ternary search は毎回3分割するのでより良いのではと思って、週末を丸ごと費やしたことがある
  真ん中の値だけを比べる代わりに、1/3 の位置の値を比較し、低すぎたら 2/3 の位置の値を比較する、という具合だ
  ただ各段階で、binary search のように探索空間が 1/2 に減るのではなく 1/3 になる代わりに、比較回数は平均で 3/2 倍になると考え、結局同等だという結論になった
  修正: zamadatix の返答どおり、実際には 5/3 倍比較になる。2/3 の場合には比較を2回しなければならないからだ
  • この ternary のやり方は、level あたりの平均比較回数が 3/2 ではない
    最初の 1/3 は比較1回、2番目の 1/3 は2回、3番目の 1/3 も2回なので、平均は (1+2+2)/3 = 5/3 だ。「1回か2回かだから50%ずつ」と感じてしまいがちだが、実際には最初の比較で決まる確率は 1/3、2回比較する確率は 2/3 だ
    だから ternary は全体の平均比較回数ではほんの少し悪い。5/3 * Log_3[n] = 1.052... * Log_2[n] になる
    つまり level 数は減るが、最後まで到達するには平均的により多く比較することになる。探索対象値が一様分布し、演算コストが理想化されている、といったいくつかの一般的仮定のもとでは、2より大きい分割数を持つこの種の探索全般に当てはまる。本文が扱う現実ハードウェアの差は、まさにここで効いてくる
  • その10代の発想にも見るべきものはあった
    ただし binary search アルゴリズムの ternary 版としてではない。それは本当の ternary search ではなく、偏った binary search に近い。比較は本質的に binary なので、比較を含む探索アルゴリズムは一種の binary search であり、中央要素以外を選ぶのはアルゴリズム複雑性の観点では効率が落ちる。もちろん実際のハードウェアでは、条件次第でより良いこともある。真の ternary search をやるには、基本演算として 3-way comparison が必要だ
    面白いのは radix efficiency[1] を考えるときで、最適な選択は e に最も近い自然数である 3 になる。tree search にも関係があり、ternary tree が binary tree より良い場合もある
    [1] https://en.wikipedia.org/wiki/Optimal_radix_choice
  • その先には、たとえば高速に seek できないディスクのような場所では 128-way B-tree を使える。key を128個取ってくるコストは key 1個よりそれほど高くないのに、追加で7回の fetch を減らせる
  • そのあと ternary comparator を搭載した CPU を想像していたのか気になる
  • 10代のころ以降、CPU は実行幅と vector capability の両面で劇的に広くなった。増えた throughput によって、dependency chain を減らすためにより多くの演算を投入する方向へバランスが移った
    当時の CPU では非現実的だったそのアイデアも、今の CPU ではより現実的かもしれない