October 20, 2017

Branch Prediction

Written by: Advancing Computer Science student Christopher Peterson

While browsing Stack Overflow one day, I stumbled upon a question asking why sorted arrays process faster than unsorted arrays. This led me to learn about the concept of “branch prediction.”

Branch prediction is a processor’s way of speeding up processing time by guessing what a result is going to be. For example, if you have a conditional if statement, it will guess that it will evaluate to “true” and do all the processing for that. The downside to this is that, while it’s fast if it guesses correctly, it has to go back and process everything again if it guessed wrong.

That being said, it doesn’t always guess “true.” It looks for patterns in what it’s processing. For instance, going through a loop of thousands of conditional statements, it will look for “TFTFTF,” “TTFFTTFF,” “TTT…TTFFF…FF,” or any other combinations of true and false it can. With that, it is then able to guess correctly most of the time and speed up processing.

Two-level_branch_prediction.svg

Image by Orwa diraneyya, via Wikimedia Commons. Used under the CC BY-SA 3.0 license.

Branch prediction is something that happens at the hardware level, so it’s not something that a programmer can really program into his or her software. However, compilers can add some hints to the compiled program to give the processor an idea of what the branch prediction should be like. The compilers usually do this automatically in the background based on the level of optimization they are using, but some compilers also allow the programmer to add compiler flags to their code to aid in this process.

Regardless, branch prediction is a nice optimization that a lot of modern processors use. Whether or not a programmer realizes it’s happening, it (usually) aids in speeding up even the messiest of programs, but can also slow down the program if it can’t find a pattern.

Leave A Comment