HN 日本語サマリー

← 一覧へ戻る
プログラミング

静的検索ツリー:バイナリサーチの40倍高速(2024年)

Static search trees: 40x faster than binary search (2024) (curiouscoding.nl)

165 pointsby lalitmaganti13 コメント

要約

この記事では、ソート済みデータに対する高スループット検索のための静的検索ツリー(S+ツリー)の実装と最適化について解説しています。特に、EytzingerレイアウトやSIMD命令、バッチ処理などの最適化手法を駆使し、従来のバイナリサーチと比較して大幅な高速化を実現する方法を探求しています。

全文翻訳

静的探索木:二分探索の40倍高速

この記事は、curiouscoding.nl の著者である Ragnar Groot Koerkamp から提供されたものです。そうでないと、悪いことが起こります。明確化が必要な場合は、誰でも Ragnar に直接連絡してください。また、左に投票し、緑を支持してください!地球を救え!

目次

この記事では、Algorithmica で紹介された静的探索木(S+ツリー)を、ソート済みデータの高スループット検索のために実装します。ここでは、そのコードを起点として、限界まで最適化していきます。大部分は、その投稿の「今後の課題」のアイデアを取り入れて実装します。そして、可能な限り多くの命令を削るためにアセンブリコードを徹底的に調べます。最後に、スループットを最適化するための大きな追加として「バッチ処理」を行います。

すべてのソースコード(ベンチマークおよびプロットコードを含む)は、github:RagnarGrootKoerkamp/static-search-tree にあります。

r/programming, hacker news, twitter, bsky, または youtube で議論してください。

1 はじめに 見出しへのリンク

1.1 問題提起 見出しへのリンク

入力。 (n)個の32ビット符号なし整数 vals: Vec<u32> のソート済みリスト。

出力。 (q)というクエリをサポートするデータ構造で、vals の中で (q)以上の最小の要素を返すか、そのような要素が存在しない場合は u32::MAX を返します。オプションで、この要素のインデックスも返すことができます。

指標。 私たちはスループットを最適化します。つまり、1秒あたりに回答できる(独立した)クエリの数です。典型的なケースは、入力として十分な長さの queries: &[u32] があり、対応する answers: Vec<u32> を返す場合です。1

通常、queries/s の代わりに ns/query(または単に ns)として逆スループットを報告します。これは、クエリあたりに費やされる償却(平均ではない)時間と考えることができます。

ベンチマーク設定。 ここでは、入力とクエリの両方が単純に一様ランダムにサンプリングされた31ビット整数2であると仮定します。

コード。 コードでは、これは次のようにモデル化できます。

1
2
3
4
5
6
7
8
9
trait SearchIndex {
    /// お互いの関数実装でデフォルト実装を持つ2つの関数。
    fn query_one(&self, query: u32) -> u32 {
        Self::query(&[query])[0]
    }
    fn query(&self, queries: &[u32]) -> Vec<u32> {
        queries.iter().map(|&q| Self::query_one(q)).collect()
    }
}

コードスニペット 1: 私たちのソリューションが実装すべきトレイト。

1.2 動機 見出しへのリンク

このプロジェクトを単に楽しむためだけでなく、より高い目標があります。バイオインフォマティクスの大きな目標の一つは、DNA(例えば、単一のヒトゲノム(30億塩基対/文字)やそれらの集まり)をインデックス化するための効率的なデータ構造を作成することです。そのようなデータ構造の一つがサフィックス配列(Wikipedia)であり、入力文字列のサフィックスをソートします。古典的には、サフィックス配列を二分探索することで、文字列が出現する場所を見つけることができます。

このプロジェクトは、サフィックス配列検索の高速化に向けた第一歩です。

また、入力データが静的であると仮定していることにも注意してください。通常、固定された参照ゲノムを使用するためです。

1.3 推奨される読書 見出しへのリンク

この問題に対する古典的な解決策は二分探索であり、次のセクションで簡単に触れます。この探索レイアウトやその他の探索レイアウトに関する優れた論文は、Khuong と Morin による「Array Layouts for Comparison-Based Searching」(2017年)です。Algorithmica にも、その論文に基づいたケーススタディがあります。

この記事では、Algorithmica のフォローアップ投稿、static B-trees で紹介されたS+ツリーに焦点を当てます。私の時間を節約するため、ほとんどの場合、あなたがその投稿に精通していることを前提とします。

また、CPU を限界までプッシュするベンチマークを含む、私の作業中のCPUパフォーマンス入門を読むことをお勧めします。そこで得られたメトリクスを、最適化の試みを理解するためのベースラインとして使用します。

SIMD命令を調べる際には、Intel Intrinsics Guide も役立ちます。ここでは AVX2 命令のみを使用することを前提としており、Intel を想定しています。また、私のラップトップには AVX512 命令がないため、それらが利用可能でないことも想定していません。

1.4 二分探索とEytzingerレイアウト 見出しへのリンク

ベースラインとして、Rust 標準ライブラリの二分探索実装を使用します。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
pub struct SortedVec {
    vals: Vec<u32>,
}

impl SortedVec {
    pub fn binary_search_std(&self, q: u32) -> u32 {
        let idx = self.vals.binary_search(&q).unwrap_or_else(|i| i);
        self.vals[idx]
    }
}

コードスニペット 2: Rust 標準ライブラリでの二分探索。

配列レイアウト論文(Khuong and Morin 2017)の主な結論は、Eytzinger レイアウトが実際には最良のものの1つであるということです。このレイアウトはメモリ内の値を並べ替えます。二分探索は実質的にデータ上の二分探索木となり、ルートは中央のノード、次に (\frac 14 n) と (\frac 34 n) の位置のノード、次に (\frac 18n, \frac 38n, \frac 58n, \frac 78n) と続きます。Eytzinger レイアウトの主な利点は、二分探索の最初のステップで必要なすべての値が近くに配置されているため、効率的にキャッシュできることです。ルートをインデックス (1) に配置し、インデックス (i) のノードの2つの子を (2i) と (2i+1) に配置します。これは、インデックス (2i) または (2i+1) のどちらが必要になるかを知る前に、次のキャッシュラインを効果的にプリフェッチできることを意味します。これはさらに進んで、4回の反復で必要となる値であるインデックス (16i) から (16i+15) を含むキャッシュラインをプリフェッチすることができます。これは、ツリーのトラバーサルに関連するレイテンシをかなり効果的に隠すことができます。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
pub struct Eytzinger {
    /// ツリーのルートはインデックス1にあります。
    vals: Vec<u32>,
}

impl Eytzinger {
    /// L: 先読みするレベル数。
    pub fn search_prefetch<const L: usize>(&self, q: u32) -> u32 {
        let mut idx = 1;
        while (1 << L) * idx < self.vals.len() {
            idx = 2 * idx + (q > self.get(idx)) as usize;
            prefetch_index(&self.vals, (1 << L) * idx);
        }
        // 最後の数回の反復では、もはや先読みは必要ありません。
        while idx < self.vals.len() {
            idx = 2 * idx + (q > self.get(idx)) as usize;
        }
        let zeros = idx.trailing_ones() + 1;
        let idx = idx >> zeros;
        self.get(idx)
    }
}

コードスニペット 3: (L=4)レベルの先読みを伴うEytzingerレイアウトの検索の実装。

これら2つをプロットすると、Eytzingerレイアウトは、配列がL2キャッシュ(私の場合 256kB、中央の赤い線)に収まる場合は二分探索と同等に機能しますが、配列がL3キャッシュ(12MB)よりもはるかに大きくなると、二分探索よりもはるかに優れた性能を発揮し始めます。最終的に、Eytzinger検索は4倍高速になり、一度に4回のキャッシュラインのプリフェッチが可能になることにうまく対応しています。

[画像: Figure 1: 入力サイズの増加に伴う二分探索とEytzingerレイアウトのクエリスループット。1GBの入力では、二分探索は約1150ns/queryを必要としますが、Eytzingerは200ns/queryで6倍高速です。(ここでは2本の青い線についてお詫びします。上の線は二分探索、下の線はEytzingerです。すべてのプロットを機能させるのに十分な時間がかかり、すべての色をカスタマイズするのは面倒なので、デフォルトの色を循環させて使用しました。残念ながら、ここでは2つの同じ色が使用されました。少なくとも、プロット間で色は一貫しています。)]

図1:入力サイズの増加に伴う二分探索とEytzingerレイアウトのクエリスループット。1GBの入力では、二分探索は約1150ns/queryを必要としますが、Eytzingerは200ns/queryで6倍高速です。(ここでは2本の青い線についてお詫びします。上の線は二分探索、下の線はEytzingerです。すべてのプロットを機能させるのに十分な時間がかかり、すべての色をカスタマイズするのは面倒なので、デフォルトの色を循環させて使用しました。残念ながら、ここでは2つの同じ色が使用されました。少なくとも、プロット間で色は一貫しています。)

1.5 Hugepages 見出しへのリンク

すべての実験で、通常の 4kB ページではなく、2MB のhugepages を使用してツリーを割り当てるようにします。これにより、仮想メモリからハードウェアメモリへのアドレス変換を行うTranslation Lookaside Buffer(TLB)への圧力が軽減されます。hugepages を使用すると、その内部ページテーブルがはるかに小さくなるため、より良くキャッシュできます。

透過的hugepages が有効になっている場合、2MB の正確な倍数を割り当てる際に自動的に提供されるため、ツリーの割り当てを常に次の 2MB の倍数に丸めます。しかし、32MB 未満の小さな割り当ては、カーネルに新しいメモリページを要求するのではなく、プログラムのヒープに配置されるため、実際にはhugepages にならないことが判明しました。したがって、実際に行われるすべての割り当ては、次の 32MB の倍数に丸められます。

全体として、hugepages は、データセットが実際に 1MB から 32MB のサイズの間にある場合に、小さな違いを生むことがあります。それより小さいデータ構造は、そもそも hugepages を必要としません。Eytzinger レイアウトで hugepages を有効にすると(上記のプロットのように)、大きいサイズで大幅な高速化が得られます。

1.6 ベンチマークに関する注意 見出しへのリンク

プロットでは、入力データのサイズが対数(下)x軸に示されています。上部には、対応するベクトルの要素数が表示されます。各要素は4バイトを占める u32 であるため、これは4分の1になります。測定値は (2^i)、(1.25 \cdot 2^i)、(1.5\cdot 2^i)、および (1.75\cdot 2^i) の値で取得されます。

y軸は、クエリあたりの測定時間を示します。上記のプロットでは、レイテンシと表示されています。これは for q in queries { index.query(q); } としてベンチマークされているためです。それでも、CPU のパイプライン処理とアウトオブオーダー実行により、複数の反復を並列に実行できます。具体的には、反復 (i) の最後のキャッシュラインを待っている間に、次のクエリの最初の命令を実行を開始できます。真のレイテンシを測定するには、クエリ (i+1) をクエリ (i) の結果に依存させることで、ループキャリード依存性を導入する必要があります。しかし、この記事の主な目的はスループットを最適化することなので、それにはこだわりません。

したがって、すべてのプロットは index.query(all_queries) を実行したときのスループットを示します。

ベンチマークには、私のラップトップの i7-10750H CPU を使用し、周波数を コードスニペット 4 を使用して 2.6GHz に固定しています3。

1
sudo cpupower frequency-set -g powersave -d 2.6GHz -u 2.6GHz

コードスニペット 4: CPU 周波数を 2.6GHz に固定する。

キャッシュのサイズも関連性があります。コアあたり 32KiB のL1キャッシュ、コアあたり 256KiB のL2キャッシュ、および物理6コア間で共有される 12MiB のL3キャッシュです。さらに、ハイパースレッディングは無効になっています。

すべての測定は5回行われます。線は中央値に従い、2番目から4番目の値の範囲(つまり、最小値と最大値を破棄した後)を示します。上記のほとんどのプロットで、範囲がほとんど見えないことに注意してください!したがって、特に二分探索のグラフが非常にノイズが多いように見えても、その「ノイズ」は実際には完全に再現可能です。実際、配列レイアウト論文(Khuong and Morin (2017))で説明されているように、キャッシュアソシアティビティの効果によって引き起こされます(この記事はすでに長すぎます)。

1.7 キャッシュライン 見出しへのリンク

メインメモリとキャッシュは、キャッシュラインのレベルで動作します。これは64バイト(少なくとも私のマシンでは)または16個の u32 値で構成されます。したがって、1バイトしか読み取らない場合でも、そのバイトを含むキャッシュラインがまだL1キャッシュにない場合、全体がRAMまたはL3またはL2からL1にフェッチされます。

通常の二分探索は、通常、各キャッシュラインの1つの値しか使用しません。検索の終わりに、最後の16個の値が1つまたは2つのキャッシュラインしか占めないところまでです。

Eytzinger レイアウトも同様の問題を抱えています。次のキャッシュラインをプリフェッチできるにもかかわらず、各キャッシュラインの1つの値しか使用しません。これは基本的に、これらの検索スキームの両方が利用可能なメモリ帯域幅をかなり非効率的に使用していることを意味します。そして、それらのほとんどが行っているのはメモリからのデータの到着を待つことなので、それは良くありません。また、それはまだ関連性はありませんが、多くのスレッドで並列に実行する場合や、バッチ処理を行う場合、単一コアのRAMスループットとメインメモリ自体のスループットがボトルネックになります。

何らかの方法で、各キャッシュラインの情報をより効率的に使用できれば、はるかに良いでしょう ;)

データを異なる方法で格納することで、それが可能です。レイヤーごとに格納するのではなく、各反復が新しいレイヤーに入るようにするのではなく、一度にツリーの4つのレイヤーを格納できます(コードスニペット 5)。これは15個の値を取り、完全にパディングされたキャッシュラインにうまく収めることができます。次にキャッシュラインをフェッチするとき、それを一度に4回の反復に使用できます。ずっと良いです!その一方で、将来のキャッシュラインを事前にプリフェッチできなくなるため、全体的なレイテンシは同じになります。しかし、全体として4倍少ないキャッシュラインをフェッチするため、スループットに役立つはずです。

残念ながら、コードとプロットはありません。なぜなら、私が本当に焦点を当てたいのは次の部分だからです。

[画像: Figure 2: 上の2行は、Eytzinger検索の4つのレイヤーを1つのキャッシュラインにパックする方法を示しています。最初の行は古典的な二分探索レイアウトに従い、2番目の行はEytzingerレイアウトを再帰的に適用します。3行目は代わりにSツリーノードを示しています。簡潔さと明瞭さのために、連続した値を使用していますが、実際にはこれは任意のソート済み数値のリストになります。]

図2:上の2行は、Eytzinger検索の4つのレイヤーを1つのキャッシュラインにパックする方法を示しています。最初の行は古典的な二分探索レイアウトに従い、2番目の行はEytzingerレイアウトを再帰的に適用します。3行目は代わりにSツリーノードを示しています。簡潔さと明瞭さのために、連続した値を使用していますが、実際にはこれは任意のソート済み数値のリストになります。

1.8 SツリーとBツリー 見出しへのリンク

ちょうど15個の値のノードで終わりました。これは高さ4の探索木を表しており、その中で二分探索を行うことができます。そこから、Sツリーへのステップはわずかです。

Bツリー。 しかし、まずBツリーについて簡単に言及しなければなりません(Wikipedia)。これらはより古典的な動的バリアントで、ノードはポインタでリンクされています。Wikipedia が書いているように、それらは通常、ファイルがディスクから4kBチャンクで読み込まれることが多いため、より大きなブロックサイズ(例えば4kB)で使用されます。したがって、それらはより大きな分岐係数も持ちます。

Sツリー。 しかし、代わりにAlgorithmica によって名付けられたSツリーを使用します。これらは、Bツリーの高い分岐係数と、Eytzinger レイアウトのコンパクトさの中間にある、良いバランスです。15個の値を探索木として解釈する代わりに、それらをソートされた方法で格納し、16分探索木として考慮することができます。15個の値は、サブツリーのデータを16個の部分に分割するだけで、線形スキャンを実行してどの部分に再帰するかを見つけることができます。しかし、15個の値と1つのパディングをキャッシュラインに格納する場合、16個の値にして分岐係数を17にすることもできます。

S+ツリー。 BツリーとSツリーは、各値を1回だけ、リーフノードまたは内部ノードに格納します。これは、結果がどのレイヤーで見つかったかを追跡する必要があるため、やや面倒であることが判明しました。これを単純化するために、すべての値をリーフとして格納し、それらを内部ノードに複製することができます。これはB+ツリーまたはS+ツリーと呼ばれます。しかし、私は怠惰なので、この変更を含めるために単にSツリーを使用します。

[画像: Figure 3: 18個の値に対する「フル」S+ツリー(ここでは単にSツリーと呼びます)の例。ノードサイズは(B=2)、分岐係数は(B+1=3)です。各内部ノードは、右側のサブツリーの最小値を格納します。メモリでは、レイヤーは単純に後ろにパックされます。]

図3:「フル」S+ツリー(ここでは単にSツリーと呼びます)の例。18個の値に対して、ノードサイズは(B=2)、分岐係数は(B+1=3)です。各内部ノードは、右側のサブツリーの最小値を格納します。メモリでは、レイヤーは単純に後ろにパックされます。

フルSツリーは、Eytzinger レイアウトと同様の方法でナビゲートできます。インデックス (i) のノード(注:値ではない4)は、インデックス ((B+1)\cdot i + 1 + {0, \dots, B}) に (B+1) 個の子ノードを持ちます。

ツリーが部分的にしか満たされていない場合、フルレイアウトは多くのスペースを無駄にする可能性があります(図4)。代わりに、各レイヤーのオフセット (o_\ell) を明示的に格納することで、レイヤーをパックできます。

ノード (o_\ell + i) の子ノードは、(o extbackslash_{\ell+1} + (B+1)\cdot i + {0, \dots, B}) にあります。

[画像: Figure 4: フル表現は非効率的になる可能性があります。パックされた表現は空きスペースを削除し、各レイヤーが開始するオフセット(o_ell)を明示的に格納します。]

図4:フル表現は非効率的になる可能性があります。パックされた表現は空きスペースを削除し、各レイヤーが開始するオフセット(o_ell)を明示的に格納します。

最後に、コードを見てみましょう。ツリー内の各ノードは、単純に16個の u32 値のリストとして表されます。ノードが64バイトのキャッシュライン境界に配置されることを明示的に要求します。

1
2
3
4
#[repr(align(64))]
pub struct TreeNode<const N: usize> {
    data: [u32; N],
}

コードスニペット 5: 64バイトのキャッシュラインに配置された検索ツリーノード。今のところ、Nは常に16です。ノード内の値は常にソートされている必要があります。

Sツリー自体は、ノードのリストと各レイヤーが開始するオフセットのリストです。

1
2
3
4
5
6
7
8
9
/// N: ノード内の要素数、常に16。
/// B: 分岐係数 <= N+1。通常は17。
pub struct STree<const B: usize, const N: usize> {
    /// ツリーノードのリスト。
    tree: Vec<TreeNode<N>>,
    /// ルートはインデックス tree[offsets[0]] にあります。
    /// その子ノードは tree[offsets[1]] から始まり、以下同様です。
    offsets: Vec<usize>,
}

コードスニペット 6: Sツリーデータ構造。ノードあたりの値の数 (B)(通常は16だが、時には15)と各ノードのサイズ (N)(常に16)に依存します。

スペースを節約し、興味深い部分(少なくとも私にとって)に焦点を当てるために、Sツリーを構築するためのコードは表示しません。それはインデックスの扱いの連続であり、正しく行うには多くの時間がかかります。また、構築は現在まったく最適化されていません。いずれにせよ、コードはこちらで見つかります。

私たちが調べるのは、Sツリーを検索するためのコードです。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
fn search(&self, q: u32, find: impl Fn(&TreeNode<N>, u32) -> usize) -> u32 {
    let mut k = 0;
    for o in self.offsets[0..self.offsets.len()-1] {
        let jump_to = find(self.node(o + k), q);
        k = k * (B + 1) + jump_to;
    }

    let o = self.offsets.last().unwrap();
    // node(i) は unchecked indexing を使用して tree[i] を返します。
    let mut idx = find(self.node(o + k), q);
    // get(i, j) は unchecked indexing を使用して tree[i].data[j] を返します。
    self.get(o + k + idx / N, idx % N)
}

最初のステップは find 関数を最適化することです。

2 find の最適化 見出しへのリンク

2.1 線形探索 見出しへのリンク

まず、find に何をさせたいかを正確に定義しましょう。入力は16個のソート済み値とクエリ値 (q) を持つノードであり、(q) 以上の最初の要素のインデックスを返す必要があります。

簡単なコードはコードスニペット 8です。

1
2
3
4
5
6
7
8
pub fn find_linear(&self, q: u32) -> usize {
    for i in 0..N {
        if self.data[i] >= q {
            return i;
        }
    }
    N
}

コードスニペット 8: 最初に見つかった要素 (\geq q) の線形スキャンで、見つかり次第中断します。

結果はまだそれほど印象的ではありません。

[画像: Figure 5: Sツリー検索の初期バージョンは、Eytzingerレイアウトよりもかなり遅いです。このプロットおよび以降のプロットでは、「古い」線は暗く表示され、以前の最良線と新しい最良線はわずかに強調表示されます。プロット間で色は一貫しています。]

図5:Sツリー検索の初期バージョンは、Eytzingerレイアウトよりもかなり遅いです。このプロットおよび以降のプロットでは、「古い」線は暗く表示され、以前の最良線と新しい最良線はわずかに強調表示されます。プロット間で色は一貫しています。

2.2 自動ベクトル化 見出しへのリンク

結果として、コードスニペット 8 の早期 return; はパフォーマンスにとって非常に悪いことが判明しました。なぜなら、分岐予測器がうまく機能しないからです。

代わりに、(q) より小さい値の数をカウントし、それを (q) 以上の最初の値のインデックスとして返すことができます。(例:(q) 以上のすべての値のインデックスはインデックス0を与えます。)

1
2
3
4
5
6
7
8
9
pub fn find_linear_count(&self, q: u32) -> usize {
    let mut count = 0;
    for i in 0..N {
        if self.data[i] < q {
            count += 1;
        }
    }
    count
}

コードスニペット 9: 早い中断の代わりに (< q) の値をカウントします。if self.data[i] < q は分岐なしのコードに最適化できます。

実際、コードは分岐なしであるだけでなく、SIMD命令に自動ベクトル化されています!

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
vmovdqu      (%rax,%rcx), %ymm1     ; data[..8] をロード
vmovdqu      32(%rax,%rcx), %ymm2   ; data[8..] をロード
vpbroadcastd %xmm0, %ymm0           ; クエリ値を「スプラット」
vpmaxud      %ymm0, %ymm2, %ymm3    ; v
vpcmpeqd     %ymm3, %ymm2, %ymm2    ; v
vpmaxud      %ymm0, %ymm1, %ymm0    ; v
vpcmpeqd     %ymm0, %ymm1, %ymm0    ; 4x クエリと値の比較
vpackssdw    %ymm2, %ymm0, %ymm0    ; 
vpcmpeqd     %ymm1, %ymm1, %ymm1    ; v
vpxor        %ymm1, %ymm0, %ymm0    ; 2x 結果を否定
vextracti128 $1, %ymm0, %xmm1       ; v
vpacksswb    %xmm1, %ymm0, %ymm0    ; v
vpshufd      $216, %xmm0, %xmm0     ; v
vpmovmskb    %xmm0, %ecx            ; 4x マスクを抽出
popcntl      %ecx, %ecx             ; 16ビットマスクのpopcount

コードスニペット 10: コードスニペット 9 は自動ベクトル化されています!

