- ソート済み配列で値を探す際によく使われる二分探索は、一度に1つの値しか比較しないが、最新のCPUは1命令で複数の値を同時に比較できるため、この能力を活用すれば探索速度を大きく高められる
- SIMD Quadは配列を16個ずつのブロックに分け、ブロック位置は4分木的な補間探索で素早く絞り込み、ブロック内部はSIMD命令で16要素をまとめて比較する階層型探索アルゴリズム
- ベンチマークでは、Intelのwarm cache基準で二分探索比2倍以上高速で、Appleのcold cacheでも2倍以上高速、すべての測定条件で
std::binary_searchより優れていた
- 二分探索のように半分に分ける代わりに4分割すると、命令数はやや増えるものの、Intelの大規模配列ではメモリレベル並列性をより活用でき、cold cache性能が改善した
- 教科書的アルゴリズムは、今日のCPUのデータ並列性とメモリ並列性を前提に設計されていないため、ハードウェア特性を踏まえて再設計することで実効性能を向上できる
中核アイデア
- 二分探索は一度に1つの値だけを比較する構造だが、最新の64ビットARMおよびx64プロセッサは、1命令で16ビット整数8個を同時比較できる
- このハードウェア能力を活用すれば、探索単位を個々の要素ではなくブロック単位に変え、比較回数を大幅に減らせる
- 配列を半分に分ける代わりに**4分割（4分探索）**すると、命令数はやや増えても、ボトルネックは命令数ではない可能性が高く、メモリレベル並列性もより活用しやすい
ソート済み配列のメンバーシップ検査の基本方式
- ソート済み配列で値の存在有無を確認する最も単純な方法は、値を1つずつ調べる線形探索で、C++では
std::findで同等の処理ができる
- 大きな配列では二分探索のほうが速く、探索区間の中央の値を基準に上下半分を捨てる処理を繰り返す
- C++の
std::binary_searchは、値の存在有無をブール値で返す
- Roaring Bitmap形式は、サイズ1〜4096の16ビット整数配列を使い、値の存在確認に二分探索を用いる
SIMD Quadアルゴリズムの構造
- 16ビット符号なし整数のソート済み配列を、16要素固定長ブロックに分割
- 各ブロックの最後の要素を補間キーとして使い、対象値がありそうな単一ブロックまで範囲を絞り込んだうえで、そのブロックの16要素をSIMDで同時に調べる
- 動作手順:
- 要素数が16未満なら、全体を単純な線形探索
- 配列を16個連続要素のブロックに分け、全ブロック数は
num_blocks = cardinality / 16
- ブロック末尾要素をキーとして使い、現在の探索範囲の1/4地点を対象値と比較して
baseを調整
- 有効なブロックなら、ARMではNEON、x64ではSSE2で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 cacheではデータアクセスが多いため線形探索がより不利
- Intelプラットフォーム: warm cacheでSIMD Quadは二分探索より2倍以上高速、cold cacheでは利得はやや小さい
- Appleプラットフォーム: cold cacheでSIMD Quadは2倍以上高速、warm cacheでは利得はより限定的
- すべての場合でSIMD Quadは
std::binary_searchより高速だった
- SIMD部分は特殊命令で処理量を減らし、命令数と分岐も少ないため、高速化の理由は明確
4分探索の効果
- SIMD最適化は維持しつつ、4分の補間探索を二分探索に置き換えたSIMD binary版も比較
- Appleプラットフォームでは、4分アプローチの効果は小さかった
- Intelプラットフォームでは、大規模配列のcold cache環境で4分アプローチが有意な最適化になった
- Intelサーバーでは、4分探索のほうがメモリレベル並列性をより活用できた
実装の要点
simd_quad関数は、uint16_t配列、要素数cardinality、探索対象の値posを受け取り、ブール値を返すgapは16固定で、cardinality < gapなら単純なループで探索- ブロック探索ループは
n > 3の間、1/4、2/4、3/4地点のブロック末尾値を読んで比較し、3つの比較結果の合計でbaseを移動
- 選択されたブロックは、ARM NEONの
vceqq_u16またはx64 SSE2の_mm_cmpeq_epi16で16要素を2組に分けて並列比較する
- 残り要素区間は、
v >= posとなる地点でv == posかどうかを返す
結論
- 教科書的な二分探索は十分に良いアルゴリズムだが、実際の性能という観点では意味のある形でさらに高速化できる
- 標準的なアルゴリズムは、今日のコンピュータの高い並列性を前提に設計されていないことが多い
- SIMD Quadは、メモリレベル並列性とデータ並列性の両方を活用しようとするアプローチ
- さらに優れたアルゴリズムもあり得るため、より創造的なアプローチが必要
- ソースコード
- shotgunを使ったソート済み配列間の高速な積集合
1件のコメント
Hacker Newsのコメント
Daniel Lemireが言う低レベルなハードウェア最適化とは別に、二分探索やその実装上の変種が最善なのは、データが整列済み／単調であること以外に何も分からない場合だけだ。
データ分布について事前情報があるなら、その情報を使ってはるかに高速なアルゴリズムを作れる。紙の辞書で人間が純粋な二分探索より速く適当なページの塊へ移動できるのがその例だ。
数学的には、整列リスト検索は閉ループ制御アルゴリズムで単調関数の逆関数を求めることに近く、コスト関数を作って勾配降下法やその加速版を使うこともできる。より一般には、過度に抽象化された定式化の解法を持ち込むより、解こうとしている特定の問題についての情報をより多く使う方が常に効率的であり、ハードウェアをよりうまく使って得られる定数倍の改善よりも、はるかに大きくスケーラブルな高速化をもたらしうる。
固定反復回数は分岐予測器に優しく、コアループも対象ハードウェア向けに乗算を避けつつかなりタイトに最適化されている。もっと賢くしようとする試みはループを悪化させ、利益を生まなかった。構造体配列形式でサイズが 12 あり、たいてい N が小さいので難しくもある。
ブックマークしていなかったので、年に2回くらいまた探している。伝説によれば、今でも探しているらしい。
だからデータベースではB木が標準になっている。データは何であってもよく、新しい行を大量に取り込めば特性はいつでも大きく変わりうる。
勾配降下法のようなやり方で問い合わせを高速化するアルゴリズムは作れるが、B木はすでに非常に高速で、最悪性能や I/O 要求量の予測可能性、範囲スキャン、ソート順巡回、接頭条件のサポートといった利点も多い。
特定のデータ分布に対してより効率的な問い合わせアルゴリズムは作れるが、重要な性質を失うことが多い。別のアルゴリズムがより近い初期推定を出せても、最後の項目を見つけるのが遅いかもしれないし、平均は速くても最悪性能が悪すぎて使えないこともある。
紙の辞書でも最初の推定の後はほぼ二分探索を使っており、その初期推定で減らせる段階は数回しかない。適当なページの塊に到達した後は、必要以上に線形にざっと見る方を使っていて、厳密な二分探索の方が速いかもしれないが、ページをめくる時間とのバランスも必要だ。
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
「4分探索」は結局、二分探索ループを1段階展開しただけではないのか。項目がある区間を見つけるための比較回数はだいたい同じで、1回に2個ではなく4個ずつ処理しているように見える。ループ展開でも同じ効果が出そうだ。
実質的にプロセッサの観点では、どのループもすでにある程度展開されており、ループ自体の小さなオーバーヘッドだけが残る。二分探索で主なコストになるのは、メモリやキャッシュからデータを持ってくることなので、本当の勝負は後で必要になるデータをできるだけ早く要求して、到着待ちを減らすことだ。
4分探索のようなアルゴリズムの違いは、各分岐の片側だけを深く先読みする代わりに、ありうるすべてのケースを浅くプリフェッチする点にある。結局必要になるプリフェッチは必ず発行され、実際の実行経路で使わないデータに帯域を少し無駄遣いする程度で済む。
探索アルゴリズムの実際の性能を予測するうえで、「比較回数」はほとんど役に立たない指標だ。ボトルネックはどれだけ多く比較できるかではなく、メモリとキャッシュ帯域をどれだけ使い切れるかにある。現代プロセッサの分岐動作を内部まで考えれば、ループ展開と見なすこともできる。
いずれにせよ両方の探索とも定数が異なる O(log N) だ。アルゴリズムの授業では定数はあまり重要ではないが、現実ではかなり効くことがある。
最近、指数探索[2]についても記事[1]を書いた。探したい要素群自体が整列済みの状態で、配列に対して繰り返し二分探索する必要があるときに使えるアルゴリズムで、私たちのワークロードでは8倍の高速化が出た。
[1] https://lalitm.com/post/exponential-search/
[2] https://en.wikipedia.org/wiki/Exponential_search
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 の間を二分探索すれば、最新ユーザーと副次的にユーザー数を見つけられる。競合 SaaS 企業を調べるときに知っておくと便利な情報だ。
CPU は常にキャッシュライン全体、通常は64バイトを一度にアクセスするのだから、キャッシュライン全体を探索する方がよさそうだ。データが CPU 内に載った後は、実質的に無料に近い。
だから「二分」探索で中央のキャッシュラインのすべての値を調べ、一致する値がなければ左／右へ進む方式を試してみたい。キャッシュライン探索は 512 ビット SIMD 命令1つでできる。64バイトのキャッシュラインは 16 ビット整数 32 個なので、単純な二分探索よりほぼ32倍速いかもしれないし、少なくともメモリアクセスは32倍減って、現実的なプログラムの大半ではそこが支配的だろう。
4バイトキーと4バイト子ポインタ、あるいは配列インデックスを使えば、内部ノードはキー7個、子ポインタ8個、次ポインタ1個で64バイトのキャッシュラインをちょうど埋められる。100万項目なら木の深さは約20から約7に減り、上位数段はキャッシュに残っている可能性が高い。
少し工夫すれば SIMD で B木ノード内探索を高速化できるが、データ依存性が非常に強い。
より小さな配列なら、末尾に番兵値を置いた線形探索はすでに打ち負かしにくい。ただ、この主張が曖昧なのは、「小さい」があまりにぼんやりした条件で実感しづらいことにある。
全体としてこの記事は気に入った。以前から気になっていた点を、有用な除去実験まで添えて完璧に掘り下げている。
小さな配列、16〜32 項目で探索実験を少しやってみたが、二分探索は分岐が多くて最悪の方法の一つだった。小さな配列で最も速かったのは分岐なし線形探索だった。
ループを途中で止めず、すべての要素をなめる方式だ。たとえば配列にある数が含まれているか知りたければ、全項目の検査結果を論理 OR でまとめる。SIMD は使わなかったが、小さな配列では分岐が非常に高コストなので、分岐なしですべての要素をただ調べる方が速い。
アルゴリズムの説明が少し分かりにくかった。
SIMD 部分は最後の段階、つまり最後の16要素を探索するときにだけ使われる。
4分探索の部分は3つの地点を調べて4つの経路を作るものだが、単に正しいキーではなく正しいブロックを見つけている。
細部が興味深くて、著者は各ブロックの最後の要素を4分探索に使っている。最初の要素や任意の要素を使うとアルゴリズムがどう変わるのか気になる。
ここでの核心的な直感であるSIMD の多重比較は、最後の段階より大きなスケールにも使えそうだ。
概要はこうだ: a) gather で等間隔の16か所から複数要素を取ってくる b) SIMD 命令で並列比較 c) 正しいブロックに絞る d) ブロックが小さければ線形探索に切り替え、そうでなければ gather／比較サイクルを繰り返す。
gather 命令は不連続メモリから読み込み、二分探索なら不要なほど多く読むことになる。それでも多方向比較が可能になって、二分探索4段分を折りたためるなら、大きなテーブルでは勝てるかもしれない。
すべてのデータ型で完全な16方向比較ができるわけでもない。float64 の探索は AVX-512 でも8方向比較に制限されるが、int32 と float32 は16方向比較が可能だ。
gather ベースの方式より二分探索の方が実際には速い可能性が高いと思う。
古典的な計算機科学のアルゴリズムは、実質的に並列性のない CPU を対象に「設計」されたようなものだ。複数コアも Hyper-threading も SIMD 命令もなく、すべてのメモリアクセス時間が同じで L1/L2/L3 キャッシュ遅延のような概念もなく、一般的／ランダムなデータを扱うという前提だ。
この前提のどれか一つでも外れると、性能を上げるための調整余地がたくさん生まれる。
古典アルゴリズムは、特定のデータ形状や特定 CPU の特性／機能をより深く理解したあとで、より最適化された解法を開発するための非常に良い出発点を与えてくれる。
最適化の尖った先端まで行くと、たいていはデータがメモリにどう保存されどうアクセスされるか、そしてそれを改善する変更が後続段階を損なわないかを見ることになる。昔の職場で、誰かがコードのある部分を長時間最適化したのだが、その最適化のせいで後で必要な大量の情報がキャッシュから追い出され、アプリケーション全体はむしろ遅くなったことがあった。
これはおそらく Rob Pike のプログラミング第5法則、言い換えれば The Mythical Man Month で Fred Brooks が述べたことの焼き直しに近い。参照: https://www.cs.unc.edu/~stotts/COMP590-059-f24/robsrules.htm...
10代の頃、週末を丸ごと使って、二分探索が各段階で探索空間を半分にするから良いのなら、三分探索は3分の1ずつ減らすのでもっと良いのではないかと考えていた。
中央値1つだけを比較する代わりに、1/3 地点の値を比較し、低すぎれば 2/3 地点の値を比較する方式だ。
しかし各段階で二分探索の 1/2 ではなく 1/3 に縮める一方で、比較は平均 3/2 倍すると考えたので、結局同じだと思っていた。
修正: zamadatix の返信を見ると、実際には 2/3 の場合に比較を2回するので平均 5/3 倍だった。
最初の 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 だ。
したがって、総平均比較回数では三分探索がごくわずかに悪いことを示せる: 5/3*Log_3[n] = 1.052... * Log_2[n]
つまり段階数は減るが、最後まで進むには平均してより多く比較することになる。これはこの種のあらゆる探索、つまり分割数が 2 より大きい場合に概ね成り立つ。もちろん、探す値が一様分布し、演算コストが理想化されているなどの前提があり、まさにそこに本文の議論が入ってくる。
二分探索アルゴリズムの三分版としてではない。というのも、それは本当の三分探索ではなく、偏った二分探索に近いからだ。比較は本質的に二値なので、比較を含む探索アルゴリズムはすべて一種の二分探索であり、中央要素以外を選ぶのはアルゴリズム複雑性の観点では効率が落ちる。ただし現実のハードウェアでは、条件次第でより良いこともありうる。本当の三分探索をやるなら、基本演算として3方向比較が必要だ。
面白くなるのは「基数効率」[1]を考えるときだ。最良の選択は e に最も近い自然数である 3 になる。木探索とも関係があり、三分木が二分木より良いこともある。
[1] https://en.wikipedia.org/wiki/Optimal_radix_choice
だから、そのアイデアは当時の CPU では現実的でなかったとしても、今の CPU ではより可能性が高くなっているかもしれない。