最速のブランチレス二分探索

• この記事では、標準の std::lower_bound 関数より2倍高速で、より短い汎用二分探索の C++ 実装について論じています。
• 新しい実装は、分岐/条件付きジャンプではなく条件付き移動命令にコンパイルされるため、「ブランチレス」です。
• 二分探索は、ソート済みリストを中央の要素で2つに分け、中央の値を与えられた値と比較することで動作します。比較結果に応じて、どちらの部分リストを続けて探索するかを決定します。
• この記事では、分岐予測という概念についても論じています。これは、プロセッサが命令を並列実行して速度を高める技術です。しかし、二分探索は予測しにくいため、分岐予測は理想的ではありません。
• 著者は、標準実装や branchless_lower_bound 版より高速な新しい二分探索実装 sb_lower_bound を紹介しています。これは、ループ内の命令数がはるかに少ないため高速です。
• 著者はまた、探索リストの分割に別の方法を使う、より高速な版 bb_lower_bound も提示しています。
• この記事は、プログラムの最も遅い部分がプロセッサにとって予測不能な探索や比較を含むなら、clang を -mllvm -x86-cmov-converter=false とともに使ってみることを提案して締めくくられています。より高速な二分探索が必要なら、sb_lower_bound を試してみてください。
• 著者はまた、新しい二分探索実装のコードを提供し、それぞれの性能について詳しく論じています。
• この記事は、ホットループ内のアセンブリ命令数を9から8に減らした sb_lower_bound のリファクタリング版で更新されており、これにより速度がわずかに向上しました。
• 著者はまた、プリフェッチという概念についても論じています。これは、特定のメモリ領域をキャッシュに先読みし、プリフェッチされたデータが実際に必要になったときに L1/L2 キャッシュ遅延だけが発生するようにするものです。256KB+ 向けにプリフェッチを追加した sb_lower_bound 版も提供されています。
• この記事は Mihail Dumitrescu によって執筆され、2023年6月24日に公開されました.

[GN⁺]

Hacker Newsの意見

• 記事は、分岐なし二分探索の概念と潜在的な利点について論じています。
• あるコメントでは、分岐を排除する必要性に疑問を呈し、分岐予測ミスによるパイプラインの停滞はアーキテクチャの本質的な部分ではないと示唆しています。
• コメントではさらに、すべての処理は本質的に分岐であり、こうした分岐が性能を損なわない理由は、メインパイプライン上の分岐ではないからだと説明しています。
• 別のコメントでは、lowerBound を実装するために、“bare-metal” 言語へコンパイルされる Nim 言語の使用を提案しています。
• コードが最初に一致したものを返すのか、それとも一致した任意のものを返すのかについての議論があり、コードの機能を理解することの重要性を強調しています。
• あるコメントでは、ブログ記事の直感的な導入を称賛しており、最速の汎用二分探索 C++ 実装をすぐに提示していると述べています。
• コメントでは、Zig stdlib は二分探索のために C++ を呼び出していないと指摘し、Zig stdlib の二分探索へのリンクを提供しています。
• 二分探索と分岐の問題についての議論があり、問題は分岐そのものではなく、比較が完了するまで次に読み込むメモリ位置がわからないというデータ依存性から生じるのではないかと示唆しています。
• コメントでは、Cascade Lake プロセッサ上での二分探索の性能結果を共有し、clang はこの特定のコードの最適化において gcc より劣ると示唆しています。
• あるコメントでは、「BUT RUST」リンクのリンク先に疑問を呈し、このリンクは古いようだと述べています。
• コメントでは、より複雑な比較関数ではこの結果は維持されないと指摘し、最良の性能は基本型に対して sb_lower_bound を使い、それ以外の場合は std::lower_bound を使うことで達成できると提案しています。
• 最後のコメントでは、予測不能な属性がいまや cmov 変換パスに影響を与えるようになったと述べ、追加情報のためのリンクを提供しています。