Hacker News Reader

Comment by moregrist | Hacker News Reader

There’s ample information out there. There are quite a few text books, blogs, and YouTube videos covering computer architecture, including branch prediction.

For example: - Dan Luu has a nice write-up: https://danluu.com/branch-prediction/ - Wikipedia’s page is decent: https://en.m.wikipedia.org/wiki/Branch_predictor

> I've also found G_LIKELY and G_UNLIKELY in glib to be useful when writing some types of performance-critical code.

A lot of the time this is a hint to the compiler on what the expected paths are so it can keep those paths linear. IIRC, this mainly helps instruction cache locality.

View on HN

> A lot of the time this is a hint to the compiler on what the expected paths are so it can keep those paths linear. IIRC, this mainly helps instruction cache locality.

The real value is that the easiest branch to predict is a never-taken branch. So if the compiler can turn a branch into a never-taken branch with the common path being straight line code, then you win big.

And it takes no space or effort to predict never taken branches.

> And it takes no space or effort to predict never taken branches.

Is that actually true, given that branch history is stored lossily? What if other branches that have the same hash are all always taken?

A BPU needs to predict 3 things:

  - 1) Is there a branch here?
  - 2) If so, is it taken?
  - 3) If so, where to?

If a conditional branch is never taken, then it's effectively a NOP, and you never store it anywhere, so you treat (1) as "no there isn't a branch here." Doesn't get cheaper than that.

Of course, (1) and (3) are very important, so you pick your hashes to reduce aliasing to some low, but acceptable level. Otherwise you just have to eat mispredicts if you alias too much.

Note: (1) and (3) aren't really functions of history, they're functions of their static location in the binary (I'm simplifying a tad but whatever). You can more freely alias on (2), which is very history-dependent, because (1) will guard it.

Reply on news.ycombinator.com