The small test case below shows the observable slow down with
cmp provided as-is (first timings), and no slow down with
less_than provided instead (second timings).
First, you're measuring non-monomorphic dispatch by passing
different closures in the same run. This is probably not a
representative benchmark for your application. Measure them in
isolation.
Second, any searching or sorting function that has an unbiased
branch at it's heart will exhibit potentially unstable
performance. Key to performance (and not just with LuaJIT) is to
use a branch-free comparisons and a branch-free step or swap.
The usual trick is to replace the comparison with
sar(a - b, 31)
which returns either 0 (all zeros) or -1 (all ones). [Assuming
you've aliased bit.arshift to sar.]
Then use the result as a mask (or inverted mask) for the step
amount or swap index. There are more elegant formulations of
binary search that easily accomodate such a masked step amount.
If log2(N) is low enough, you can even unroll the steps.
[
Actually, branch-free binary search can be optimized further. And
there are many more algorithmic choices. Some references:
