CPU branch prediction evolution over years (2017)

by Keyframe • 4 years ago

210 70 4 years ago

Is the moral of CPU branch prediction that generating dynamically branch-free code is preferable to generating statically branch-free?

jleahy• 4 years ago

That’s certainly true, a correctly predicted branch costs little more than a nop or unconditional jmp.

Code doesn’t have to be branch free, just branch in a predictable way.

Statically branch free code is great when you have things that are genuinely unpredictable, think branches driven by data. You might reach for min/max as an example of that, but in most cases these tend to be highly predictable. Control flow in a decompressor is probably a better example (eg. literal vs copy).

mhh__5• 4 years ago

A correctly predicted branch, in a sense can cost less than a nop in that it does actual work and requires no additional effort from the backend.

taeric6• 4 years ago

I would think it is less on the "don't have branches" but more "try to have a happy/common path." This is oddly at odds with how humans work as operators. For human operators, you typically want each interaction to be as unpredictable as possible, to keep their attention. Falling into rote action is a sure way to get a mistake out of a person. (Or to get them to quit.)

However, for computers, it is good to view them as a machine. As most machines, they are best if they are doing the exact same thing over and over. And over.

As such, if you can contrive for the machine to always take the same branch the vast majority of the time, you will get it to work faster. Whether this is done with a dynamic arrangement of the data, or a static arrangement of the code depends largely on the specifics. Consider sorting networks as a fun exploration of the idea. They can be ridiculously fast, as they always do the same amount of work. (Provided you have enough execution units.)

marcosdumay3• 4 years ago

The more predictable a work process becomes, the quicker people can do it too.

Our issue is with correctness, that is something we not even think about in computers. So, it's not really surprising that this completely different issue has different constraints than speed.

superjan• 4 years ago

This is related to an idea from data oriented design: Split up your data such that each piece of data needs exactly the same transform, and do all those at once.

mhh__5• 4 years ago

Avoiding either > Easily predicted branch > conditional move > difficult to predict branch

masklinn• 4 years ago

Avoiding either > Easily predicted branch

Branchless code can easily out-cost a well-predicted branch (and its content if any).

marcosdumay3• 4 years ago

Well, reducing the share number of branches in your code has exactly the same impact as improving the predictor's performance. So, no I don't think you can get this conclusion from the article.

The article is only biased into improving the CPU and ignoring any opportunity of improving your program. What is understandable, because it's about CPU architectures.

In practice, you will want to improve whatever part you have the freedom to change. You usually can not choose.

mungoman2• 4 years ago

The branches still take (instruction) cache. So it is beneficial to reduce the number of branches, even if they could have been predicted accurately.

jasonwatkinspdx• 4 years ago

The way Linus put it in an old newsgroup posting from his Transmeta days was something like: "the job of a cpu is to generate the minimum number of cache misses as early as possible."

BoardsOfCanada• 4 years ago

I could have sworn that PPro used 2-bit saturating counters, but I checked and: "The P6 rejects the commonly used Smith algorithm, which maintains four states using two bits, in favor of the more recent Yeh method[1]. This adaptive algorithm uses four bits of branch history and can recognize and predict repeatable sequences of branches, for example, taken–taken–not taken."

One other thing I wondered about is if there have been improvements to the recovery of mispredicted branches that have not yet been retired. It seems like the huge OOO-windows of the latest Apple and Intel CPUs would see diminishing returns otherwise. Anyone knows?

brigade• 4 years ago

Yeah, these days it's likely for only the frontend to stall during misprediction recovery. Already decoded µops from before the branch still make their way through the backend as normal. If you have enough of those (long dependency chains or the branch was reordered early enough), it's possible that the misprediction has effectively no penalty.

As a corollary, this means that when possible you want the dependency chain for branches to be as independent and short as possible, so the CPU can reorder and resolve branches as early as possible.

gpderetta• 4 years ago

The original pentium famously used a 2 bit counter except, IIRC, it was buggy and it didn't actually saturate. It was fixed on the Pentium MMX.

A simple 2 bit predictor wouldn't have been enough for the PPro as the deeper pipeline and the new OoO window required a better predictor.

throwawaylinux• 4 years ago

Misprediction recovery is an important area of optimization. Mispredictions tend to flush and begin refetching ASAP, so rather than wait until retire, they will do that when they execute, including out of order (a newer branch could flush before an older one is resolved, and later itself could be flushed by that older one).

