Bitwise Binary Search: Elegant and Fast
&gt; However, I’ve found that some compilers, e.g. GCC on x86-64 will refuse to make this variant branchless. I hate how fickle compilers can be sometimes, and I wish compilers exposed not just the likely&#x2F;unlikely attributes, but also an attribute that allows you to mark something as unpredictable to nudge the compiler towards using branchless techniques like CMOV’s.<p>There has been a Clang bug open about this for more than 4 years: <a href="https:&#x2F;&#x2F;bugs.llvm.org&#x2F;show_bug.cgi?id=40027" rel="nofollow">https:&#x2F;&#x2F;bugs.llvm.org&#x2F;show_bug.cgi?id=40027</a><p>Naturally, this came up in the context of binary searches, but it is the same for any tree traversal where each branch has maximum entropy (which means it&#x27;s optimal from a traversal time point of view). Clang is especially reluctant to emit predicated instructions (this is a major pet peeve of mine).<p>In my codebase I ended up having a function<p><pre><code>    template &lt;class T, class I, class Compare&gt;
    I argmax(const T&amp; a, const T&amp; b, I i, I j, Compare cmp) {
      return cmp(a, b) ? j : i;
    }
</code></pre>
which I then specialize for various integer types and code it with inline ASM to use a CMOV. This allows to write all kinds of binary searches and tree traversals without having to do inline ASM every time. I&#x27;d really prefer not to have to do that, but the performance impact is significant.<p>In this post, I don&#x27;t think there is a comparison with a classical binary search implemented in a branch-free fashion? Searching along dyadic intervals is a cute trick, but it&#x27;s not clear whether the improvement comes from that or simply from being branch-free.