Fastest Branchless Binary Search

<p><pre><code> auto length = last - first; while (length &gt; 0) { auto half = length &#x2F; 2; if (comp(first[half], value)) { &#x2F;&#x2F; length - half equals half + length % 2 first += length - half; } length = half; } return first; </code></pre> can be restructured with a conditional `first += half` and instead `length -= half` (see, e.g., Listing 2 in <a href="https:&#x2F;&#x2F;arxiv.org&#x2F;abs&#x2F;1509.05053" rel="nofollow">https:&#x2F;&#x2F;arxiv.org&#x2F;abs&#x2F;1509.05053</a>). Doing it this way requires one final comparison when `length &gt; 0` on entry, because the while condition is `length &gt; 1`, but moves the subtraction off the critical path.

I implemented a variation of this in ZFS’ btree implementation a few years ago:<p><a href="https:&#x2F;&#x2F;github.com&#x2F;openzfs&#x2F;zfs&#x2F;commit&#x2F;677c6f8457943fe5b56d7aa8807010a104563e4a">https:&#x2F;&#x2F;github.com&#x2F;openzfs&#x2F;zfs&#x2F;commit&#x2F;677c6f8457943fe5b56d7a...</a><p>It only works if the comparator is inlined, which is why I had to use a macro and duplicate the code everywhere. C++’s templates effectively do the same thing.<p>By the way, I notice that C++ favors comparators returning a boolean while C favors comparators returning -1, 0 or 1. Let me share this simple macro from ZFS:<p>#define TREE_CMP(a, b) (((a) &gt; (b)) - ((a) &lt; (b)))<p>Use that to generate -1, 0 or 1. Then if you want a boolean, compare the output to &lt; 0 to get the boolean that a C++ comparator would return and as long as the comparator is inlined, the compiler will automatically simplify, such that you get only 1 comparison.<p>The C++ STL designers who opted for a boolean return value from comparators did premature optimization, since they had no reason to break with the C convention under C++’s &quot;the compiler will inline and optimize&quot; philosophy. The neat thing about the C way is that if you want to generate a boolean from the comparator, you have a choice for the boolean’s semantics (&lt; 0 or &lt;= 0) while C++ made that choice for you.<p>That said, I have never needed the latter and as a much younger developer, I thought that the C++ way was superior, but time has caused me to conclude the C guys got this right.<p>Finally, since I am on topic of comparators, there is a fairly famous example of how to generate -1, 0 or 1 when comparing against 0:<p><a href="https:&#x2F;&#x2F;www.cs.cornell.edu&#x2F;courses&#x2F;cs6120&#x2F;2020fa&#x2F;blog&#x2F;super-optimization&#x2F;" rel="nofollow">https:&#x2F;&#x2F;www.cs.cornell.edu&#x2F;courses&#x2F;cs6120&#x2F;2020fa&#x2F;blog&#x2F;super-...</a><p>I only mention it since it is interesting and I like sharing interesting things. Reimplementing the signum function from there with TREE_CMP() does not generate code as good as the superoptimized example in godbolt:<p><a href="https:&#x2F;&#x2F;godbolt.org&#x2F;z&#x2F;1j8nWjnqP" rel="nofollow">https:&#x2F;&#x2F;godbolt.org&#x2F;z&#x2F;1j8nWjnqP</a><p>It is probably an optimization opportunity for GCC.

Related repository of interest: <a href="https:&#x2F;&#x2F;github.com&#x2F;scandum&#x2F;binary_search">https:&#x2F;&#x2F;github.com&#x2F;scandum&#x2F;binary_search</a><p><i>&quot;The most notable variant, the monobound binary search, executes two to four times faster than the standard binary search on arrays smaller than 1 million 32 bit integers.&quot;</i>