[zenolijo]

I do wonder how branch prediction actually works in the CPU, predicting which branch to take also seems like it should be expensive, but I guess something clever is going on.

I've also found G_LIKELY and G_UNLIKELY in glib to be useful when writing some types of performance-critical code. Would be a fun experiment to compare the assembly when using it and not using it.

[bee_rider]

Modern branch predictors are pretty sophisticated. But, it is also worth keeping in mind that you can do pretty good, for a lot of codes, by predicting simple things like “backwards jumps will probably be followed.” Because a backwards jump is probably a loop, and so jumping backwards is by far the most likely thing to do (because most loops go through more than one iteration).

And a lot of programmers are willing to conspire with the hardware folks, to make sure their heuristics work out. Poor branches, never had any chances.

[moregrist]

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.

[_chris_]

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

[o11c]

> 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?

[_chris_]

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.

[hansvm]

Semantically it's just a table from instruction location to branch probability. Some nuances exist in:

- Table overflow mitigation: multi-leveled tables, not wasting space on 100% predicted branches, etc

- Table eviction: Rolling counts are actually impossible without space consumption; do you have space wasted, periodic flushing, exponential moving averages, etc

- Table initialization: When do you start caring about a branch (and wasting table space), how conservative are the initial parameters, etc

- Table overflow: What do you do when a branch doesn't fit in the table but should

As a rule of thumb, no extra information/context is used for branch prediction. If a program over the course of a few thousand instructions hits a branch X% of the time, then X will be the branch prediction. If you have context you want to use to influence the prediction, you need to manifest that context as additional lines of assembly the predictor can use in its lookup table.

As another rule of thumb, if the hot path has more than a few thousand branches (on modern architectures, often just a few thousand <100% branches (you want the assembly to generate the jump-if-not-equal in the right direction for that architecture though, else you'll get a 100% misprediction rate instead)) then you'll hit slow paths -- multi-leveled search, mispredicted branches, etc.

It's reasonably interesting, and given that it's hardware it's definitely clever, but it's not _that_ clever from a software perspective. Is there anything in particular you're curious about?

[aclindsa]

> As a rule of thumb, no extra information/context is used for branch prediction.

As you'll find in the results of the recent branch prediction competition, global branch history (a record of which branches have recently been taken) is a piece of context critical to achieving the high accuracy of modern branch predictors: https://ericrotenberg.wordpress.ncsu.edu/cbp2025-workshop-pr...

[NobodyNada]

> If a program over the course of a few thousand instructions hits a branch X% of the time, then X will be the branch prediction.

This is not completely true - modern branch predictors can recognize patterns such as "this branch is taken every other time", or "every 5th time", etc. They also can, in some cases, recognize correlations between nearby branches.

However, they won't use factors like register or memory contents to predict branches, because that would require waiting for that data to be available to make the prediction -- which of course defeats the point of branch prediction.

[delta_p_delta_x]

> I do wonder how branch prediction actually works in the CPU, predicting which branch to take also seems like it should be expensive

There are a few hardware algorithms that are vendor-dependent. The earliest branch predictors were two-bit saturating counters that moved between four states of 'strongly taken', 'weakly taken', 'weakly not taken', 'strongly not taken', and the state change depended on the eventual computed result of the branch.

Newer branch predictors are stuff like two-level adaptive branch predictors that are a hardware `std::unordered_map` of branch instruction addresses to the above-mentioned saturating counters; this remembers the result of the last n (where n is the size of the map) branch instructions.

Ryzen CPUs contain perceptron branch predictors that are basically hardware neural networks—not far from LLMs.

[ActorNightly]

Branch prediction is probably the main reason CPUs got fast in the past 2 decades. As Jim Keller descrbied, modern BPs look very much like neural networks.

[pkaye]

Here is some examples of the different branch prediction algorithms.

https://enesharman.medium.com/branch-prediction-algorithms-a...

[rayiner]

It’s fairly expensive but well suited to pipelined implementations in hardware circuits: https://medium.com/@himanshu0525125/global-history-branch-pr.... Modern CPU branch predictors can deliver multiple predictions per clock cycle.

[dmoy]

There's a bunch of ways it works. There's a tradeoff between hardware cost and accuracy. Sometimes it's static, sometimes there's a counter of varying size (1 bit, 2 bit, etc). It can get a lot more complicated.

The basic branch predictors are very cheap, and often good enough (90%+ accuracy).

Patterson & Hennessy goes into a bunch of detail.

[atq2119]

By now I'd assume that all modern high performance CPUs use some form of TAGE (tagged geometric history) branch prediction, so that's a good keyword to search for if you really want to get into it.

[remexre]

https://danluu.com/branch-prediction/ is a good illustrated overview of a few algorithms.

[checker659]

There are two things to predict: whether there will be a branch, and if so, to where.

[ip26]

It is expensive, but it’s even more expensive not to.