スペースを節約するために、このセクションのさらなる結果は、セクションの最後にある図6で見つけることができます。

この自動ベクトル化されたバージョンは、線形探索よりも2倍以上高速であり、Eytzinger レイアウトを明らかに上回っています!

2.3 末尾のゼロ 見出しへのリンク

独自のSIMDを実装することもできます。元の線形スキャンのアイデアのSIMDバージョンは、16個の比較を並列に実行し、それをビットマスクに変換してから、末尾のゼロの数をカウントします。#[feature(portable_simd)] を使用すると、次のようになります。

1
2
3
4
5
6
7
8
pub fn find_ctz(&self, q: u32) -> usize {
    // Simd<u32, N> は N(=16) 個の u32 値の SIMD ベクトル用の portable-rust 型です。
    let data: Simd<u32, N> = Simd::from_slice(&self.data[0..N]);
    // splat は単一の u32 値を取り、それをすべての N レーンにコピーします。
    let q = Simd::splat(q);
    let mask = q.simd_le(data);
    mask.first_set().unwrap_or(N)
}

コードスニペット 11: 末尾ゼロカウント命令を使用した find の実装。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
vpminud      32(%rsi,%r8), %ymm0, %ymm1  ; data[8..] とクエリの最小値を取る
vpcmpeqd     %ymm1, %ymm0, %ymm1         ; 最小値はクエリと等しいか?
vpminud      (%rsi,%r8), %ymm0, %ymm2    ; data[..8] とクエリの最小値を取る
vpcmpeqd     %ymm2, %ymm0, %ymm2         ; 最小値はクエリと等しいか?
vpackssdw    %ymm1, %ymm2, %ymm1         ; 結果をパックする
vpmaxud      %ymm0, %ymm0, %ymm0         ; v
vpackssdw    %ymm1, %ymm0, %ymm0         ; 2x クエリと値の比較
vpackssdw    %ymm2, %ymm0, %ymm0         ; v
vpshufd      $216, %ymm0, %ymm0          ; v
vpmovmskb    %ymm0, %r8d                 ; 8ビット値の各高位ビットを抽出。
orl          $65536,%r8d                 ; ビット16を設定し、unwrap_or(N)をカバーする
tzcntl       %r8d,%r15d                  ; 末尾ゼロをカウント

コードスニペット 12: コードスニペット 11 のアセンブリコード。popcntl で終わる代わりに、tzcntl で終わります。

次に、生成されたコードをもう少し詳しく見てみましょう。

まず、simd_le が min と cmpeq に変換されるのはなぜでしょうか?

Intel Intrinsics Guide を確認すると、符号付き比較しかなく、 unsigned データがないことがわかります。今のところ、すべての値が31ビットに収まり、i32::MAX 以下であると仮定します。その場合、入力を Simd<i32, 8> に変換しても意味は変わりません。

仮定

入力値とクエリ値は両方とも 0 から i32::MAX の間です。

最終的には、i32 入力を直接取るか、u32 値を i32 の範囲に収まるようにシフトすることで、これを修正できます。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
pub fn find_ctz_signed(&self, q: u32) -> usize
where
    LaneCount<N>: SupportedLaneCount,
{
-    let data: Simd<u32, N> = Simd::from_slice(                   &self.data[0..N]   );
+    let data: Simd<i32, N> = Simd::from_slice(unsafe { transmute(&self.data[0..N]) });
-    let q = Simd::splat(q       );
+    let q = Simd::splat(q as i32);
     let mask = q.simd_le(data);
     mask.first_set().unwrap_or(N)
}

コードスニペット 13: u32 値の代わりに i32 値を使用する以外は、前と同じです。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
-vpminud      32(%rsi,%r8), %ymm0, %ymm1
-vpcmpeqd     %ymm1, %ymm0, %ymm1
+vpcmpgtd     32(%rsi,%rdi), %ymm1, %ymm2 ; クエリ(%ymm1) > data[8..] か?
-vpminud      (%rsi,%r8), %ymm0, %ymm2
-vpcmpeqd     %ymm2, %ymm0, %ymm2
+vpcmpgtd     (%rsi,%rdi), %ymm1, %ymm1   ; クエリ(%ymm1) > data[..8] か?
 vpackssdw    %ymm2, %ymm1, %ymm1         ; 結果をパック
+vpxor        %ymm0, %ymm1, %ymm1         ; 結果を否定 (ymm0 はすべて1)
 vextracti128 $1, %ymm1, %xmm2            ; u16x16 を抽出
 vpacksswb    %xmm2, %ymm1, %ymm1         ; シャッフル
 vpshufd      $216, %ymm1, %ymm1          ; シャッフル解除
 vpmovmskb    %xmm1, %r8d                 ; 8ビット値の各高位ビットを抽出。
 orl          $65536,%r8d                 ; ビット16を追加してunwrap_or(N)をカバーする
 tzcntl       %edi,%edi                   ; 末尾ゼロをカウント

