Fastest Branchless Binary Search(mhdm.dev)
mhdm.dev
Fastest Branchless Binary Search
https://mhdm.dev/posts/sb_lower_bound/
4 comments
_Pragma("GCC unroll 9")
while (nelems > 1) {
auto half = nelems / 2;
nelems -= half;
first += (comp(first[half - 1], value)) * half;
}
return first;
I devised this a couple years ago for use in ZFS’ btree code:
https://github.com/openzfs/zfs/commit/677c6f8457943fe5b56d7a...
Feel to have it under your choice of OSI approved license, including CC-0.
Yeah, that's the same structure. For simple comparisons, I would expect a conditional move, 0 branch except for the data-independent loop.
My recollection is that the branch predictor should mispredict the last branch of the loop. Unrolling eliminates that misprediction by replacing all of the loop iteration branches with a jump table branch that it will predict correctly more often. This is micro-optimizing to an extreme. I vaguely recall seeing a slight improvement in a microbenchmark that I attributed to this effect.
[deleted]
I implemented a variation of this in ZFS’ btree implementation a few years ago:
https://github.com/openzfs/zfs/commit/677c6f8457943fe5b56d7a...
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.
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:
#define TREE_CMP(a, b) (((a) > (b)) - ((a) < (b)))
Use that to generate -1, 0 or 1. Then if you want a boolean, compare the output to < 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.
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 "the compiler will inline and optimize" 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 (< 0 or <= 0) while C++ made that choice for you.
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.
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:
https://www.cs.cornell.edu/courses/cs6120/2020fa/blog/super-...
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:
https://godbolt.org/z/1j8nWjnqP
It is probably an optimization opportunity for GCC.
https://github.com/openzfs/zfs/commit/677c6f8457943fe5b56d7a...
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.
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:
#define TREE_CMP(a, b) (((a) > (b)) - ((a) < (b)))
Use that to generate -1, 0 or 1. Then if you want a boolean, compare the output to < 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.
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 "the compiler will inline and optimize" 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 (< 0 or <= 0) while C++ made that choice for you.
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.
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:
https://www.cs.cornell.edu/courses/cs6120/2020fa/blog/super-...
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:
https://godbolt.org/z/1j8nWjnqP
It is probably an optimization opportunity for GCC.
Related repository of interest: https://github.com/scandum/binary_search
"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."
"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."
can be restructured with a conditional `first += half` and instead `length -= half` (see, e.g., Listing 2 in https://arxiv.org/abs/1509.05053). Doing it this way requires one final comparison when `length > 0` on entry, because the while condition is `length > 1`, but moves the subtraction off the critical path.