←back to thread

Beautiful branchless binary search

(probablydance.com)
386 points ingve | 1 comments | 28 Apr 23 05:46 UTC | HN request time: 0.204s | 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 #
secondcoming ◴[28 Apr 23 06:17 UTC] No.35738053[source]▶
> The reason you mainly want branchless code is for security reasons

That just isn’t true.

replies(1): >>35738128 #
latency-guy2 ◴[28 Apr 23 06:29 UTC] No.35738128[source]▶
Which part isn't true? I think the qualifier 'mainly' definitely weakens the statement, but I'm struggling to think of how it could certainly be false statement.

This is certainly true for at minimum DDoS attacks, and I would absolutely consider that a security risk.

replies(2): >>35738144 #>>35738371 #
1. 2102922286 ◴[28 Apr 23 06:31 UTC] No.35738144[source]▶
When implementing cryptographic primitives, you want to avoid branching on secret values. The reason why is that the CPU's branch predictor will attempt to predict the value that you're branching on, and thus something about the values that you're branching on gets revealed if you can see how long a CPU takes to run a task/perform a function.

This is more than just a theoretical issue. These channel attacks have been demonstrated in practice, even if the victim CPU is running across the internet.