3 ms·

With optimization, it will really inline it with an unknown size array: https://godbolt.org/z/sK3nK34Y4 https://godbolt.org/z/sK3nK34Y4 That's not the most gen

• ryao 1y ago
  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-search/#removing-branches 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/677c6f8457943fe5b56d7aa8807010a104563e4a 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 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 https://gcc.gnu.org/bugzilla/show_bug.cgi?id=110001