Hacker News Reader

Comment by 4k0hz | Hacker News Reader

There's no branch in that code either way. The comparison operator outputs a value (which is arithmetic, not a branch), and that value is added unconditionally.

View on HN

Isn’t there an implicit check to exit the loop?

The check isn't important; what's important is being predictable so the CPU can guess which way the check will go. I don't know exactly how it works, but after the first couple of loops, the predictor will assume it's always going to end up in the loop and make that the fast path. It may guess wrong the first couple of loops, and the last check wrong, but the other 997 will be correct.

There is a static branch predictor that is used if there is no statistic on a branching instruction yet, and it's really simple: Jumps backward are assumed to be taken (they usually are from a loop), jumps forward are assumed to be not taken.

So the jump that forms the loop will be predicted correctly for all executions but the very last (when the loop ends).

That's very cute.

I wonder how much more complicated and effective statistical predictors are.

They get much more complicated, but their effectiveness tops out where certain branches just can’t be predicted in advance.

“that code” refers to the body of the loop.

Unless the loop is unrolled, yes, there is a branch to exit the loop. But then that doesn’t matter because the whole goal at the beginning was to avoid branch misprediction (which is not the same thing as avoiding branches entirely).

Reply on news.ycombinator.com