binary_search

Nice catch. I had goofed by omitting optimization when checking this from an iPad. That said, this brings me to my original reason for checking this, which is to say that it did not use a cmov instruction to eliminate unnecessary branching from the loop, so it is probably slower than a binary search that does: https://en.algorithmica.org/hpc/data-structures/binary-searc... That had been the entire motivation behind this commit to OpenZFS: https://github.com/openzfs/zfs/commit/677c6f8457943fe5b56d7a... It should be possible to adapt this to benchmark both the inlined bsearch() against an implementation designed to encourage the compiler to emit a conditional move to skip a branch to see which is faster: https://github.com/scandum/binary_search My guess is the cmov version will win. I assume merits a bug report, although I suspect improving

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."

This is really cool! About a decade ago I did research on sorting and searching, which was the same type of work going on here (https://github.com/pbiggar/sorting-branches-caching). I found it was extremely difficult to accurately say whether one algorithm is faster than another in the general case. I found a bunch of speed improvements that probably only apply in processors with very long pipelines (like the P4)). Execution speed is probably the right metric here, but it makes it hard to understand _why_ it's faster. PS. Looking at "boundless interpolated search" (https://github.com/scandum/binary_search/blob/master/binary-...), it seems it's missing a `++checks`. I initially thought this could be the cause of a misreporting it as being faster, but I see the benchmark is run-time based so that wouldn't cause it unless the incrementing it

The readme doesn't describe why it's faster. Looking at the code of the variant that is the fastest: https://github.com/scandum/binary_search/blob/master/binary-... It seems like it's a quaternary search which seems like an arbitrary "magic number" of interior points. It's easy to understand what it does if you already know other variants like ternary search (cut search space into 3 to pick 2 interior points) or golden section search (same thing as ternary except in golden ratio). Here, quaternary search is just picking 3 interior points after dividing into 4 parts. So the speed up is the same as how b-trees get their speedup: increase branching factor which costs more comparisons but reduces the depth. I might be wrong, but instead of quaternary it could also be 5-ary or 8-ary or any B-ary and any of these variants can also have the pote