Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Beautiful branchless binary search

probablydance.com

Post reply on HN
Print view View original

1–10 of 198 posts

Re: Beautiful branchless binary search

#2

Post by rowanG077 »

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.

Re: Beautiful branchless binary search

#3

Post by berkut »

rowanG077 wrote: post #2

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 p…

> "The reason you mainly want branchless code is for security reasons where a timing sidechannel could reveal information."

Erm, that likely depends on the industry you're in?

In HPC, branchless algorithms are often needed to use wide architectures (SIMD / GPUs) to their full capacity...

Re: Beautiful branchless binary search

#4

Post by vkazanov »

rowanG077 wrote: post #2

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 p…

Branchless algos (especially in the case where there truly are no explicit or implicit branches) is just as useful for performance purposes as it is for security. Having a branchless algo at hand is like being halfway to data-level parallelism either through SIMD or GPU.

Re: Beautiful branchless binary search

#6

Post by hmry »

rowanG077 wrote: post #2

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 p…

cmov doesn't go through the branch predictor, and AFAIK it even loads both operands unconditionally every time before checking the condition. I see no reason to consider it a branch, and have never heard anybody else categorize it as one.

Re: Beautiful branchless binary search

#7

Post by secondcoming »

rowanG077 wrote: post #2

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 p…

> The reason you mainly want branchless code is for security reasons

That just isn’t true.

Re: Beautiful branchless binary search

#8

Post by vkazanov »

kookamamie wrote: post #5

Trusting the C++ compiler to emit a specific instruction for guaranteed performance - cute, but not realistic.

I don't think it is the instruction that makes the difference. Cmov is a branch either way.

Branches can be unpredictable and slow, no matter what instructions, (or tables, or whatever) are used to introduce the branch at question.

It is predictable nature of branching in this algo that makes the difference. Which makes me wonder...

EDIT: the cmov vs explicit branching story is a bit more complicated than just branch vs no branch.

Re: Beautiful branchless binary search

#9

Post by 2102922286 »

rowanG077 wrote: post #2

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 p…

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).

Post reply on HN