←back to thread

Beautiful branchless binary search

(probablydance.com)
386 points ingve | 1 comments | 28 Apr 23 05:46 UTC | HN request time: 1.197s | source
Show context
rowanG077 ◴[28 Apr 23 06:02 UTC] No.35737974[source]▶
Nice algorithm. I don't agree that it is branchless however. Cmov is a branching instruction for sure. And it doesn't really matter whether a branch can be well predicted. The reason you mainly want branchless code is for security reasons where a timing sidechannel could reveal information. Calling this algorithm branchless devalues the term into something meaningless.

Edit: Everybody in the comments is focusing on performance. For performance sensitive code the point is not that it's branchless, the point is that it is fast, that some branchless code is faster than branching code is an implementation detail. During encryption the point is that it certain codepaths MUST be branchless.

replies(8): >>35738013 #>>35738026 #>>35738051 #>>35738053 #>>35738063 #>>35738216 #>>35738547 #>>35738591 #
1. 2102922286 ◴[28 Apr 23 06:19 UTC] No.35738063[source]▶
cmov (i.e. conditional move) doesn't branch. By branch here, we mean "at point at which the successor program counter value might be one of two locations." It's true that this _does_ have security implications, however this is frequently used as a term of art by performance engineers (see https://www.youtube.com/watch?v=g-WPhYREFjk for example).

> And it doesn't really matter whether a branch can be well predicted.

I'm not so sure this is true. See https://lemire.me/blog/2019/10/15/mispredicted-branches-can-... as an example.

A properly predicted branch can be _faster_ than a cmov instruction, however the important point is avoiding the branch mispredict. The fact that we're using cmov is beside the point. We could achieve a similar effect by performing a subtraction and doing bitwise arithmetic to extract the sign bit (which, in effect, performs a comparison).