News for hackers. Stuff that matters.
Re:CPU branch prediction evolution over years by mysterypie on Saturday December 31, 2022 @06:56PM (#34202034)
> 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?

Re:CPU branch prediction evolution over years by shiftingleft on Saturday December 31, 2022 @07:06PM (#34202099)
Not much if you adjust the ISA for it!

https://arxiv.org/abs/2007.15919

This paper adds more or less like 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.

Re:CPU branch prediction evolution over years by coder543 on Saturday December 31, 2022 @09:24PM (#34202955)
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, not sure about subsequent versions). This 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.

Re:CPU branch prediction evolution over years by cpgxiii on Sunday January 01, 2023 @01:15AM (#34204098)
In many ways we've seen that return to dumber hardware + smarter compilers in the GPGPU realm, although even there the hardware continues to get more capable over time.

Those applications tend to work, though, on the basis that either the compiler is generating fat binaries to support multiple architecture versions (e.g. Cuda), or some sort of IR, or compilation happens at runtime (e.g. OpenCL). It doesn't really work if you want to generate single binaries that will work performantly on a wide range of hardware versions - particularly important for users answering "how will application X work on future hardware Y", which really gets in the way of general-purpose use.

That's really the great advantage of putting more smarts in the hardware - you can evolve the processor design (often to improve performance) while executing the same binaries.

Re:CPU branch prediction evolution over years by shiftingleft on Sunday January 01, 2023 @01:22AM (#34204126)
Thanks for the insights!

In my defense, 1.5X is "not much" when compared with 5 to 100X :-)

Re:CPU branch prediction evolution over years by alain94040 on Saturday December 31, 2022 @09:00PM (#34202820)
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.

Re:CPU branch prediction evolution over years by coder543 on Saturday December 31, 2022 @09:17PM (#34202906)
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, it takes 6x longer to process 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

Re:CPU branch prediction evolution over years by magicalhippo on Saturday December 31, 2022 @09:35PM (#34203015)
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.

Re:CPU branch prediction evolution over years by salawat on Sunday January 01, 2023 @11:47AM (#34207906)
Of course, now you're opening the speculative execution leak by cache timing can of worms.

Which, again, may not be an issue given your constraints.

Re:CPU branch prediction evolution over years by mysterydip on Saturday December 31, 2022 @09:34PM (#34203008)
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?
Re:CPU branch prediction evolution over years by coder543 on Saturday December 31, 2022 @09:39PM (#34203035)
The results for partially-executed instructions aren't "committed" yet, so the pipeline is flushed / thrown away, and execution starts again with an empty pipeline at the corrected address. IIRC, each stage of a pipeline has its own registers. The registers your code knows about would not have been updated until the end of the pipeline, but that branch instruction is ahead of the speculative execution, so none of the speculative results would be stored before the mistake is identified.
Re:CPU branch prediction evolution over years by magicalhippo on Saturday December 31, 2022 @09:46PM (#34203074)
Not undoing AFAIK, as it won't have committed the results before the branch resolves. However it will have to throw away all the work it did and start from the correct branch target. This is called a pipeline stall.

Particularly the Pentium 4 suffered due to a long pipeline hence long stall. The successor to the Pentium 4 was an evolved Pentium III core with a much improved branch predictor and larger cache[1] which helped it outperform the Pentium 4[2].

[1]: https://en.wikipedia.org/wiki/Pentium_M

[2]: https://en.wikipedia.org/wiki/Intel_Core_(microarchitecture)

Re:CPU branch prediction evolution over years by Retric on Saturday December 31, 2022 @11:17PM (#34203545)
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.

Re:CPU branch prediction evolution over years by Taniwha on Saturday December 31, 2022 @11:27PM (#34203603)
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)
Re:CPU branch prediction evolution over years by AgentOrange1234 on Saturday December 31, 2022 @10:07PM (#34203179)
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.
Re:CPU branch prediction evolution over years by tcmart14 on Saturday December 31, 2022 @11:39PM (#34203670)
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!
Re:CPU branch prediction evolution over years by eru on Sunday January 01, 2023 @12:13AM (#34203812)
> 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?

Re:CPU branch prediction evolution over years by cellularmitosis on Sunday January 01, 2023 @03:49AM (#34204760)
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.

Re:CPU branch prediction evolution over years by coder543 on Sunday January 01, 2023 @11:26AM (#34207646)
> 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.