Fastest Branchless Binary Search (mhdm.dev)
from tedu to programming on 11 Aug 2023 18:09
https://azorius.net/g/programming/p/P9VrKNW322Pshj3YX2-Fastest-Branchless-Binary-Search 

template <class ForwardIt, class T, class Compare>
constexpr ForwardIt sb_lower_bound(
      ForwardIt first, ForwardIt last, const T& value, Compare comp) {
   auto length = last - first;
   while (length > 0) {
      auto rem = length % 2;
      length /= 2;
      if (comp(first[length], value)) {
         first += length + rem;
      }
   }
   return first;
}

Oh and I’m sorry about just thrusting C++ code on you. Rude, I know. You don’t really need to know C++ to understand this article, just iterators (first and last), basically pointers to elements in an array, though note they can point one past the last array entry.

#cxx #programming

threaded - newest

tedu on 11 Aug 2023 18:15 collapse

There's a brief mention of what happens if the comparison function is slow, but then it doesn't really go too deep into that. I think this code is actually kinda slow in the case where you could bail early because it always performs max comparisons. Half the time you can skip one comparison if I'm guessing correctly? But there's maybe an implicit requirement that they're implementing lower bound, with less than only comparison.