How Branch Prediction Works in CPUs - Computerphile

How does branch prediction speed up operations? Matt Godbolt continues the deep dive into the inner workings of the CPU
/ computerphile
/ computer_phile
This video was filmed and edited by Sean Riley.
Computer Science at the University of Nottingham: bit.ly/nottscomputer
Computerphile is a sister project to Brady Haran's Numberphile. More at www.bradyharanblog.com
Thank you to Jane Street for their support of this channel. Learn more: www.janestreet.com

[@llamallama1509]

I like the little anecdote at the end about the ray tracer and changing a test to gain a big speed boost.

[@axelBr1]

In awe of the people who came up with such simple ideas to do branch prediction. And the people that work out how to build that logic in silicon, so that it can run in one click tick are gods!

[@kevincozens6837]

Kudos to the host for tending to ask very good questions about the topic being discussed.

[@rudiklein]

Being able to explain a complex technical subject in a way I can understand is an amazing skill.

[@aaronr.9644]

I've been programming for a very long time but I didn't realise how sophisticated these branch predictors could get. The idea that it can compute a simple hash in a single clock cycle and use that to capture patterns is fascinating. Now that makes me want to go look into the details of some of these open CPU designs :)

[@elirane85]

During my CS degree we had some classes about CPU architecture and pipelines, I was always impressed at how complicated the things we take for granted are actually are and what we studied was very very basic things, not even close to the magic which is Branch Prediction

[@eloniusz]

Branch prediction is why there is a lot of algorithms that work faster on sorted data even if the order of elements theoreticaly doesn't matter for this algorithm.

[@nefex99]

Very cool - great, understandable explanation!

[@baltakatei]

Side note: Branch prediction is incompatible with keeping memory secret. Disable branch prediction when handling secrets.

[@uttarandas]

Thanks, I needed this.

[@prakharrai1090]

Wonderful!

[@ArneChristianRosenfeldt]

IBM managed to slow down their mainframe using branch prediction. How often do you have JMP (else branch) ? DSPs just had zero overhead loop instructions similar to the one in 80186 . So at the start of the loop you have an instruction where the immediate value says from where to jump back to here. Only needs a single register, not a table. Works on inner loops.

[@musmuk5350]

Excellent video thank you

[@vadrif-draco]

Is that Ray Tracing video at the end soon to be released? Can't find it via search by name

[@custard131]

i seem to have missed the original but this guy seems great at explaining CPU stuff

[@deepak.rocks.]

Nice 👍

[@bjryan19]

As a software developer I'm wondering how you optimize for branch prediction when the cpu is effectively a black box. I guess you can only speculate that you are getting branches wrong or maybe there is a cpu setting to store branch prediction hits and misses?

[@pmmeurcatpics]

The part where the branch predictor increments/decrements the probability of each branch prediction reminded me of JITs, which too were covered recently on Computerphile. Do I understand correctly that this branch prediction adjustment too happens at runtime? Or could the program be dry-ran a couple of times during the compilation process to preconfigure the branch predictor somehow? It's a fascinating piece of technology either way:)

[@clehaxze]

I realized this is Godbolt!!!!

[@hyperion6483]

If we can decode that an instruction is a branch way ahead of the execution step that will decide to take it or not, isn't it possible to build a second pipeline in parallel as soon as we know that this instruction is a branch that could be taken, such that when we come to the execution step that will decide if we have to take it or not we only need to decide if we stay on the actual pipeline or switch to the second one we built in parallel ?