Comment by uecker
4 months ago
A comparator can be inlined just fine in C. See here where the full example is folded to a constant: https://godbolt.org/z/bnsvGjrje
Does not work if the compiler can not look into the function, but the same is true in C++.
That does not show the comparator being inlined since everything was folded into a constant, although I suppose it was. Neat.
Edit: It sort of works for the bsearch() standard library function:
https://godbolt.org/z/3vEYrscof
However, it optimized the binary search into a linear search. I wanted to see it implement a binary search, so I tried with a bigger array:
https://godbolt.org/z/rjbev3xGM
Now it calls bsearch instead of inlining the comparator.
With optimization, it will really inline it with an unknown size array: https://godbolt.org/z/sK3nK34Y4
That's not the most general case, but it's better than I expected.
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 this is a low priority much like my last report in this area:
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=110001