コードスニペット 14: 2つの vpminud と vpcmpeqd 命令はなくなりましたが、代わりに vpcmpgtd が導入され、vpxor が戻ってきました。:((古いバージョンと新しいバージョンで異なるレジスタが使用されていることは無視してください。)

また、非常に場違いに感じる vpshufd 命令も見られます。16個の u32 比較の結果を単一の16ビット値にパックする際に、データが残念な方法でインターリーブされ、それを修正する必要があることがわかります。ここでは、Algorithmica は「事前にシャッフルする」アプローチを採用しており、シャッフル解除命令のために各ノードの値を事前にシャッフルします。また、popcount を使用することも提案されており、これは次に実行することです。

2.4 Popcount 見出しへのリンク

見たように、末尾ゼロカウントアプローチの欠点は、レーンの順序を維持する必要があることです。代わりに、ここでは、以前の自動ベクトル化SIMDと同様に、クエリより小さいレーンの数を数えるだけで、レーンの順序は関係なくなります。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
pub fn find_popcnt_portable(&self, q: u32) -> usize
where
    LaneCount<N>: SupportedLaneCount,
{
    let data: Simd<i32, N> = Simd::from_slice(unsafe { transmute(&self.data[0..N]) });
    let q = Simd::splat(q as i32);
-    let mask = q.simd_le(data);
+    let mask = q.simd_gt(data);
-    mask.first_set().unwrap_or(N)
+    mask.to_bitmask().count_ones() as usize
}

コードスニペット 15: 末尾ゼロの代わりにpopcountを使用します。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
vpcmpgtd     32(%rsi,%rdi), %ymm0, %ymm1
vpcmpgtd     (%rsi,%rdi), %ymm0, %ymm0
vpackssdw    %ymm1, %ymm0, %ymm0     ; 1
-vpxor        %ymm0, %ymm1, %ymm1
 vextracti128 $1, %ymm0, %xmm1        ; 2
vpacksswb    %xmm1, %ymm0, %ymm0     ; 3
vpshufd      $216, %ymm0, %ymm0      ; 4
vpmovmskb    %ymm0, %edi             ; 5
-orl          $65536,%edi
+popcntl      %edi, %edi

コードスニペット 16: xor と or 命令はなくなりましたが、比較結果から整数ビットマスクへの5命令のシーケンスにまだ stuck しています。

理想的には、最初のパック命令 vpackssdw の u16x16 出力から直接 movmsk を使用して、16個の16ビット値の各高位ビットを取得したいところです。残念ながら、AVX2 では u8、u32、u64 用の movemask 命令はありますが、u16 用はありません。

また、vpshufd 命令は証明済みで無用なので、コンパイラがそれを削除しなかったのは少し残念です。代わりにSIMDを手動で記述する時が来ました。

2.5 手動SIMD 見出しへのリンク

結果として、ほとんどのパッキングなしで済ませることができます!vpmovmskb (_mm256_movemask_epi8) を8ビットデータで使用する代わりに、vpackssdw の16ビット出力から直接使用できます!比較は各レーンをすべてゼロまたはすべて1に設定するため、最も重要なおよび中央のビットを安全に読み取り、最後にカウントを2で割ることができます5。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
pub fn find_popcnt(&self, q: u32) -> usize {
    // N が 16 であることを明示的に要求します。
    let low: Simd<u32, 8> = Simd::from_slice(&self.data[0..N / 2]);
    let high: Simd<u32, 8> = Simd::from_slice(&self.data[N / 2..N]);
    let q_simd = Simd::<_, 8>::splat(q as i32);
    unsafe {
        use std::mem::transmute as t;
        // u32 から i32 への変換。
        let mask_low = q_simd.simd_gt(t(low));
        let mask_high = q_simd.simd_gt(t(high));
        // portable_simd から __m256i 組み込み型への変換。
        let merged = _mm256_packs_epi32(t(mask_low), t(mask_high));
        // 32ビットは、レーンあたり2つのカウントを保持するのに十分です。
        let mask: i32 = _mm256_movemask_epi8(t(merged));
        mask.count_ones() as usize / 2
    }
}

コードスニペット 17: SIMDコードの手動バージョン。明示的に組み込み関数を使用します。これは少し醜く、[u32; 8]、Simd<u32, 8>、およびネイティブの __m256i 型の間で多くの変換(キャスト)が行われますが、それに耐える必要があります。

1
2
3
4
5
6
7
8
9
vpcmpgtd     (%rsi,%rdi), %ymm0, %ymm1
vpcmpgtd     32(%rsi,%rdi), %ymm0, %ymm0
vpackssdw    %ymm0, %ymm1, %ymm0
-vextracti128 $1, %ymm0, %xmm1
-vpacksswb    %xmm1, %ymm0, %ymm0
-vpshufd      $216, %ymm0, %ymm0
-vpmovmskb    %ymm0, %edi
+vpmovmskb    %ymm0, %edi
 popcntl      %edi, %edi

コードスニペット 18: 合計5命令のみが残っています。ここでは、明示的な2による除算はありません。これは、関数がインライン化された後の残りの部分のポインタ演算に吸収されるためです。

ここで、これらの作業の結果を見てみましょう。

[画像: Figure 6: 最適化された find 関数を使用したSツリーは、スループットをEytzingerの240ns/queryから自動ベクトル化されたものの140ns/query、最終的な手動最適化バージョンの115ns/queryに向上させ、2倍以上の高速化を実現しています!]

図6:最適化された find 関数を使用したSツリーは、Eytzingerの240ns/queryから自動ベクトル化されたものの140ns/query、最終的な手動最適化バージョンの115ns/queryに向上させ、2倍以上の高速化を実現しています!

このプロットで非常によく見えるように、削除した各単一命令は、スループットの小さくも一貫した改善をもたらします。最大の改善は最後のステップから来ており、実際に3命令を削り取りました。

実際、このプロットをもう少し分析できます。

  • 入力が64バイト((2^6))まで、パフォーマンスは一定です。この場合、「検索ツリー」はルートノードのみで構成されます。
  • 入力が1KB((2^{10}))まで、ツリーは2つのレイヤーを持ち、パフォーマンスは一定です。
  • 同様に、ツリーに新しいレイヤーが追加されるたびに(または実際には、分岐係数 (B+1=17) のべき乗である16ではなく)、レイテンシがジャンプアップするのを見ます。(2^{14})、(2^{18})、(2^{22})、(2^{26}) で、そのたびにツリーの高さが上がります(ただし、アイデアは伝わるでしょう)。
  • ある意味で、x軸を時間のスナップショットとしても(手計算で)解釈できます。グラフがジャンプアップするたびに、ジャンプの高さは、その追加レイヤーの処理に費やされた時間とほぼ同じです。
  • L3キャッシュのサイズを超えると、物事は急速に遅くなります。その時点で、ツリーの各追加レイヤーはかなりの時間を追加します。なぜなら、RAM の待機は本質的に遅いからです。
  • 一方、RAM にヒットすると、減速は段階的ではなく、よりスムーズになります。これは、L3 がまだデータ構造の一部をキャッシュでき、その割合がゆっくりと減少するためです。
  • 再び手計算ですが、x軸を固定された時点でのスペース使用量のスナップショットとしても解釈できます。ツリーの最初の3つのレイヤーはL1に収まります。4番目と5番目のレイヤーはL2とL3に収まります。ツリーが6層深くなると、そのレイヤーの読み取りはほとんどRAMにヒットし、追加のレイヤーは確実にRAMに行くことになります。

これから、この最後のバージョン、find_popcnt を使用します。

3 探索の最適化 見出しへのリンク

3.1 バッチ処理 見出しへのリンク

約束通り、最初の改善はバッチ処理です。一度に1つのクエリを処理する代わりに、複数の(多くの)クエリを一度に処理できます。これにより、CPU は複数のクエリを同時に処理でき、特に、RAM へのリクエストを(最大10〜12個)同時に進行させることができます。そのようにして、1読み取りあたり80nsのレイテンシを待つ代わりに、同時に10回の読み取りを待つことになり、償却待ち時間を約8nsに短縮します。

バッチ処理は、SツリーではなくS+ツリーを使用しているという事実に非常に役立ちます。なぜなら、各要素は最後のレイヤー(同じ深さ)で見つかり、したがってツリーを通過する検索ステップの数は、バッチ内のすべての要素で同じだからです。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
fn batch<const P: usize>(&self, qb: &[u32; P]) -> [u32; P] {
    let mut k = [0; P];
    for [o, _o2] in self.offsets.array_windows() {
        for i in 0..P {
            let jump_to = self.node(o + k[i]).find(qb[i]);
            k[i] = k[i] * (B + 1) + jump_to;
        }
    }

    let o = self.offsets.last().unwrap();
    from_fn(|i| {
        let idx = self.node(o + k[i]).find(qb[i]);
        self.get(o + k[i] + idx / N, idx % N)
    })
}

コードスニペット 19: バッチ処理コードは、1つのクエリを処理するのと非常に似ています。単に (P) 個のアイテムのバッチに対する追加ループを挿入するだけです。

[画像: Figure 7: バッチサイズ1(赤)は、非バッチバージョン(青)と非常に似ており、約115ns/queryです。バッチサイズを2、4、8に増やすたびにパフォーマンスが大幅に向上し、16付近で45ns/query(2.5倍高速)で飽和します。]

図7:バッチサイズ1(赤)は、非バッチバージョン(青)と非常に似ており、約115ns/queryです。バッチサイズを2、4、8に増やすたびにパフォーマンスが大幅に向上し、16付近で45ns/query(2.5倍高速)で飽和します。

興味深い観察結果の1つは、バッチサイズ1から2に移行してもパフォーマンスが倍増しないことです。これは、CPUのアウトオブオーダー実行がすでに十分に深く、事実上(ほぼ)2つのクエリを並列に実行できていたためだと推測します。バッチサイズ4、次に8に移行すると、大幅な高速化が得られます。再び4に移行すると、8に移行したときよりも相対的に少し速度が低下するため、バッチサイズ4でもCPUはすでに次の4のバッチをある程度先読みしている可能性があります🤯。

スループットはバッチサイズ16(実際には12ですでに)で飽和しますが、これはCPUが12個のラインフィルバッファを持ち、最大12個のキャッシュラインを並列に読み取ることができることに対応します。

それでも、主にプロットがよりクリーンになるため、バッチサイズ128に落ち着きます。また、わずかに高速でもあります。これは、バッチを初期化する定数オーバーヘッドが、バッチが大きいほど小さいことが原因である可能性があります。

3.2 プリフェッチ 見出しへのリンク

CPU はアウトオブオーダー実行を使用してすでに複数の読み取りを並列にフェッチしていますが、プリフェッチを使用して明示的に支援することもできます。ノードを処理した後、次に訪問する必要がある子ノード k を決定するため、バッチの残りの部分を続行する前に、そのノードをメモリから読み取るように直接要求できます。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
 fn batch<const P: usize>(&self, qb: &[u32; P]) -> [u32; P] {
     let mut k = [0; P];
     for [o, o2] in self.offsets.array_windows() {
         for i in 0..P {
             let jump_to = self.node(o + k[i]).find(qb[i]);
             k[i] = k[i] * (B + 1) + jump_to;
+            prefetch_index(&self.tree, o2 + k[i]);
         }
     }

     let o = self.offsets.last().unwrap();
     from_fn(|i| {
         let idx = self.node(o + k[i]).find(qb[i]);
         self.get(o + k[i] + idx / N, idx % N)
     })
 }

コードスニペット 20: 次の反復のためのキャッシュライン/ノードを先読みします。

[画像: Figure 8: データがL2キャッシュに収まらなくなった場合にプリフェッチが高速化に役立ち、1GBの入力で45ns/queryから30ns/queryに低下します。]

図8:データがL2キャッシュに収まらなくなった場合にプリフェッチが高速化に役立ち、1GBの入力で45ns/queryから30ns/queryに低下します。

いくつかのことを観察します。まず、プリフェッチはデータがすでに利用可能な場合はわずかに遅くなります。この場合、命令は何も行いません。L2では、グラフをわずかに平坦にし、すでにレイテンシがわずかにボトルネックになっていることを示しています。L3ではこの効果が大きくなり、RAMサイズにヒットするまで、スムーズ/水平なグラフが得られます。そこでは、プリフェッチが最大の利点を提供します。

3.3 ポインタ演算 見出しへのリンク

再び、アセンブリコードを見て、今度は検索関数自体を最適化する時です。結果は以下の図9に示されています。

3.3.1 事前スプラット 見出しへのリンク

まず、find 関数が呼び出しごとにクエリを u32 から Simd<u32, 8> にスプラットすることを指摘できます。これは少し(実際にはそれほど速くはありませんが)より良いことです。すべてのクエリを事前にスプラットし、それらを再利用します。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
pub fn batch_splat<const P: usize>(&self, qb: &[u32; P]) -> [u32; P] {
    let mut k = [0; P];
+    let q_simd = qb.map(|q| Simd::<u32, 8>::splat(q));

     for [o, o2] in offsets.array_windows() {
         for i in 0..P {
-            let jump_to = self.node(o + k[i]).find      (qb[i]    );
+            let jump_to = self.node(o + k[i]).find_splat(q_simd[i]);
             k[i] = k[i] * (B + 1) + jump_to;
             prefetch_index(&self.tree, o2 + k[i]);
         }
     }

     let o = offsets.last().unwrap();
     from_fn(|i| {
-        let idx = self.node(o + k[i]).find      (qb[i]    );
+        let idx = self.node(o + k[i]).find_splat(q_simd[i]);
         self.get(o + k[i] + idx / N, idx % N)
     })
}

コードスニペット 21: ループからスプラットをホイスティングするのは少しきれいです。しかし、速くはありません。

最初のループの各反復のアセンブリコードは次のようになります。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
movq         (%rsp,%r11),%r15
leaq         (%r9,%r15),%r12
shlq         $6, %r12
vmovdqa      1536(%rsp,%r11,4),%ymm0
vpcmpgtd     (%rsi,%r12), %ymm0, %ymm1
vpcmpgtd     32(%rsi,%r12), %ymm0, %ymm0
vpackssdw    %ymm0, %ymm1, %ymm0
vpmovmskb    %ymm0, %r12d
popcntl      %r12d, %r12d
shrl         %r12d
movq         %r15,%r13
shlq         $4, %r13
addq         %r15,%r13
addq         %r12,%r13
movq         %r13,(%rsp,%r11)
shlq         $6, %r13
prefetcht0   (%rcx,%r13)

コードスニペット 22: コードスニペット 21 の各反復のアセンブリコード。(実際にはこれは2つのコピーに展開されますが、それらは同一です。)

3.3.2 バイトベースポインタ 見出しへのリンク

上記のコードを見ると、(64) を掛ける2つの shlq $6 命令が見られます。これは、ツリーノードが64バイトであるため、配列の(i)番目の要素を取得するには、バイト (64\cdot i) で読み取る必要があるからです。要素サイズが小さい場合、インデックスに8を掛けるなどのインライン化された専用の読み取り命令があります。しかし、ストライドが64の場合、コンパイラはシフトの形式で「手動」乗算を生成する必要があります。

さらに、直接ポインタベースのルックアップは、配列インデックスよりもわずかに効率的である可能性があります。self.tree[o + k[i]] を行う場合、self.tree[o] へのポインタを効果的に事前計算できるため、k[i] のみを加算すれば済みます。まずその差分を見てみましょう。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
pub fn batch_ptr<const P: usize>(&self, qb: &[u32; P]) -> [u32; P] {
    let mut k = [0; P];
    let q_simd = qb.map(|q| Simd::<u32, 8>::splat(q));

+    // offsets[l] は self.tree[self.offsets[l]] へのポインタです。
+    let offsets = self.offsets.iter()
+        .map(|o| unsafe { self.tree.as_ptr().add(*o) })
+        .collect_vec();

     for [o, o2] in offsets.array_windows() {
         for i in 0..P {
-            let jump_to = unsafe { *o.     add(k[i]) }.find_splat64(q_simd[i]);
+            let jump_to = unsafe { *o.byte_add(k[i]) }.find_splat64(q_simd[i]);
             k[i] = k[i] * (B + 1) + jump_to;
-            prefetch_ptr(unsafe { o2.     add(k[i]) });
+            prefetch_ptr(unsafe { o2.byte_add(k[i]) });
         }
     }

     let o = offsets.last().unwrap();
     from_fn(|i| {
-        let idx = unsafe { *o.     add(k[i]) }.find_splat64(q_simd[i]);
+        let idx = unsafe { *o.byte_add(k[i]) }.find_splat64(q_simd[i]);
-        unsafe { *(*o.add(k[i] + idx / N)).data.get_unchecked(idx % N) }
+        unsafe { (o.byte_add(k[i]) as *const u32).add(idx).read() }
     })
}

コードスニペット 23: 配列インデックスの代わりにポインタベースのインデックスを使用します。

ここで、k[i] をすべて64で掛けることで、64によるすべての乗算を回避できます。まず、k[i] を64で割ることから始めます。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
pub fn batch_byte_ptr<const P: usize>(&self, qb: &[u32; P]) -> [u32; P] {
    let mut k = [0; P];
    let q_simd = qb.map(|q| Simd::<u32, 8>::splat(q));

    let offsets = self
        .offsets
        .iter()
        .map(|o| unsafe { self.tree.as_ptr().add(*o) })
        .collect_vec();

     for [o, o2] in offsets.array_windows() {
         for i in 0..P {
-            let jump_to = unsafe { *o.byte_add(k[i]) }.find_splat64(q_simd[i]);
+            let jump_to = unsafe { *o.byte_add(k[i]) }.find_splat64(q_simd[i]);
-            k[i] = k[i] * (B + 1) + jump_to * 64;
+            k[i] = k[i] * (B + 1) + jump_to;
             prefetch_ptr(unsafe { o2.byte_add(k[i]) });
         }
     }

     let o = offsets.last().unwrap();
     from_fn(|i| {
-        let idx = unsafe { *o.byte_add(k[i]) }.find_splat(q_simd[i]);
+        let idx = unsafe { *o.byte_add(k[i]) }.find_splat(q_simd[i]);
-        unsafe { (o.byte_add(k[i]) as *const u32).add(idx).read() }
+        unsafe { (o.byte_add(k[i]) as *const u32).add(idx).read() }
     })
}

コードスニペット 24: バイトベースポインタを使用すると、64による乗算を回避できます。

実際、生成されたコードは17命令から15命令に減少し、図9 で大幅な高速化が見られます!

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
movq         32(%rsp,%rdi),%r8
vmovdqa      1568(%rsp,%rdi,4),%ymm0
vpcmpgtd     (%rsi,%r8), %ymm0, %ymm1
vpcmpgtd     32(%rsi,%r8), %ymm0, %ymm0
vpackssdw    %ymm0, %ymm1, %ymm0
vpmovmskb    %ymm0, %r9d
popcntl      %r9d, %r9d
movq         %r8,%r10
shlq         $4, %r10
addq         %r8,%r10
shll         $5, %r9d
andl         $-64,%r9d
addq         %r10,%r9
movq         %r9,32(%rsp,%rdi)
prefetcht0   (%rcx,%r9)

コードスニペット 25: バイトベースポインタを使用すると、64による乗算を回避できます。

3.3.3 最終バージョン 見出しへのリンク

上記のコードの1つの特徴は、andl $-64,%r9d です。6行目ではビットマスクがそこに書き込まれます。次に7行目で、popcountされます。11行目は shll $5、つまり32倍の乗算を行います。これは、二重popcountを補正するための /2 と * 64 の組み合わせです。その後、and $-64 を実行します。ここで、-64 のマスクは 111..11000000 で、6つのゼロで終わります。しかし、私たちはちょうど32を掛けたので、これは単一のビットをゼロにするだけで、popcount が奇数の場合は何も起こりません。しかし、それが決してありえないことは事実なので、この and 命令は実際には必要ありません。

それを避けるために、この /2*64 => *32 最適化を手動で行います。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
pub fn find_splat64(&self, q_simd: Simd<u32, 8>) -> usize {
    let low: Simd<u32, 8> = Simd::from_slice(&self.data[0..N / 2]);
    let high: Simd<u32, 8> = Simd::from_slice(&self.data[N / 2..N]);
    unsafe {
        let q_simd: Simd<i32, 8> = t(q_simd);
        let mask_low = q_simd.simd_gt(t(low));
        let mask_high = q_simd.simd_gt(t(high));
        use std::mem::transmute as t;
        let merged = _mm256_packs_epi32(t(mask_low), t(mask_high));
        let mask = _mm256_movemask_epi8(t(merged));
-        mask.count_ones() as usize / 2
+        mask.count_ones() as usize * 32
    }
}

pub fn batch_byte_ptr<const P: usize>(&self, qb: &[u32; P]) -> [u32; P] {
    let mut k = [0; P];
    let q_simd = qb.map(|q| Simd::<u32, 8>::splat(q));

    let offsets = self
        .offsets
        .iter()
        .map(|o| unsafe { self.tree.as_ptr().add(*o) })
        .collect_vec();

     for [o, o2] in offsets.array_windows() {
         for i in 0..P {
-            let jump_to = unsafe { *o.byte_add(k[i]) }.find_splat64(q_simd[i]);
+            let jump_to = unsafe { *o.byte_add(k[i]) }.find_splat64(q_simd[i]);
-            k[i] = k[i] * (B + 1) + jump_to;
+            k[i] = k[i] * (B + 1) + jump_to;
             prefetch_ptr(unsafe { o2.byte_add(k[i]) });
         }
     }

     let o = offsets.last().unwrap();
     from_fn(|i| {
         let idx = unsafe { *o.byte_add(k[i]) }.find_splat(q_simd[i]);
         unsafe { (o.byte_add(k[i]) as *const u32).add(idx).read() }
     })
}

コードスニペット 26: /2 と *64 を *32 に手動でマージします。

再び、これは小さな高速化をもたらします。

[画像: Figure 9: 検索関数を少しずつ改善した結果。以前と同様に、改善は小さいですが一貫しています。1GBの入力でのスループットは31ns/queryから28ns/queryに向上します。]

図9:検索関数を少しずつ改善した結果。以前と同様に、改善は小さいですが一貫しています。1GBの入力でのスループットは31ns/queryから28ns/queryに向上します。

3.4 スキッププリフェッチ 見出しへのリンク

最初の3つのレイヤーのグラフがL1キャッシュに収まることがわかっているので、おそらくそれらのレイヤーのプリフェッチを単純にスキップできます。

[画像: Figure 10: 最初の方のレイヤーのプリフェッチをスキップすると、わずかに遅くなります。]

図10:最初の方のレイヤーのプリフェッチをスキップすると、わずかに遅くなります。

結果として、プリフェッチをスキップしても役立ちません。おそらく、プリフェッチはデータがすでに利用可能な場合は安価であり、他のものを格納するためにエビクトされたデータが必要な場合、プリフェッチが役立つという小さな可能性があります。

3.5 インターリーブ 見出しへのリンク

もう1つの観察結果は、最初の数レイヤーはCPUバウンドであるのに対し、最後の数レイヤーはメモリ帯域幅バウンドであるということです。2つのドメインをマージすることで、より高い合計スループットを得られるはずです。(区分線形凸関数 (f) の場合、(x) と (y) が異なる区分にある場合、(f((x+y)/2) < (f(x)+f(y))/2) となるのといくぶん似ています。)したがって、例えば、2つのバッチのレイヤー (i) を、もう一方のバッチのレイヤー (i+L/2) ((L) はツリーの高さ)と同時に処理することで、2つのクエリバッチを同時に処理できるかもしれません。これを実装しましたが、残念ながら結果はそれほど速くありません。

あるいは、作業を次のように分割することもできます。一方のバッチの最後のレイヤーを、もう一方のバッチの最後のレイヤーを除くすべてとインターリーブしますか?最後のレイヤーのメモリ読み取りが最も時間を要するためです。これも実際には遅くなります。

わずかな高速化をもたらすのは、現在のバッチの最後のプリフェッチと、次のバッチの最初の2つのレイヤーをインターリーブすることです。それでも結果は、コード(表示されていません;”)が大幅に複雑になる一方で、わずか 2ns の高速化にすぎません。

実際にうまくいくのは、探索のすべてのレイヤーをインターリーブすることです。ツリーが (L) レイヤーを持つ場合、(L) バッチを一度にインターリーブし、次に (i) 番目の進行中のバッチのレイヤー (i) を処理できます。次に、完了したバッチを「シフトアウト」してそれらのクエリの回答を格納し、新しいバッチを「シフトイン」します。このようにして、すべてのレイヤーの異なるワークロードを完全に平均化し、CPU の L3 および RAM へのメモリ帯域幅(少なくとも、それが現在のボトルネックであると仮定します)からほぼ最適なパフォーマンスを達成できるはずです。

インターリーブのためのコードを表示するにはクリックしてください。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
pub fn batch_interleave_full_128(&self, qs: &[u32]) -> Vec<u32> {
    match self.offsets.len() {
        // バッチサイズ128の1バッチ
        1 => self.batch_interleave_full::<128, 1, 128>(qs),
        // 並列でサイズ64の2バッチ、積128
        2 => self.batch_interleave_full::<64, 2, 128>(qs),
        // 並列でサイズ32の3バッチ、積96
        3 => self.batch_interleave_full::<32, 3, 96>(qs),
        4 => self.batch_interleave_full::<32, 4, 128>(qs),
        5 => self.batch_interleave_full::<16, 5, 80>(qs),
        6 => self.batch_interleave_full::<16, 6, 96>(qs),
        7 => self.batch_interleave_full::<16, 7, 112>(qs),
        8 => self.batch_interleave_full::<16, 8, 128>(qs),
        _ => panic!("サポートされていないツリーの高さ {}", self.offsets.len()),
    }
}

pub fn batch_interleave_full<const P: usize, const L: usize, const PL: usize>(
    &self,
    qs: &[u32],
) -> Vec<u32> {
    assert_eq!(self.offsets.len(), L);

    let mut out = Vec::with_capacity(qs.len());
    let mut ans = [0; P];

    // Pサイズのクエリチャンクで反復します。
    // 省略:初期化
    let first_i = L-1;
    for chunk in qs.array_chunks::<P>() {
        let i = first_i;

        // first_i を減算し、Lで割った余りを取ります。
        if first_i == 0 {
            first_i = L;
        }
        first_i -= 1;

        // 各チャンクあたり1要素を処理します。要素first_iから開始します。
        // (省略:最初の最大L要素を処理します。)
        // 出力を書き込み、インデックスjから新しいクエリを読み取ります。
        let mut j = 0;
        loop {
            // 最初のL-1レベル:通常の処理を行います。
            // コンパイラはこのループを展開します。
            for l in 0..L - 1 {
                let jump_to = unsafe { *offsets[l].byte_add(k[i]) }.find_splat64(q_simd[i]);
                k[i] = k[i] * (B + 1) + jump_to;
                prefetch_ptr(unsafe { offsets[l + 1].byte_add(k[i]) });
                i += 1;
            }

            // 最後のレベル:回答を読み取ります。
            ans[j] = {
                let idx = unsafe { *ol.byte_add(k[i]) }.find_splat(q_simd[i]);
                unsafe { (ol.byte_add(k[i]) as *const u32).add(idx).read() }
            };
            // 最後のレベル:インデックスをリセットし、新しいクエリを読み取ります。
            k[i] = 0;
            q_simd[i] = Simd::splat(chunk[j]);

            i += 1;
            j += 1;

            if i > PL - L {
                break;
            }
        }
        // (省略:最後の最大L要素を処理します。)

        out.extend_from_slice(&ans);
    }

    out
}

コードスニペット 27: コードでは、ツリーの高さごとに個別の関数をコンパイルすることで、すべてのレイヤーをインターリーブします。これにより、コンパイラはレイヤーのループを展開できます。最初の反復と最後の反復のコードには多くのオーバーヘッドがありますが、省略されています。

[画像: Figure 11: すべてのレイヤーの探索をインターリーブすると、二分探索のスループットが29ns/queryから24ns/queryに向上します。]

図11:すべてのレイヤーの探索をインターリーブすると、二分探索のスループットが29ns/queryから24ns/queryに向上します。

4 探索レイアウトの最適化 見出しへのリンク

4.1 左ツリー 見出しへのリンク

これまでのところ、ツリーの各内部ノードは、右側のサブツリーの最小値を格納しています(図3、以下に再掲)。

[画像: Figure 12: 通常、B+ツリーでは、各ノードは右サブツリーの最小値を格納します。これを右(S+/B+)ツリーと呼びましょう。]

図12:通常、B+ツリーでは、各ノードは右サブツリーの最小値を格納します。これを右(S+/B+)ツリーと呼びましょう。

これは、2つのサブツリーの間にある値(例えば (5.5))を検索する場合、やや非効率であることが判明しました。その場合、検索はノード ([2, 4]) を持つ最も左の(緑の)サブツリーに下降します。次に、右端の(赤の)ノード ([4,5]) に移動します。そこで、(5.5 > 5) であることを認識し、赤のレイヤーの次の値(単一の配列として格納されている)が必要になります。それは (6) です。問題は、赤のツリーノードがキャッシュラインに正確に対応しているため、(6) がメモリからフェッチする必要がある新しいキャッシュラインに含まれることです。

ここで左最大ツリーを考えてみましょう。

[画像: Figure 13: 左最大S+ツリーでは、各内部ノードは左サブツリーの最大値を格納します。]

図13:左最大S+ツリーでは、各内部ノードは左サブツリーの最大値を格納します。

ここで (5.5) を検索すると、([7,9]) をルートとする中央のサブツリーに下降します。次に左側の ([6,7]) ノードに移動し、(5.5) 以上の最初の値 (6) を読み取ります。これで、検索は直接、実際のアンスワを格納しているノードに向かいます。その前のノードではなく。

[画像: Figure 14: 左Sツリーは、インターリーブバージョンの24ns/queryから22ns/queryに実行時間を短縮します。]

図14:左Sツリーは、インターリーブバージョンの24ns/queryから22ns/queryに実行時間を短縮します。

4.2 メモリレイアウト 見出しへのリンク

いくつかの代替メモリレイアウトを検討しましょう。これまでは、すべてのレイヤーを順方向にパックしていましたが、Algorithmica の投稿では実際には逆順に格納されているため、それも試してみます。クエリコードは、レイヤーの順序がすでにオフセットにエンコードされているため、まったく同じです。

別の潜在的な改善点は、常にフル配列を格納することです。これは非常に非効率的に見えるかもしれませんが、初期化されていないメモリを使用することを確実にすれば、実際にはそれほど悪くありません。その場合、タッチされていないメモリページは決してマッピングされないため、7つのレイヤーがあり、配列全体が1GBを占める場合、レイヤーごとに平均約2MB、7つのレイヤーで14MBを無駄にするだけです。

[画像: Figure 15: これまでパックされたレイアウトを使用してきました。ここでは、Algorithmica が使用する逆レイアウトと、単純な算術インデックス計算を可能にするフルレイアウトも試します。]

図15:これまでパックされたレイアウトを使用してきました。ここでは、Algorithmica が使用する逆レイアウトと、単純な算術インデックス計算を可能にするフルレイアウトも試します。

フル配列を格納する利点は、オフセットを使用する代わりに、Eytzinger検索で行ったように、次のレイヤーのインデックスを直接計算できることです。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
pub fn batch_ptr3_full<const P: usize>(&self, qb: &[u32; P]) -> [u32; P] {
    let mut k = [0; P];
    let q_simd = qb.map(|q| Simd::<u32, 8>::splat(q));

+    let o = self.tree.as_ptr();

-    for [o, o2] in offsets.array_windows()        {
+    for _l      in 0..self.offsets.len() - 1        {
         for i in 0..P {
             let jump_to = unsafe { *o.byte_add(k[i]) }.find_splat64(q_simd[i]);
-            k[i] = k[i] * (B + 1) + jump_to     ;
+            k[i] = k[i] * (B + 1) + jump_to + 64;
             prefetch_ptr(unsafe { o.byte_add(k[i]) });
         }
     }

     from_fn(|i| {
         let idx = unsafe { *o.byte_add(k[i]) }.find_splat(q_simd[i]);
         unsafe { (o.byte_add(k[i]) as *const u32).add(idx).read() }
     })
}

コードスニペット 28: 配列をフルに格納する場合、レイヤーごとのオフセットをドロップし、代わりにインデックスを直接計算できます。

[画像: Figure 16: 逆レイアウトとフルメモリレイアウト、およびインデックスを直接計算する専用の _full 検索を使用したフルメモリレイアウトとの比較。]

図16:逆レイアウトとフルメモリレイアウト、およびインデックスを直接計算する専用の _full 検索を使用したフルメモリレイアウトとの比較。

結果として、これらのレイアウトのどちらもパフォーマンスを向上させないことが判明したため、今後も使用しません。

4.3 ノードサイズ (B=15) 見出しへのリンク

ノードあたり15個の値のみを格納して分岐係数を16にすることも試すことができます。これにより、(B+1)(現在17)による乗算が少し簡単になります。なぜなら、x = (x<<4)+x が x = x<<4 に置き換わるからです。

[画像: Figure 17: ノードあたり15個の値の格納。プロットの下部にある線は、入力サイズに対する各データ構造のオーバーヘッドを示しており、1(サイズが倍になることに対応)で上限が設定されています。]

図17:ノードあたり15個の値の格納。プロットの下部にある線は、入力サイズに対する各データ構造のオーバーヘッドを示しており、1(サイズが倍になることに対応)で上限が設定されています。

ツリーが最大5レイヤーで、データがL3キャッシュに収まる場合、(B=15) を使用すると、ツリーのレイヤー数が同じであれば、確かにわずかに高速になります。一方で、(16) の低い分岐係数は、(17) を使用する場合よりも小さいサイズで追加のレイヤーを必要とします。入力がL3キャッシュよりもはるかに大きい場合、速度はメモリバウンドになるため、速度の向上はなくなります。

4.3.1 データ構造サイズ 見出しへのリンク

通常の二分探索とEytzingerレイアウトは、ほとんどオーバーヘッドがありません。これまでのS+ツリーは、約 (1/16=6.25%) のオーバーヘッドがあります。最後のレイヤーの (1/17) の値が上のレイヤーに複製され、それらの (1/17) が再度複製され、合計で (1/17 + 1/17^2 + \cdots = 1/16) になります。

ノードサイズを15にすると、オーバーヘッドが増加します。各ノードは16個ではなく15個の値しか格納しないため、すでに (1/15) のオーバーヘッドがあります。さらに、分岐係数の低下により、複製オーバーヘッドが (1/16) から (1/15) に増加するため、合計オーバーヘッドは (2/15 = 13.3%) になり、図17 の破線青線と一致します。

4.4 要約 見出しへのリンク

[画像: Figure 18: これまでに行ったすべての改善の要約。]

図18:これまでに行ったすべての改善の要約。

これまでのすべての改善の中で、インターリーブのみが少しやりすぎかもしれません。これはバッチごとに行われない唯一の方法であり、入力全体を実際に必要とします。また、コードは、最初の反復と最後の反復が個別に処理されるため、通常のバッチクエリメソッドの3倍の長さです。

5 プレフィックス分割 見出しへのリンク

これまでは、純粋に比較ベースの探索を行ってきました。今、新しいこと、入力値の分割に移りましょう。

アイデアの最も単純な形式は、上位 (b) ビットで値を分割し、(2^b) 個の部分にすることです。その後、(2^b) 個の独立した検索ツリーを構築し、それぞれでクエリを検索できます。(b=12) の場合、これは検索の最初の2つのレイヤーを節約します(実際には少し少ないですが、(2^{12} = 16^3 < 17^3) のため)。

5.1 フルレイアウト 見出しへのリンク

メモリでは、これらのツリーをフルレイアウトと同様の方法で格納できます。主な違いは、最初の数レイヤーがスキップされ、各部分の最後にパディングがあることです。ただし、一度だけ最後にパディングがあるのではなく。

[画像: Figure 19: フル分割レイアウトは、すべての部分のフルツリーを「水平」に連結します。新しい詳細として、部分がフルでない場合、次の部分の最小値がリーフレイヤーに追加されます。]

図19:フル分割レイアウトは、すべての部分のフルツリーを「水平」に連結します。新しい詳細として、部分がフルでない場合、次の部分の最小値がリーフレイヤーに追加されます。

(b) の選択によっては、各ツリーの (15/16) までがパディングになる場合があります。このオーバーヘッドを削減するために、すべてのツリーが同じスペースに収まる限り (b) を1つ減らすことで、(b) を減らそうとします。これにより、要素が均等に分布している場合、すべての部分が少なくとも (50%) 満たされるようになります。

構築が完了すると、クエリのコードは以前と非常に似ています。クエリのインデックスを、q >> shift のような値で (0) ではなく、その部分のインデックスから開始するだけで済みます。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
pub fn search_prefix<const P: usize>(&self, qb: &[u32; P]) -> [u32; P] {
    let offsets = self
        .offsets
        .iter()
        .map(|o| unsafe { self.tree.as_ptr().add(*o) })
        .collect_vec();

    // 初期部分、およびそれらをプリフェッチします。
    let o0 = offsets[0];
-    let mut k = [0; P];
+    let mut k = qb.map(|q| {
+        (q as usize >> self.shift) * 64
+    });
     let q_simd = qb.map(|q| Simd::<u32, 8>::splat(q));

     for [o, o2] in offsets.array_windows() {
         for i in 0..P {
             let jump_to = unsafe { *o.byte_add(k[i]) }.find_splat64(q_simd[i]);
             k[i] = k[i] * (B + 1) + jump_to;
             prefetch_ptr(unsafe { o2.byte_add(k[i]) });
         }
     }

     let o = offsets.last().unwrap();
     from_fn(|i| {
         let idx = unsafe { *o.byte_add(k[i]) }.find_splat(q_simd[i]);
         unsafe { (o.byte_add(k[i]) as *const u32).add(idx).read() }
     })
}

コードスニペット 29: 分割ツリーのフルレイアウトの検索は、各クエリが属するパーティションから開始します。

[画像: Figure 20: 「単純な」分割ツリー、(b_{textrm{max}}in {4,8,12,16,20}) について、点線で示されています。]

図20:「単純な」分割ツリー、(bachr{textrm{max}}in {4,8,12,16,20}) について、点線で示されています。

実際、(0) から (1) の間で変動するスペースオーバーヘッドを持つ分割ツリーは、まだ実用的ではないことがわかります。より大きな (b) は、残りのツリーの高さを減らし、実際、より大きな (b) の方がクエリが高速であることがわかります。特に小さなツリーでは、インターリーブよりも大幅な高速化があります。驚くべきことに、どのパーティションサイズも、大きな入力に対してインターリーブよりも高速なクエリはありません。また、パーティショニングはL1キャッシュまでのサイズに対して非常に高速ですが、これはオーバーヘッドが (\gg 1) であるためのみ可能であることに注意することも重要です。

5.2 コンパクトなサブツリー 見出しへのリンク

以前のパックレイアウトを使用したのと同様に、ここではパックされたすべてのサブツリーの表現を単純に連結することで、これも行うことができます。すべてのサブツリーが同じ合計サイズにパディングされていることを確認しますが、ここではフルツリーにパディングするのではなく、必要なパディングのみを追加します。次に、各ツリーにメモリ内で同じレイアウトを与えます。

最初のツリーの各レイヤーの開始位置を示すオフセット (o_\ell) を持ち、ツリーの定数サイズを格納します。これにより、各部分の各レイヤーを簡単にインデックス化できます。

[画像: Figure 21: 前の図19と比較して、各サブツリーの最下位レベルは、3ノードではなく2ノードしか使用しなくなりました。]

図21:前の図19と比較して、各サブツリーの最下位レベルは、3ノードではなく2ノードしか使用しなくなりました。

クエリのコードは少し複雑になります。今、各クエリが属する部分を明示的に追跡し、レイヤーオフセット、レイヤー内オフセット k[i]、および部分オフセットに基づいてすべてのインデックスを計算する必要があります。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
pub fn search<const P: usize>(&self, qb: &[u32; P]) -> [u32; P] {
    let offsets = self
        .offsets
        .iter()
        .map(|o| unsafe { self.tree.as_ptr().add(*o) })
        .collect_vec();

    // 初期部分、およびそれらをプリフェッチします。
    let o0 = offsets[0];
+    let mut k: [usize; P] = [0; P];
+    let parts: [usize; P] = qb.map(|q| {
+        // 部分のバイトオフセット。
+        (q as usize >> self.shift) * self.bpp * 64
+    });
     let q_simd = qb.map(|q| Simd::<u32, 8>::splat(q));

     for [o, o2] in offsets.array_windows() {
         for i in 0..P {
-            let jump_to = unsafe { *o.byte_add(           k[i]) }.find_splat64(q_simd[i]);
+            let jump_to = unsafe { *o.byte_add(parts[i] + k[i]) }.find_splat64(q_simd[i]);
             k[i] = k[i] * (B + 1) + jump_to;
-            prefetch_ptr(unsafe { o2.byte_add(           k[i]) });
+            prefetch_ptr(unsafe { o2.byte_add(parts[i] + k[i]) });
         }
     }

     let o = offsets.last().unwrap();
     from_fn(|i| {
-        let idx = unsafe { *o.byte_add(           k[i]) }.find_splat(q_simd[i]);
+        let idx = unsafe { *o.byte_add(parts[i] + k[i]) }.find_splat(q_simd[i]);
-        unsafe { (o.byte_add(           k[i]) as *const u32).add(idx).read() }
+        unsafe { (o.byte_add(parts[i] + k[i]) as *const u32).add(idx).read() }
     })
}

コードスニペット 30: パックされたサブツリーのインデックス作成には、部分を明示的に追跡する必要があります。これにより、少し遅くなります。

[画像: Figure 22: 前の単純/フルレイアウト(b=16 の濃い青い点)と比較して、コンパクトレイアウト(例えば、b=16 の赤い点)は一貫してメモリ使用量が少なく、わずかに遅くなります。]

図22:前の単純/フルレイアウト(b=16 の濃い青い点)と比較して、コンパクトレイアウト(例えば、b=16 の赤い点)は一貫してメモリ使用量が少なく、わずかに遅くなります。

(b_{\textrm{max}}) が固定されている場合、入力が十分に大きく、ツリーに十分なレイヤーがある限り、コンパクトレイアウトのメモリオーバーヘッドは小さいです。したがって、このツリーは実用的になる可能性があります。しかし、残念ながら、クエリは以前よりもわずかに遅くなります。なぜなら、各クエリの部分を明示的に追跡する必要があるからです。

5.3 両者の最良:コンパクトな第一レベル 見出しへのリンク

先ほど見たように、ツリーを1つずつ格納するとクエリが遅くなるため、それを避けたいです。しかし、一方で、フルレイアウトはスペースを無駄にする可能性があります。

ここでは、2つのアイデアを組み合わせます。パックされたツリーの水平連結を格納したいのですが、これはレベルが定数でない分岐係数を持つため、複雑です。代わりに、各ツリーの最後の数個(レベル2)のサブツリーを完全に省略し、存在するサブツリーをフルサブツリーにパディングすることができます。これにより、最初のレベルのみが構成可能な分岐係数 (B_1) を持ち、構築完了後に格納できます。

このレイアウトは、サブツリーがフルである必要があるため、以前よりもスペースがわずかに多くなりますが、オーバーヘッドは通常 (1/16) のオーダーになります。なぜなら(均一なデータの場合)、各ツリーは (\geq 9) 個のサブツリーを持ち、そのうち最後の1つだけがフルではないからです。

[画像: Figure 23: ここでは、サブツリーの数を (B+1) より少なく、(2) に固定できます。 (B+1=3) の代わりに。示されていませんが、深いレイヤーは常にフルで、(B+1) の分岐係数を持つ必要があります。]

図23:ここでは、サブツリーの数を (B+1) より少なく、(2) に固定できます。 (B+1=3) の代わりに。示されていませんが、深いレイヤーは常にフルで、(B+1) の分岐係数を持つ必要があります。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
pub fn search_b1<const P: usize>(&self, qb: &[u32; P]) -> [u32; P] {
    let offsets = self
        .offsets
        .iter()
        .map(|o| unsafe { self.tree.as_ptr().add(*o) })
        .collect_vec();

     let o0 = offsets[0];
     let mut k: [usize; P] = qb.map(|q| {
          (q as usize >> self.shift) * 64
     });
     let q_simd = qb.map(|q| Simd::<u32, 8>::splat(q));

-    for         [o, o2]  in offsets.array_windows()        {
+    if let Some([o1, o2]) = offsets.array_windows().next() {
         for i in 0..P {
-            let jump_to = unsafe { *o.byte_add(k[i]) }.find_splat64(q_simd[i]);
+            let jump_to = unsafe { *o.byte_add(k[i]) }.find_splat64(q_simd[i]);
-            k[i] = k[i] * (B + 1) + jump_to;
+            k[i] = k[i] * self.b1 + jump_to;
             prefetch_ptr(unsafe { o2.byte_add(k[i]) });
         }
     }

-    for [o, o2] in offsets     .array_windows() {
+    for [o, o2] in offsets[1..].array_windows() {
         for i in 0..P {
             let jump_to = unsafe { *o.byte_add(k[i]) }.find_splat64(q_simd[i]);
             k[i] = k[i] * (B + 1) + jump_to;
             prefetch_ptr(unsafe { o2.byte_add(k[i]) });
         }
     }

     let o = offsets.last().unwrap();
     from_fn(|i| {
         let idx = unsafe { *o.byte_add(k[i]) }.find_splat(q_simd[i]);
         unsafe { (o.byte_add(k[i]) as *const u32).add(idx).read() }
     })
}

コードスニペット 31: 今やコードはシンプルになり、部分インデックスを明示的に追跡する必要がなくなりました。唯一変わるのは、forループの最初の反復を別々に処理し、そこで B+1 の代わりに分岐係数 self.b1 を使用することです。

[画像: Figure 24: 第一レベルを圧縮すると、スペース使用量はコンパクトレイアウトと非常に似ており、クエリ速度はフルレイアウトと同じくらい高速です。]

図24:第一レベルを圧縮すると、スペース使用量はコンパクトレイアウトと非常に似ており、クエリ速度はフルレイアウトと同じくらい高速です。

5.4 オーバーラップするツリー 見出しへのリンク

上記の方法すべてに欠点があるのは、メモリ使用量が最大のパートの影響を大きく受けることです。なぜなら、すべてのパートは少なくともそれと同じ大きさでなければならないからです。これは、パートサイズの分布が非常に偏っている場合に特に問題となります。隣接するツリー間でストレージを共有することで、これを回避できます。(p) 番目のパートのサブツリーの数((S_p))と (S_{max} = \max_p S_p) とします。次に、オーバーラップ (0\leq v\leq B) を定義し、各新しいパートごとに、以前のように (S_{max}) ではなく、(B_1 = S_{max}-v) 個の新しいサブツリーのみを追加します。各パートの値は、前のパートが終了した場所に単純に追加されます。ただし、そのサブツリーが現在のパートにとって「到達不可能」な場合は、まずパディングが追加されます。このようにして、連続するパートはオーバーラップし、メモリを交換でき、大きなパートの影響をある程度「バッファリング」できます。

[画像: Figure 25: この例では、3番目のツリーは (8, 12) の範囲に (6) 個の値があり、(S_{max}=3) 個のサブツリーが必要です。オーバーラップは (v=1) で、各追加ツリーには (2) 個のサブツリーのみが追加されます。すべての要素が自身のツリーから到達可能であることを保証するために、パディング要素をグレーで追加します。]

図25:この例では、3番目のツリーは (8, 12) の範囲に (6) 個の値があり、(S_{max}=3) 個のサブツリーが必要です。オーバーラップは (v=1) で、各追加ツリーには (2) 個のサブツリーのみが追加されます。すべての要素が自身のツリーから到達可能であることを保証するために、パディング要素をグレーで追加します。

オーバーラップが (1) の場合(上記の例)、最初のレイヤーのノードはそれぞれ (B) 個のサブツリーの最大値を含みます。オーバーラップが (1) より大きい場合、最初のレイヤーのノードはオーバーラップする値を含みます。代わりに、単一のリストを格納し、必要な (B) 個の値のスライスを取得するためにアラインメントされていない読み取りを行うことができます。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
pub fn search<const P: usize, const PF: bool>(&self, qb: &[u32; P]) -> [u32; P] {
    let offsets = self
        .offsets
        .iter()
        .map(|o| unsafe { self.tree.as_ptr().add(*o) })
        .collect_vec();

     let o0 = offsets[0];
-    let mut k: [usize; P] = qb.map(|q| {
-        (q as usize >> self.shift) * 4 *  16
+    let mut k: [usize; P] = qb.map(|q| {
+        (q as usize >> self.shift) * 4 * (16 - self.overlap)
     });
     let q_simd = qb.map(|q| Simd::<u32, 8>::splat(q));

     if let Some([o1, o2]) = offsets.array_windows().next() {
         for i in 0..P {
-            let jump_to = unsafe {  o.byte_add(k[i]).read_unaligned() }.find_splat64(q_simd[i]);
+            let jump_to = unsafe {  o.byte_add(k[i]).read_unaligned() }.find_splat64(q_simd[i]);
             k[i] = k[i] * self.l1 + jump_to;
             prefetch_ptr(unsafe { o2.byte_add(k[i]) });
         }
     }

     for [o, o2] in offsets[1..].array_windows() {
         for i in 0..P {
             let jump_to = unsafe { *o.byte_add(k[i]) }.find_splat64(q_simd[i]);
             k[i] = k[i] * (B + 1) + jump_to;
             prefetch_ptr(unsafe { o2.byte_add(k[i]) });
         }
     }

     let o = offsets.last().unwrap();
     from_fn(|i| {
-        let idx = unsafe {  o.byte_add(k[i]).read_unaligned() }.find_splat(q_simd[i]);
+        let idx = unsafe {  o.byte_add(k[i]).read_unaligned() }.find_splat(q_simd[i]);
         unsafe { (o.byte_add(k[i]) as *const u32).add(idx).read() }
     })
}

コードスニペット 32: 各パートには (16-v) 個の値が含まれ、元の16個ではなくなります。16値境界に常に読み取るわけではないため、read_unaligned を使用します。

[画像: Figure 26: オーバーラップするツリーは通常、第一レベル圧縮バージョンよりもメモリ使用量が少なく、速度も同等です。]

図26:オーバーラップするツリーは通常、第一レベル圧縮バージョンよりもメモリ使用量が少なく、速度も同等です。

5.5 人間データ 見出しへのリンク

これまでは一様ランダムデータでテストしてきましたが、最大のパートは平均サイズから (\sqrt n) 程度逸脱します。ここで、実際のデータを見てみましょう。ヒトゲノムのk-マーです。DNA は ACGT 文字で構成されており、2ビットでエンコードできるため、(k=16) 文字の各文字列は32ビット整数を定義します6。次に、ヒトゲノムの最初の (n) 個のk-マー、染色体1から始まるものを調べます。

参考までに、下のプロットは、(k=12) のk-マーが全ヒトゲノムでどれだけ頻繁に出現するかを示しています。合計で約3Gのk-マーがあり、各k-マーの期待されるカウントは約200です。しかし、代わりに、200万回以上出現するk-マーが見られます!したがって、最初の24ビットで分割した場合、最大のパートのサイズは入力の約 (2^{-10}) にすぎず、(2^{-24}) ではありません。

累積カウントはオレンジ色で示されており、過小評価されているk-マーによる多くの平坦な領域も見られます。

[画像: Figure 27: ヒトゲノムのすべての (4^{12} = 16M) $k=12$-マーのk-マーカウントを示すプロット。ランダムデータでは各k-マーは約200回出現しますが、ここでは200万回以上出現するk-マーが見られます。]

図27:ヒトゲノムのすべての (4^{12} = 16M) $k=12$-マーのk-マーカウントを示すプロット。ランダムデータでは各k-マーは約200回出現しますが、ここでは200万回以上出現するk-マーが見られます。

[画像: Figure 28: ヒトゲノムのk-マーに対するオーバーラップツリーの構築には、はるかに多くのスペースが必要であり、16個の部分のみを使用しても、通常50%のオーバーヘッドが必要になるため、このデータ構造は実用的ではありません。]

図28:ヒトゲノムのk-マーに対するオーバーラップツリーの構築には、はるかに多くのスペースが必要であり、16個の部分のみを使用しても、通常50%のオーバーヘッドが必要になるため、このデータ構造は実用的ではありません。

5.6 プレフィックスマップ 見出しへのリンク

線形にすべてをマッピングするのではなく、不均衡なパーティションサイズを処理する方法が必要です。これは、前のと同様に、フルツリーをコンパクトに格納し、その前に、各部分の要素を含む最初のサブツリーのインデックスを格納する配列(下の青色)を配置することで行うことができます。前のオーバーラップツリーと同様に、最初のレイヤーは単純にすべての到達可能な要素(アラインメントされていない可能性あり)の最大値のリストです。

[画像: Figure 29: プレフィックスマップ(青色)は (2^b) 個の要素を格納し、各 b ビットプレフィックスについて、そのプレフィックスの要素を含む最初のサブツリーのインデックスを格納します。]

図29:プレフィックスマップ(青色)は (2^b) 個の要素を格納し、各 b ビットプレフィックスについて、そのプレフィックスの要素を含む最初のサブツリーのインデックスを格納します。

クエリに応答するには、まずその部分を見つけ、次にポインティングされた要素から始まるブロック(16要素)を読み取り、その後通常どおりサブツリーから続行します。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
pub fn search<const P: usize, const PF: bool>(&self, qb: &[u32; P]) -> [u32; P] {
    let offsets = self
        .offsets
        .iter()
        .map(|o| unsafe { self.tree.as_ptr().add(*o) })
        .collect_vec();

     let o0 = offsets[0];
-    let mut k: [usize; P] = qb.map(|q| {
-        (q as usize >> self.shift) * 4 *  16
+    let mut k: [usize; P] = qb.map(|q| {
+        unsafe { 4 * *self.prefix_map.get_unchecked(q as usize >> self.shift) }
     });
     let q_simd = qb.map(|q| Simd::<u32, 8>::splat(q));

     if let Some([o1, o2]) = offsets.array_windows().next() {
         for i in 0..P {
             let jump_to = unsafe {  o.byte_add(k[i]).read_unaligned() }.find_splat64(q_simd[i]);
             k[i] = k[i] * self.l1 + jump_to;
             prefetch_ptr(unsafe { o2.byte_add(k[i]) });
         }
     }

     for [o, o2] in offsets[1..].array_windows() {
         for i in 0..P {
             let jump_to = unsafe { *o.byte_add(k[i]) }.find_splat64(q_simd[i]);
             k[i] = k[i] * (B + 1) + jump_to;
             prefetch_ptr(unsafe { o2.byte_add(k[i]) });
         }
     }

     let o = offsets.last().unwrap();
     from_fn(|i| {
-        let idx = unsafe {  o.byte_add(k[i]).read_unaligned() }.find_splat(q_simd[i]);
+        let idx = unsafe {  o.byte_add(k[i]).read_unaligned() }.find_splat(q_simd[i]);
         unsafe { (o.byte_add(k[i]) as *const u32).add(idx).read() }
     })
}

コードスニペット 33: コードでは、前のオーバーラップバージョンと比較して唯一変わるのは、開始インデックスを線形に計算する(およびそれに応じて要素レイアウトを適応させる)代わりに、prefix_map を使用してパックツリー表現の正しい場所に直接ジャンプすることです。

[画像: Figure 30: 要素数 > 部分数 で、ツリーが少なくとも2つのレイヤーを持つ限り、この表現のスペースオーバーヘッドは再び (1/16) に近くなります。]

図30:要素数 > 部分数 で、ツリーが少なくとも2つのレイヤーを持つ限り、この表現のスペースオーバーヘッドは再び (1/16) に近くなります。

また、インターリーブクエリを再度行うこともできます。これらは小さな入力に対してわずかに高速であり、パーティショニングなしのインターリーブと同じくらい高速です。

[画像: Figure 31: ランダムデータでのインターリーブクエリ付きプレフィックスマップインデックス。]

図31:ランダムデータでのインターリーブクエリ付きプレフィックスマップインデックス。

ヒトデータでは、パーティション化されたインデックスはL1とL2では少し高速であり、一貫して約1レイヤー分の時間を節約します。より大きなインデックスでは、パフォーマンスはパーティショニングを使用しない場合と依然として非常に似ています。

[画像: Figure 32: ヒトデータでのインターリーブ付きプレフィックスマップ。]

図32:ヒトデータでのインターリーブ付きプレフィックスマップ。

5.7 要約 見出しへのリンク

[画像: Figure 33: パーティショニング結果の要約。全体として、インターリーブクエリがすでに存在する場合、パーティショニングは提供されないようです。]

図33:パーティショニング結果の要約。全体として、インターリーブクエリがすでに存在する場合、パーティショニングは提供されないようです。

6 マルチスレッド比較 見出しへのリンク

[画像: Figure 34: 6スレッドを使用すると、実行時間は27nsから7nsに低下します。速度向上は4倍未満であるため、合計RAMスループットによってボトルネックが発生しており、実際、単一スレッドでは遅い方法も最適に近いスループットに達しています。]

図34:6スレッドを使用すると、実行時間は27nsから7nsに低下します。速度向上は4倍未満であるため、合計RAMスループットによってボトルネックが発生しており、実際、単一スレッドでは遅い方法も最適に近いスループットに達しています。

7 結論 見出しへのリンク

全体として、4GBの入力に対する二分探索の 1150ns/query から、インターリーブクエリを備えた最適化Sツリーの 27ns へと、40倍以上の高速化を達成しました!この改善の大部分は、クエリのバッチ処理と今後のノードのプリフェッチによるものです。さらに高いスループットを得るために、インターリーブクエリを異なるレイヤーで行うことで、計算のCPUバウンド部分とメモリバウンド部分のバランスを取り、全体のスループットを向上させます。ノードあたり15個の要素を使用することも、16個の代わりにスループットをいくらか向上させますが、データ構造のオーバーヘッドを6.25%から13.3%に倍増させます。L3キャッシュに収まる入力では問題ありませんが、速度向上は価値があります。一方、より大きな入力では速度はメモリバウンドであるため、速度向上はなく、追加のメモリ要件はやや大きくなります。

また、データのプレフィックスによるパーティショニングについても検討しました。これはいくらかの高速化をもたらしますが、偏った入力データでは、ツリーが多くのバッファスペースを必要とするか、または各パートをツリーの最初のレベルの場所に対応付ける追加のルックアップが必要になるため、利点がすぐに減少することが判明しました。最終的には、パーティショニングの追加の複雑さと入力データの形状への依存性は、インターリーブクエリを直接使用することと比較して、速度向上には値しないと言えます。

7.1 今後の課題 見出しへのリンク

7.1.1 分岐探索 見出しへのリンク

私たちが検討したすべての方法は分岐なしであり、各クエリでまったく同じ数の反復を使用します。特にパーティショニングと組み合わせると、少数の大きなパートを通常の小さなパートとは独立して処理できる可能性があります。そのようにすれば、ほとんどのクエリをわずかに少ない反復で回答できます。

一方で、保存されるレイヤーは主にツリーのルート付近の高速なルックアップであり、コードに分岐を導入すると、予測ミスによる遅延がかなり発生する可能性があります。

7.1.2 補間探索 見出しへのリンク

最後のプロットで見たように、総RAMスループット(コアあたりのスループットではなく)は、複数のスレッドを使用するとボトルネックになります。したがって、総クエリスループットを改善する唯一の方法は、クエリあたりのRAMアクセスを厳密に少なくすることです。プレフィックスルックアップは、レイヤーをキャッシュに収まるように置き換えるだけなので役立ちません。代わりに、補間探索(Wikipedia)を使用できます。ここでは、クエリ (q) の推定位置が、周囲の要素の既知の位置の間で線形に補間されます。ランダムデータでは、これは二分探索の (O(\lg n)) ではなく、(O(\lg \lg n)) の反復しかかからず、RAMアクセスを節約できます。一方で、データがランダムでない場合、最悪の場合のパフォーマンスは (O(n)) であり、静的に制限された (O(\lg n)) ではありません。

PLA-index(Abrar and Medvedev 2024)も、正確に構築された区分線形近似で単一の補間ステップを使用します。近似後の誤差は、グローバルな上限によって決定されるため、残りの検索ステップの数を制限することもできます。

7.1.3 データをより小さくパッキングする 見出しへのリンク

RAMアクセスをより効率的に使用するもう1つのオプションは、これまで使用してきた32ビットではなく、16ビットに値をパックすることです。特に、まず16ビットプレフィックスルックアップを実行した場合、それらのビットはすでにわかっているので、クエリと値の最後の16ビットのみを比較すれば十分です。これにより、分岐係数が17から33に増加し、1GBの入力の場合、ツリーのレイヤー数が約1.5減少します。

もう1つのオプションは、Hacker News の ant6n によって提案された、「可変深度」エンコーディングのようなものです。ルートノードは、すべての値の上位16ビットを格納し、ツリーを下るにつれて、「中間」16ビットを格納し、バケット内のすべての要素に共通する最初の (p) ビットをスキップします。

7.1.4 元のデータでのインデックスを返す 見出しへのリンク

さまざまなアプリケーションでは、(q) 以上の最小値だけでなく、元のソート済みリストでのインデックスも返す方が役立つ場合があります。例えば、各アイテムに追加データを持つ配列を格納する場合です。

すべてのデータを最下位レイヤーに格納するS+ツリーを使用しているため、これはほとんど簡単です。プレフィックスマップ分割ツリーもネイティブでこれをサポートしますが、他の分割バリアントはサポートしません。それらはバッファ/パディング要素を最下位レイヤーに含み、したがって各パートの位置オフセットを個別に格納および検索する必要があります。

7.1.5 範囲クエリ 見出しへのリンク

現在のクエリメソッドを、(q) 以上の最初の値と (q) より大きい最初の値の両方を返すバージョンに拡張できます。これにより、値 (q) に対応する位置の範囲を決定できます。実際には、これを実行する最も簡単な方法は、クエリを (q) と (q+1) に単純に倍増することです。これにより、最初のレイヤーでCPUオーバーヘッドが発生しますが、クエリ実行は分岐なしのままになります。(q) が見つからないか、数回しか発生しない場合、ほとんど同じキャッシュラインをフェッチするため、メモリは効率的に再利用され、帯域幅は他のクエリに使用できます。

実際には、これは4GBの入力に対する個々のクエリよりも約20%高速ですが、範囲クエリは単一クエリよりも約60%遅くなります。小さな入力の場合、速度向上は少なく、範囲クエリは個々のランダムクエリよりも2倍以上遅くなることさえあります。

7.1.6 クエリのソート 見出しへのリンク

これまでまったく考慮してこなかったことの1つですが、Hacker News の orlp によって提起されたのは、クエリのバッチ処理です。一時的にクエリがソートされていると仮定すると、すべてのノードの再利用が最大化され、すべてがメモリから一度だけフェッチされる必要があることがわかります。クエリの数が多い場合(例えば (n/16) 以上)、最後のレイヤーの多くのノードに複数のクエリがヒットし、一度だけフェッチするとメモリ圧力が軽減されます。同様に、(n/256) クエリ以上あれば、前のレイヤーのノードを複数回フェッチすることを回避できます。

実際には、クエリのソートにどれくらいの時間がかかるかはよくわかりませんが、単純なこととしては、8ビット基数ソートを1〜2ラウンド行うことです。つまり、(256=16^2) または (65536=16^4) 個の部分にソートし、検索の最初の2つまたは4つのレイヤーをスキップできます。

7.1.7 サフィックス配列探索 見出しへのリンク

このプロジェクトの次のステップは、これを高速なサフィックス配列(Wikipedia)検索スキームに統合することです。アイデアは、例えば4番目のサフィックスごとにこのSツリーを構築し、各サフィックスの最初の32ビット(またはおそらく64ビット)をSツリーの値として使用することです。クエリが与えられると、その最初の32ビットに対応する範囲を迅速に決定し、クエリに対応するサフィックス配列の最終スライスを決定するために、残りの(おそらく小さい)範囲のみを二分探索できます。

参考文献 見出しへのリンク

Abrar, Md. Hasin, and Paul Medvedev. 2024. “Pla-Index: A K-Mer Index Exploiting Rank Curve Linearity.” In Wabi 2024. https://doi.org/10.4230/LIPICS.WABI.2024.13.

Khuong, Paul-Virak, and Pat Morin. 2017. “Array Layouts for Comparison-Based Searching.” Acm Journal of Experimental Algorithmics 22 (May): 1–39. https://doi.org/10.1145/3053370.


  1. Rust構文に慣れていない方へ。Vec<u32> は、C++ の std::vector のような、32ビット符号なし整数のアロケートされたベクトルです。&[u32] は、所有権のないメモリを指すスライス(またはビュー)です。[u32; 8] は8つの要素の配列で、std::array<unsigned int, 8> のようなものです。↩︎
  2. 後で32ビットでない理由がわかります。↩︎
  3. これは非現実的だと主張する人もいるかもしれません。なぜなら、実際にはプロセッサは動的な周波数を持つからです。しかし、ここでは現実的なベンチマークよりも再現可能なベンチマークを優先します。↩︎
  4. ;)
  5. コンパイラにこのトリックを教えることができれば、それは素晴らしいでしょう。コンパイラはすでにカウントコードを自動ベクトル化しているので、これはそれほど多くの作業ではないと思います。↩︎
  6. 最上位ビットを破棄して31ビット値を取得します。↩︎