There are also several levels of predictor and mistakes in the low latency but less accurate ones can cause recovery events if they are overridden a few cycles later by slower predictors.

Flush / recovery is made as light weight as possible, only flushing instructions after the branch, and only the parts of the pipeline that the oldest one has reached.

There is some literature on controlling speculation if you are not confident. Say if you have a really poorly predicted indirect branch target where a mispredict is not 50/50 but 99/1, and it depends on a very slow source, then you might not want to speculate 500 instructions ahead of that but say okay let's just wait for it to resolve. Or, if you have a 50/50 hard to predict branch, you might kick off some prefetching down the other path when you see it so recovery is faster (but this will cost more power). I don't know if anybody does anything with these "hard to predict branches" today. Apparently it's actually quite difficult to predict whether a branch is hard to predict, and the resources to make that prediction can be put to better use just trying to predict them instead of predicting that you can't predict them :) Although that might change. Point is al kinds of misprediction optimization are actively being pursued.

dang• 4 years ago

How and why CPUs do “branch prediction” (2017) - https://news.ycombinator.com/item?id=20324092 - July 2019 (33 comments)

A history of branch prediction - https://news.ycombinator.com/item?id=15078574 - Aug 2017 (65 comments)

skywal_l2• 4 years ago

Do you ever take a day off?

Yeahsureok• 4 years ago

Ever considered that the related threads comment is easily scripted?

sweetjuly2• 4 years ago

We also didn’t talk at all about how different workloads affect different branch predictors. Predictor performance varies not only based on table size but also based on which particular program is run.

One of my favorite little tradeoffs around this topic is around power usage.

This is because, in many cases, adding more hardware (generally) increases total power usage. I.e. adding more execution units makes the processor faster at the expense of increased power usage. Good branch predictors, however, are very notable exception to this rule because even though the increase instantaneous power usage over a small delta-t, over a much larger one they tend to save a LOT of power by avoiding costly mispredictions. This means that, somewhat counterintuitively, adding more hardware decreases total power, which is really cool!

mhh__5• 4 years ago

Similar with a well designed cache. Lots of static power usage, but saves you so many hits (especially instruction caches)

nayuki• 4 years ago

You mean reducing energy usage. Energy is power integrated over time.

mysterypie• 4 years ago

One way you might design a CPU is to have the CPU do all of the work for one instruction, then move on to the next instruction, do all of the work for the next instruction, and so on.

If a modern CPU did no branch prediction, how much slower would it be? Just curious to know a ballpark figure, like 5x slower or 100x slower?

shiftingleft2• 4 years ago

Not much if you adjust the ISA for it!

https://arxiv.org/abs/2007.15919

This paper adds (more or less) a really big branch delay slot to fill the cpu with work while it's waiting for the branch to resolve.

Impossibility of Spectre-like attacks is a neat side-effect.

coder5434• 4 years ago

