3

できれば移植可能な方法で、任意のソートされた配列で (ほとんど) ブランチのないバイナリ検索を実行するにはどうすればよいですか? (たとえば、コンパイラが CMOV 命令を生成するのを助けるコードは、これに最適です。)

「ほぼ」とは、「できるだけ少ないブランチを含む」ことを意味します。

4

1 に答える 1

5

Visual C++ 2012 (64 ビット) でテストしたときにstd::lower_bound、ブランチ (つまり、テスト) が 1 つしかないバージョンを次に示します。begin != end

template<class FwdIt, class T, class P>
FwdIt branchless_lower_bound(FwdIt begin, FwdIt end, T const &val, P pred)
{
    while (begin != end)
    {
        FwdIt middle(begin);
        std::advance(middle, std::distance(begin, end) >> 1);
        FwdIt middle_plus_one(middle);
        ++middle_plus_one;
        bool const b = pred(*middle, val);
        begin = b ? middle_plus_one : begin;
        end = b ? end : middle;
    }
    return begin;
}

SSE2 をサポートする 32 ビットでは、おそらく Conditional-Move 命令も使用して、同様の速度を得ることができます。

これで、速度は小さな配列の線形検索と競合するはずですが、確認する価値があるかもしれません.

vector<int>興味深いことに、 CPU のサイズが最大 (約) 45 の場合でも、線形検索の方が高速であることがわかりました。理由はわかりませんが、私の測定値が正確であったかどうかはわかりません...

また、これは i5 CPU での分岐バイナリ検索よりも高速ではないことがわかりました。

于 2013-01-22T08:46:10.557 に答える