静的探索木：二分探索より40倍高速

ソート済み配列に対する二分探索は古典的だが、現代のハードウェアでは最適とは言い難い。Curious Codingの新しい記事では、標準的な二分探索よりも最大40倍高いスループットを達成する静的探索木（S+木）の構築を解説している。この研究はAlgorithmicaのS-treeの概念を基に、積極的なマイクロ最適化で限界に挑戦している。

問題とベースライン

入力は32ビット符号なし整数のソート済みリスト。目標は多数の独立したクエリに応答し、クエリ以上の最小の要素を返すこと。指標はスループット（1秒あたりのクエリ数）で、ベースラインはRustの標準ライブラリの二分探索である。

主要な最適化

記事では、S+木をいくつかの層で体系的に改善している：

Eytzingerレイアウト：二分探索木のメモリ配置を並べ替え、連続するステップでアクセスされるノードが近接するようにし、キャッシュ動作を改善する。プリフェッチによりメモリレイテンシを隠蔽できる。
バッチ処理：一度に1つのクエリを処理する代わりに、多数のクエリを並行して処理し、オーバーヘッドを償却し、より良いSIMD利用を可能にする。
SIMDベクトル化：AVX2命令を使用して複数のキーを同時に比較し、クエリあたりの分岐とメモリアクセスを削減する。
ノードサイズの調整：キャッシュラインやSIMDレジスタ幅に合わせてノードサイズ（B=15、B=16など）を実験する。
プリフェッチ戦略：数ステップ先のキャッシュラインをプリフェッチし、DRAMレイテンシを隠蔽する。
ポインタ演算：バイトベースのポインタとクエリ値の事前スプラッティングにより、不要な間接参照を排除する。

結果

最終的な実装は、ランダムデータに対して標準的な二分探索の約40倍のスループットを達成する。著者はまた、非一様なクエリ分布に対するプレフィックス分割やマルチスレッドスケーリングについても探求している。

なぜこれが重要なのか

これは単なるおもちゃのベンチマークではない。動機はバイオインフォマティクス、特にDNAインデックス作成のためのサフィックス配列検索にある。ヒトゲノムは30億塩基対あり、それを効率的に検索することは重要である。ここでの手法は、データベースインデックスからゲノム解析パイプラインまで、静的なソート済みデータに対する高スループット検索に直接適用できる。

この記事は具体的で新鮮である。すべての最適化はアセンブリ分析とベンチマーク数値によって裏付けられている。メモリ階層、SIMD、分岐予測について考えるためのマスタークラスである。