I've only glanced over that paper, but they're using a processor with a 5-stage pipeline, which is really short by modern standards (Zen 1 uses a 19-stage pipeline, and I couldn't quickly find the number for subsequent versions of Zen). Using a very short pipeline significantly reduces the advantage of control flow speculation (CFS)... but they still showed CFS offering up to a ~50% advantage over their best alternative, if I'm reading that right.

I wish they had included the geometric mean of their benchmarks, but I didn't see it anywhere, and I'm not going to run the numbers right now. Even if the speedup CFS offered on a 5-stage pipeline is "only" 25%, that is still huge... and on a larger pipeline, that delta would grow. "Not much" is drastically different from my interpretation of those results.

I do think security is extremely important, but I'm not convinced that things are currently so terrible that this is the only way forward, as the authors seemed to imply.

OTOH, I would enjoy seeing a return of an Itanium-style ISA that moves a lot of speculation from the hardware to the compiler. I think compilers are in a much better place now than they were when Itanium hit the scene, which did not help Itanium's problems.

alain94040• 4 years ago

Some back of the envelope math:

- there is a branch instruction every 10 instructions or so

- if you can't predict, assume you guess wrong half of the time

So every 20 instructions or so, you take the wrong branch. Sounds like it could be a significant overhead, from 10% - 50% depending on what the code inside the loop is doing.

For instance, if your code is doing only arithmetic operations, no load/store, such as computing factorial or other silly integer math, 20 instructions would probably take 20 cycles or less to execute, but the branch failure would cause a similar delay. So that's 50% overhead. In the other case, assume the 20 instructions are fairly slow (lots of memory accesses), then your branch penalty won't feel so bad.

coder5434• 4 years ago

One of the other comments around here[0] points to one truly classic StackOverflow question[1] where the answer is "branch prediction". In that example, the CPU is 6x slower at processing the data when the branch predictor is failing repeatedly. It is surely still succeeding some of the time, since that question wasn't specifically built to foil the branch predictor, so that isn't even the upper bound for performance loss.

If you designed a CPU to lack a branch predictor, you would certainly make different choices that would reduce the penalty of that, but there would still be a significant penalty.

Modern CPUs are all pipelined[2] because it allows a sequence of instructions to be executed (to some degree) in parallel. With out-of-order CPUs, the amount of parallelism that is possible for a sequence of instructions increases even more.

Without a branch predictor, you would have to stall the entire pipeline as soon as you see a branch instruction, until that instruction is finished. Obviously if you don't have a branch predictor, you're going to choose to have a shorter pipeline, but the penalty of each branch instruction will still be significant.

There's a lot of nuance to any proper answer to this question, and it's been years since I learned about this or thought deeply about this, so I'm probably not the right person to provide a deeper answer at this point. The performance impact would be significant.

[0] https://news.ycombinator.com/item?id=34202230

[1] https://stackoverflow.com/questions/11227809/why-is-processi...

[2] https://en.wikipedia.org/wiki/Instruction_pipelining

mysterydip• 4 years ago

If the branch predictor fails, does it have to take time undoing the steps it's already done? Or are pipelines long enough that the fail would be detected before registers/pointers are updated?

magicalhippo2• 4 years ago

Also, as I understand it, a big part of the "win" of branch prediction is to ensure those caches are filled.

If you can execute ahead, through branches, you can resolve cache misses while the pipeline catches up, effectively reducing the cache miss penalty. If instead you have to stop at a branch, you're always gonna pay the full cache miss penalty, which can be significant.

Retric• 4 years ago

That’s mostly true, but the heat generated by calculations which where thrown away still impacts the CPU’s thermal budget and the devices battery life. This coupled with branch prediction overhead makes failed branch predictions far worse than simply stalling would be without them.

However, even very dumb branch prediction tends to be well worth it for the vast majority of code.

Taniwha• 4 years ago

A useful (very rough) rule of thumb here is that every 5th instruction is a branch this limits all sorts of things - like branch cost and prediction algorithms and sizes, but also how many instructions it's worth decoding per clock which puts practical limits on system issue rates (a predicted taken branch typically reduces the issue rate)

AgentOrange1234• 4 years ago

There’s no easy answer. Branch prediction is a key enabler for other kinds of speculation. Modern CPUs can have dozens of ops in a partially executed state. This lets them, e.g., simultaneously fetch many lines of memory that are going to be needed soon, under the assumption that a branch will/won’t be taken. If you can’t predict branches, you won’t be able to keep nearly so many ops in flight, and the whole apparatus for speculative execution starts to make a lot less sense. Everything is workload dependent, but I suspect you’re more in the 100x than 5x range after the knock-on effects.

tcmart14• 4 years ago

Wouldn't any kind of measurement have to rely on a heuristic? We would need a baseline as to how often a branch prediction is accurate. If the branch prediction is always wrong, we can assume the speed would be the same. If the branch prediction is always correct, then it should be a pretty big speed up. I would be interested to see a paper on about this topic, so if anyone has one, please share!

eru• 4 years ago

If the branch prediction is always wrong, we can assume the speed would be the same.

Not sure, because in that case the wrongly-predicting CPU is doing lots of wasted work, which contributes to eg waste heat. A non-predicting CPU could do more real work, than a wrong-predicting one?

cellularmitosis• 4 years ago

Hopefully others can correct me here, but my intuition is that the lower bound of performance would be determined by the pipeline length. I.e. if your instruction pipeline was 8 stages, worst-case scenario is flushing the pipeline on every instruction, which would cause it to run at 1/8th speed. (At one point I believe the Pentium 4 had a twenty-stage pipeline, yikes!).

In practice, branches aren't every instruction, so the impact will be less.

coder5434• 4 years ago

At one point I believe the Pentium 4 had a twenty-stage pipeline, yikes!

Modern pipeline lengths aren't documented publicly as often as they could be, but Zen 1 was a 19 stage pipeline, and it performed great for the time. But, I think Pentium 4's full pipeline was 31 stages. Regardless, I think CPU designers these days have better tools and techniques for dealing with long pipelines.

drexlspivey• 4 years ago

classic StackOverflow question “Why is processing a sorted array faster than processing an unsorted array?” https://stackoverflow.com/questions/11227809/why-is-processi...

travisgriggs• 4 years ago

Wow, I really enjoyed reading this. It really made me miss the old CPU Praxis articles that made me fall in love with the old ARS-Technica.

I’d be curious what branch prediction algorithms more recent CPY architectures have employed. Arm in general, Apples various Arm chips, etc.

ramesh31• 4 years ago

Is branch prediction even a good idea? I remember it blowing my mind when I learned about the existence of this stuff from Spectre. Should CPUs even try to be this "clever"? It seems like something better left to the kernel.

mikebenfield• 4 years ago

Branch prediction is pretty fundamental to CPU performance; unless we want much slower CPUs it’s necessary.

Although it’s interesting to think about how software could help with branch prediction, the simple answer about the kernel thing is that software is the wrong place in the architecture for branch prediction to happen. Maybe there’s some crazy alternative way things could be done, but in anything like the current computing model branch prediction has to happen in hardware.

Izkata• 4 years ago

Maybe there’s some crazy alternative way things could be done

"Branchless programming" is an umbrella term for techniques in existing programming languages to avoid branches.

justsomehnguy2• 4 years ago

    CPU Single Thread Rating

    Name                                pts     Date
    Intel Core2 Duo E7600 @ 3.06GHz   1,270     Q2 2009
    Intel Core Solo T1350 @ 1.86GHz     413     Q1 2009
    Intel Core Solo U1300 @ 1.06GHz     340     Q3 2009
    Intel Atom D425 @ 1.80GHz           320     Q1 2011

These Atoms were quite gutted to have a low die size and low TDP, and the first things what were cut are cache and branch prediction. You can see how D425 from 2011 is on the same level as two year earlier and a almost a half GHz slower U1300.

In the Bonnell microarchitecture, internal micro-ops can contain both a memory load and a memory store in connection with an ALU operation, thus being more similar to the x86 level and more powerful than the micro-ops used in previous designs.[3] This enables relatively good performance with only two integer ALUs, and without any instruction reordering, speculative execution or register renaming. A side effect of having no speculative execution is invulnerability against Meltdown and Spectre.

https://www.cpubenchmark.net/compare/948vs579vs593vs609/Inte...

https://en.wikipedia.org/wiki/Bonnell_(microarchitecture)

bsoft16385• 4 years ago

Bonnell has a branch predictor: https://en.wikichip.org/wiki/intel/microarchitectures/bonnel...

In-order execution does not mean that there is no branch prediction, it just means that the number of instructions speculated is much smaller.

1over137• 4 years ago

Could the compiler put PGO (profile guided optimization) results into a table embedded into the executable binary and feed that to the CPU?

saagarjha• 4 years ago

Yes, the “table” is encoded into the code itself ;)

astrange2• 4 years ago

The CPU can’t necessarily use any per-branch hints, including special “unlikely” branch instructions or implying one direction is less likely than the other, because not all designs have that info available at the predictor. It especially usually doesn’t know the address of the branch.

tjalfi• 4 years ago

Some architectures such as Itanium, MIPS, and x86 have branch hint instructions that allow the compiler to indicate whether branches are taken. I'm not sure about Itanium, but they weren't really beneficial on MIPS or x86; the MIPS branch hint instructions are deprecated and Intel's compiler stopped emitting branch hints at least a decade ago.

bad-engineers• 4 years ago

Easy to follow up until "two-level adaptive, global", then it became harder to read. But I'm still going. Note that there is a typo here: "P(A not taken) + P(B taken)". Suppose to be: "P(A not taken) * P(B taken)".

jtolmar• 4 years ago

I noticed that every scheme after BTFNT kept state. Did anyone ever come up with a better stateless branch predictor than it?

CPU branch prediction evolution over years (2017)

Related Stories