3 ms·

How can you call it branchless if it has "while (length > 0) {"

dehrmann 3y ago
I took a stab at the same problem a while ago. Since the upper bound of iterations is based on the input length, if you write your search in a way that extra iterations don't change the result, you can use a switch fallthrough to "unroll" the loop and not have to branch. https://github.com/ehrmann/branchless-binary-search/blob/master/src/bbsearch.c https://github.com/ehrmann/branchless-binary-search/blob/mas...
fsckboy 3y ago
the article covers that right at the top: “branchless” because the if compiles down to a conditional move instruction rather than a branch/conditional jump.
Const-me 3y ago
That particular branch is well-predicted for long arrays. You probably only gonna have a single misprediction for the complete binary search function, the performance consequence of that branch is negligible. People (and compilers, too) don’t write branchless code just for the sake of it, they do because it helps with performance.
- kragen 3y ago
  sometimes branchless code also stops timing side channel attacks, but it's not enough by itself
einpoklum 3y ago
Because that's a branch that's "always" taken, except for once - which, speed-wise, is very close to always taken, i.e. not a branch. The author counts the branching inside the loop, which is often taken and often not taken.
- postalrat 3y ago
  It's not impossible to remove that branch. Until you do that then this is a reduced branch implementation.
sltkr 3y ago
This is literally addressed in the article: More branchless, more better? Short answer: no. This section can be skipped but here’s the long answer: For n elements where 2k <= n < 2k+1 sb_lower_bound will always do k+1 comparisons. On a 64-bit machine that means at most 64 iterations of the while (length > 0) loop. So it’s possible to write a “fully branchless” version that doesn’t have the length check by using a switch with intentional fall-through. size_t length = last - first; size_t rem; switch(std::bit_width(length)) { case 64: rem = length % 2; length /= 2; first += comp(first[length], value) \* (length + rem); case 63: rem = length % 2; length /= 2; first += comp(first[length], value) \* (length + rem); // ... case 1: rem = length % 2; length /= 2; first += comp(first[length], value) \* (length + rem); } return first; If you’re not familiar with switch, think of it as a jump into code. In our case to the exact place from which there are exactly the right number of comparisons left to do. “Is it any faster?” No. Modern x86 processors handle loop conditions well as they’re predictable; we’re very likely to remain in the loop. And that’s good especially because it saves us from writing templates or macros or copy-paste-edit the 64 cases. (Maybe people will RTFA if I paste it into the comments.)
- amethyst 3y ago
  TBH I had to read that part two times before realizing that it was describing an an unrolled loop.

I took a stab at the same problem a while ago. Since the upper bound of iterations is based on the input length, if you write your search in a way that extra iterations don't change the result, you can use a switch fallthrough to "unroll" the loop and not have to branch. https://github.com/ehrmann/branchless-binary-search/blob/master/src/bbsearch.c https://github.com/ehrmann/branchless-binary-search/blob/mas...

fsckboy 3y ago

the article covers that right at the top: “branchless” because the if compiles down to a conditional move instruction rather than a branch/conditional jump.

Const-me 3y ago

That particular branch is well-predicted for long arrays. You probably only gonna have a single misprediction for the complete binary search function, the performance consequence of that branch is negligible. People (and compilers, too) don’t write branchless code just for the sake of it, they do because it helps with performance.

kragen 3y ago
sometimes branchless code also stops timing side channel attacks, but it's not enough by itself

einpoklum 3y ago

Because that's a branch that's "always" taken, except for once - which, speed-wise, is very close to always taken, i.e. not a branch. The author counts the branching inside the loop, which is often taken and often not taken.

postalrat 3y ago
It's not impossible to remove that branch. Until you do that then this is a reduced branch implementation.

sltkr 3y ago

This is literally addressed in the article: More branchless, more better? Short answer: no. This section can be skipped but here’s the long answer: For n elements where 2k <= n < 2k+1 sb_lower_bound will always do k+1 comparisons. On a 64-bit machine that means at most 64 iterations of the while (length > 0) loop. So it’s possible to write a “fully branchless” version that doesn’t have the length check by using a switch with intentional fall-through. size_t length = last - first; size_t rem; switch(std::bit_width(length)) { case 64: rem = length % 2; length /= 2; first += comp(first[length], value) \* (length + rem); case 63: rem = length % 2; length /= 2; first += comp(first[length], value) \* (length + rem); // ... case 1: rem = length % 2; length /= 2; first += comp(first[length], value) \* (length + rem); } return first; If you’re not familiar with switch, think of it as a jump into code. In our case to the exact place from which there are exactly the right number of comparisons left to do. “Is it any faster?” No. Modern x86 processors handle loop conditions well as they’re predictable; we’re very likely to remain in the loop. And that’s good especially because it saves us from writing templates or macros or copy-paste-edit the 64 cases. (Maybe people will RTFA if I paste it into the comments.)

amethyst 3y ago
TBH I had to read that part two times before realizing that it was describing an an unrolled loop.