ミス予測の削減について質問しました。
Jerry Coffin が印象的な答えをくれました。
二分探索はブランチレスですが、集合交差アルゴリズムで使用すると、元の二分探索よりもはるかに遅いことがわかりました。どういう理由ですか？
アップデート：
次のイベントを使用して、i7 プロセッサの分岐ミス予測の数をテストします: BR_MISS_PRED_RETIRED。枝のないバージョンは、元のバージョンより枝のミスが約半分であることがわかりました。
キャッシュ ミスの場合: LLC_MISSES を使用して、最後のレベルのキャッシュ ミスの数をテストします。
ただし、時間は元の約 2.5 倍です。
条件付き移動 (ブランチレス) 検索の問題は、配列が大きく、メモリ アクセス時間が分岐の予測ミスに比べて大きい場合に発生します。
条件付き移動検索は次のようなものです。
int needle; // value we are searching for
int *base = ...; // base pointer
int n; // number of elements in the current region
while (n > 1) {
int middle = n/2;
base += (needle < *base[middle]) ? 0 : middle;
n -= middle;
}
分岐を使用せずに条件付きで更新することに注意してくださいbase(少なくとも、コンパイラが三項演算子を分岐として実装することを決定しないと仮定します)。問題はbase、各反復の の値が前の反復での比較の結果にデータ依存しているため、メモリへのアクセスが一度に 1 つずつ発生し、データ依存関係を介してシリアル化されることです。
大きな配列を検索する場合、これによりメモリレベルの並列処理の可能性がなくなり、検索は次のようになりますlog2(N) * average_access_time。分岐ベースの検索には、そのようなデータの依存関係はありません。反復間の推測された制御の依存関係のみがあります。CPU が方向を選択し、それに従います。推測が正しければ、現在の反復と次の反復の結果を同時にロードします。それだけではありません。憶測は続き、一度に数十個の荷物が飛んでいる可能性があります。
もちろん、CPU が常に正しく推測するとは限りません。最悪の場合、分岐が完全に予測不可能な場合 (データと針の値に偏りがない場合)、半分の確率で間違っています。それでも、それは平均し0.5 + 0.25 + 0.125 + ... = ~1て、現在のアクセスを超えて飛行中の追加のアクセスを維持することを意味します. これは単なる理論上の話ではありません。ランダムなデータに対して二分探索を試してみると、並列処理が 2 倍になるため、分岐なしの探索よりも分岐ベースの探索が 2 倍速くなる可能性があります。
多くのデータセットでは、分岐方向は完全にランダムではないため、あなたの場合のように 2 倍以上のスピードアップが見られます。
キャッシュに収まる小さな配列の場合、状況は逆になります。ブランチレス検索には、これと同じ「シリアル依存性」の問題がまだありますが、ロード レイテンシは小さく、数サイクルです。一方、ブランチベースの検索では、約 20 サイクルのコストがかかる一定の予測ミスが発生するため、この場合は通常、ブランチレスの方が高速になります。
しばらく前に、おそらくスタックオーバーフローでも、データ フェッチ コストを回避する興味深いアプローチを見ました。誰かが、配列を暗黙的なツリーとして扱い、左の子と右の子の両方をプリフェッチするような方法で二分探索を作成しました。これは、現在の要素がテスト値と比較される前に行われました。
メモリ要求を 2 倍に増やすと実際に検索が高速化されるというのは直感に反するように思われましたが、フェッチを早く開始することで余分なメモリ ヒットを補ったようです。
私の記憶が正しければ、値が使用されていないため、読み取りの半分は事実上非依存でした。これは、投機的プリフェッチ ロード、非依存ロード、またはループ時にフェッチされた値の 1 つが現在の要素を保持するレジスタに移動される通常のロードによって実行できます。
そのバージョンは大量のロードとストアを行っているためです。
プロセッサが複数のパイプラインを持っているため、このようなタイトなループでの分岐予測は効果がないことがよくあります。分岐テストが評価されているため、両方のコード パスが既にデコードおよび評価されています。1 つのパスの結果のみが保持されますが、通常、分岐からのパイプライン ストールはありません。
一方、メモリへの書き込みには影響があります。通常、CPU のメモリ キャッシュに書き込みますが、MMU はキャッシュ ラインをシステムの残りの部分と同期させておく必要があります 配列が大きく、基本的にランダムな順序でアクセスしている場合、一定の値が得られますキャッシュ ミスを引き起こし、CPU にメモリ キャッシュをリロードさせます。
次に、元のバイナリ検索を使用します。ランダムな場所への配列アクセスは、特にコンパイラが変数にレジスタを使用できないため、分岐ミスよりもはるかに優れているわけではありません。