c++ - 如何对任意排序的数据执行(几乎)无分支的二进制搜索？

Question

我如何以一种最好的可移植方式对任意排序的数组执行(几乎)无分支的二进制搜索？ (例如，帮助编译器生成 CMOV 指令的代码对此非常有用。)

“几乎”是指“包含尽可能少的分支”。

Answer 1

这是 std::lower_bound 的一个版本当我使用 Visual C++ 2012(64 位)对其进行测试时，它只有 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 位可能也可以使用条件移动指令，以获得类似的速度。

现在速度应该与小型数组的线性搜索相比具有竞争力......但它可能值得检查。

---

有趣的是，我发现对于 vector<int>在我的 CPU 上最大(大约)45，线性搜索仍然更快!不知道为什么，或者我的测量是否准确......

---

另外事实证明，这并不比我的 i5 CPU 上的分支二进制搜索快。