Are You Smarter than a Branch Predictor?

In the last post, we discussed branches in code, how these conditional branches disrupt the performance of modern pipelined CPUs, and how these chips use branch predictors to make a guess as to which way a branch will be resolved. We saw that always taken or never taken branches can easily be guessed by the CPU, and that when we had a random branch, it was only predicted about 50% of the time, or no better than just guessing. We’ll now run a small experiment to understand exactly how much our branch predictor is able to remember.

As before, we’ll be using Google Benchmark as a harness for our program, but instead of the processing throughput, we’ll just be measuring the branch miss percentages reported to us by perf. We’re going to reuse the same Object class and total_size functions to introduce our branch.

While we previously initialized the objects using a random distribution of true/false, we’re now going to use a randomized pattern of various lengths, which will be repeated over the 100,000 objects that we’re summing up. To generate our randomized pattern, we’ll use the following function.

We’ll then apply those patterns to our set of objects, as follows

With this setup, if we were to generate a random pattern of length 1, we’d expect all of our objects to be the same, either all true or all false. As we get longer patterns, we’ll have longer stretches of randomized is_valid values before the pattern repeats, this is illustrated for patterns of length 1, 3 and 5 below

The benchmark is setup to be parameterized on the length of the pattern to generate. Of course our pattern of length 5 could generate {true, true, true, true, true} which would be identical to a pattern of length 1, so we’ll run our benchmark over many runs to get a good average of the performance. We’ll then repeat this for patterns ranging from length 1 (all branches identical) to 100,000 (all branches randomized with no pattern) and see the results.

For our baseline, we’ll take the percentage of branches correctly predicted on our 100,000 length pattern as a no intelligent predictions baseline. For this baseline we actually predict about 75% of the branches correctly, since half our branches are the well predicted loop over the vector, and then half of the remaining branches are randomly guessed correctly. So we compute our branch predictor intelligence for a pattern length p as a function of the accuracy of our random baseline pattern r

With this equation, a perfectly knowledgeable branch predictor would have a BranchIQ of 1, while our random branch predictor would have a BranchIQ of 0. Now running this over a variety of pattern lengths for 20 runs each, we see the following graph emerge, running on my Linux host1

While this is a simplified program, the results here show that up to a pattern length of about 200, the branch predictor is able to achieve a near 100% accuracy in predicting the branches over the course of the benchmark. As the pattern length increases beyond 200 there begins to be a sharp decline in the ability of the predictor to follow the pattern until at our final, lengthy patterns the branch predictor is barely improving over random guesses.

While I usually focus on x86_64, I also decided to run this same benchmark on my M3 Mac. This required a bit of fiddling as perf isn’t available on macOS, but using the built-in xctrace utility and some scripting, I was able to get a similar2 benchmark setup, and ran for a similar range of pattern lengths.

As you can see here, it seems that the branch predictor within the Apple ARM chip is more sophisticated when measured by this benchmark. All the way up to roughly 10,000 randomized patterns we see little variation in the ability to predict the branches correctly. Of course, as this is one of very few branches in this program, it’s likely that in a real system the performance would be worse, but it’s informative to see how well the baseline branch prediction is able to run.

With this demonstration, we’ve shown that the hardware branch predictor can learn not just simple patterns, but potentially hundreds or thousands of branching decisions. I would say this definitively confirms that I’m nowhere near as smart as a branch predictor, at least when it comes to memorizing patterns of random booleans! Additionally this should serve as a reminder to measure before making code changes to optimize performance. While you may think a branch is being poorly predicted and causing degradation, this demonstration has shown that surprisingly complex patterns can be predicted. Until confirmed with perf or other tooling, making a premature switch to a branchless implementation may only serve to pessimize your performance.

If you’ve enjoyed this post, please subscribe for more articles on writing high performance code! If you have questions, comments or suggestions on future articles, feel free to drop them below, thanks.