Static Search Trees：二分探索より40倍高速に
(curiouscoding.nl)- 「S+ツリー」という静的探索木を実装し、ソート済みデータの高速検索を実行
- Algorithmica の記事で提案されたコードを出発点として最適化し、提案された追加アイデアや改善作業をコード化
- アセンブリコードを分析した後、可能なあらゆる命令を最適化して性能を最大化
- 複数のクエリを並列に処理してスループットを向上させるバッチングを導入
- 目標は、S+ツリーによってソート済みデータで高いスループットを維持しながら効率的にクエリを実行すること
1. 紹介と動機
-
問題の定義:
- 入力: ソート済み 32 ビット符号なし整数リスト
vals: Vec<u32> - 出力: できるだけ小さいサイズで、特定のクエリ (q) 以上の値を返すデータ構造
- メトリクス: 1 秒あたりに処理可能な独立クエリ数
- 入力: ソート済み 32 ビット符号なし整数リスト
-
目的:
- バイオインフォマティクスにおける効率的なデータ構造の構築、特に DNA 配列インデックスのための接尾辞配列検索の高速化
- CPU 性能と SIMD 命令を活用した性能最大化を目標とする
-
参考資料:
- 二分探索と配列レイアウトの研究（“Array Layouts for Comparison-Based Searching”）
- S+ツリーと静的 B-木の紹介資料
2. S+ツリーと最適化
2.1 二分探索と Eytzinger レイアウト
- Rust 標準ライブラリの二分探索はキャッシュ効率が低く、データサイズが増えると性能が低下
- Eytzinger レイアウト:
- 二分探索木を配列形式で保存し、キャッシュ活用を最大化
- 性能: L3 キャッシュを超えるデータに対して二分探索より最大 4 倍高速
2.2 S+ツリーの概念
- S-ツリー:
- ノードごとに 15 個のソート済み値を含む 16 分木の形
- B-木より効率的で、Eytzinger レイアウトより圧縮しやすい
- S+ツリー:
- すべてのデータをリーフノードに保存し、上位ノードにも重複して保存
- 単純な検索と効率的な構造を提供
2.3 find 関数の最適化
- 基本的な線形探索:
- データを走査しながら条件に合う値を返す（非効率）
- 自動ベクトル化:
- 分岐のないコードに変換し、SIMD 命令の活用で性能が 2 倍向上
- 手動 SIMD 実装:
- 手動で SIMD 命令を活用して最適化し、5 命令で性能を最大化
3. バッチングとプリフェッチ
3.1 バッチング (Batching)
- 複数のクエリを並列に処理し、メモリ待ち時間を相殺
- バッチサイズを増やすことでスループットを改善し、最大バッチサイズ 16 で飽和
3.2 プリフェッチ (Prefetching)
- 次のノードをあらかじめメモリに取り込み、L3 キャッシュを超えるデータで性能を向上
- バッチングと組み合わせ、処理時間を 45ns/query から 30ns/query に短縮
4. データレイアウトと構造の最適化
4.1 ノードサイズの変更
- ノードごとの値を 15 個に減らして乗算処理を単純化し、キャッシュ効率を向上
- L3 キャッシュ内のデータに対してわずかな性能向上
4.2 メモリレイアウトの変更
- レイアウトを逆順で保存したり、パディングを最小化した構成を試験
- 逆順レイアウトとパディング削減レイアウトのいずれも性能への大きな影響はなし
5. データパーティショニング
5.1 接頭辞ベースのパーティショニング
- データの上位ビットを基準にパートを分割
- 小規模データでは性能が向上するが、メモリオーバーヘッドが発生
5.2 圧縮サブツリー
- 各サブツリーをパックして空間効率を向上
- パートのサイズ追跡が必要で、クエリ速度はやや低下
6. マルチスレッド比較
- 6 スレッド使用時、クエリ時間を 27ns から 7ns に短縮
- RAM 帯域幅の制限がボトルネックになる
7. 結論と今後の研究
- 二分探索と比べて 40 倍以上の性能向上（1150ns/query → 27ns/query）
- 今後の課題:
- データバランスの最適化と RAM アクセスの削減
- 範囲クエリおよびソート済みクエリの処理
- 接尾辞配列検索の統合
2件のコメント
いやあ…さまざまな言語の組み込みライブラリに適用されたら、その波及効果はかなり大きい気がします。
Hacker Newsの意見
Rust がアルゴリズム関連の低レベルなコンテンツでますます多く使われるようになっていると感じる。以前は C(++) や科学的な擬似コードで書かれたコンテンツが主流だった。Rust の利用が増えているのは好ましい
クエリをバッチに分ける方法が検討されていない。キャッシュ外テーブルの参照が主なコストである
int32 値の数はそれほど多くなく、完全なビットセットは 512MB で済む。一般的なデータ構造としては Roaring Bitmaps を勧める
Rust で低レベル効率を高める方法には驚かされる。C++ 実装と比較してみたい
Eytzinger ツリーの利点は、ノードインデックスを中順走査位置に変換する公式があることだ
4GB メモリ上で u32 を検索するのに約 27ns のオーバーヘッドが発生するのは驚きだ
Rust と C++ についての議論は多いが、Common Lisp で SIMD を維持しつつ実装する方法を考えてしまう
低レベル最適化についての記事を読むたびに、著者が時間をかけてナノ秒を節約してくれたことに感謝する
1.7 の図 3 には誤りがあると思う。1.3 の図 1 の y 軸ラベルは「逆転送量」であるべきだと提案する
ときどき書き込みも必要なら、大きな静的検索ツリーと小さな書き込み可能ツリーを併用できる