Sixteen branches is all you ... get?
In my last post I experimented with the unlikely macro from the Linux kernel and learned about how compilers organize instructions to improve performance. I also had originally assumed that these macros were for influencing branch prediction values, but that was actually not the case! I decided to go learn a bit about branch prediction and stumbled on this awesome video by BitLemon.
In his video he shows a progression of simple branch prediction algorithms to more complex ones, describing how they generally rely on the CPU "caching" the recent history of branches to help guide future guesses on which branches will be taken. Naturally the best way for me to build intuition about this is to try and experiment with it, and thus this blog post was born :)
Let's do a quick experiment to see if we can find out how much "memory" our CPU has (hint: it comes to around sixteen branch decisions, hence the title!)
Experiment setup - how we can measure impact of branch prediction
Alright so the basic idea behind branch prediction is that we remember some of the previous branching decisions. The CPU keeps track of the previous sequences of branch prediction results, like "True False False True", "True True False False", etc. If it starts executing a certain branch again, it will look at the previous sequences it saw and pick the most likely sequence to try and execute. This avoids "branch misses" where we make the wrong speculative execution and incur a large latency penalty (more on this later).
Given that the prediction is based on sequences of branch decisions, we can probably find the limit of the system by producing progressively "harder" to predict sequences. To me the most natural way to do this is by just creating longer sequences of decisions, where we have many "True" decisions then one "False" decision. The following simple loop does that exactly, with the sequence of "False False False False True ...":
long loop_mod_5(int num_iterations) {
long total = 0;
for (int i = 0; i < num_iterations; i++) {
if (i % 5 == 0) {
total += 1;
} else {
total += 2;
}
}
return total;
}
Every fifth iteration of this loop will take the if branch, while all others take the else branch. Extending the idea, we can make a bunch of different loop_mod_X loops that take the if branch every X instructions. This will allow us to graph the sequence length vs. other metrics.
How can we generate all of these loops though? To save our poor wrists from all of that typing we can create a simple python script to generate this code for us. Let's make a script with some helper code for measuring performance as well:
import sys
modulo = int(sys.argv[1])
times = int(sys.argv[2])
runs = int(sys.argv[3])
print(f"""\
#include <stdint.h>
#include <stdio.h>
#include <time.h>
#define MODULO {modulo}
#define TIMES {times}
#define RUNS {runs}
long loop_mod_{modulo}(int times) {{
long total = 0;
for (int i = 0; i < times; i++) {{
if (i % MODULO == 0) {{
total += 1;
}} else {{
total += 2;
}}
}}
return total;
}}
int64_t get_curr_time_nanos(void) {{
struct timespec ts;
clock_gettime(CLOCK_MONOTONIC, &ts);
return (int64_t)ts.tv_sec * 1000000000LL + ts.tv_nsec;
}}
int main(void) {{
volatile long result = 0;
int64_t total_time = 0;
for (int i = 0; i < RUNS; i++) {{
int64_t start = get_curr_time_nanos();
result += loop_mod_{modulo}(TIMES);
total_time += get_curr_time_nanos() - start;
}}
printf("modulo={modulo}, times=%d, runs=%d\\n", TIMES, RUNS);
printf("average: %lld ns\\n", total_time / RUNS);
printf("result: %ld\\n", result);
return 0;
}}
""")
Running this script with a command like python generate.py 10 1000 10 will generate the loop_mod_10 loop that runs 1000 iterations and 10 runs to get the average latency. For the final step, we want to be able to measure a lot of different sequence lengths, so we can run this generate -> compile -> test in a loop:
for n in $(seq 1 1 100)
do
python3 generate.py $n 100000 10 > src/loop_$n.c;
gcc src/loop_$n.c -o bin/loop_$n;
./bin/loop_$n;
done
This will print out results like this:
modulo=1, times=10000000, runs=100
average: 7282430 ns
result: 1000000000
modulo=2, times=10000000, runs=100
average: 7288380 ns
result: 1500000000
modulo=3, times=10000000, runs=100
average: 7354530 ns
result: 1666666600
modulo=4, times=10000000, runs=100
average: 7344080 ns
result: 1750000000
modulo=5, times=10000000, runs=100
average: 7370160 ns
result: 1800000000
modulo=6, times=10000000, runs=100
average: 7160640 ns
result: 1833333300
...
Nice. Now that we have our different sequence length programs produced and running, let's collect some data.
Experiment 1 - measuring latency of long sequences
For our first experiment, let's see the impact of increasing that sequence length on the latency of the overall program. If increasing the length of the sequence leads to worse branch prediction (and more branch misses) we should see that the latency of the program will increase as we increase the sequence length. Running our loop again and capturing the average of latency of the run, we create this plot:
Interesting. There does look to be a trend in the data after increasing to a sequence length of ~12 or so, but there is also a lot of noise. Latency is likely too coarse grained of a metric to see the impact here - let's see if we can use more fine-grained metrics to investigate.
Experiment 2 - using perf to measure branch misses directly
Linux thankfully offers a whole suite of performance tools for measuring experiments just like this one. One of the best ones is called perf which can output process metrics over the course of the process lifetime. If we run perf stat ./bin/loop_5 we can see a lot of cool performance information:
Performance counter stats for './bin/loop_5':
3,300.53 msec task-clock # 1.000 CPUs utilized
6 context-switches # 1.818 /sec
0 cpu-migrations # 0.000 /sec
58 page-faults # 17.573 /sec
9,206,036,924 cycles # 2.789 GHz
3,889,978,481 stalled-cycles-frontend # 42.25% frontend cycles idle
21,228,643,968 instructions # 2.31 insn per cycle
# 0.18 stalled cycles per insn
2,204,680,092 branches # 667.977 M/sec
88,578 branch-misses # 0.00% of all branches
3.301277986 seconds time elapsed
3.282314000 seconds user
0.018996000 seconds sys
Context-switches, page-faults, number of instructions, wow there is a lot here! And to our luck, the Linux kernel team also developed the branch-misses metric, which exactly fits our experiment. Let's do another loop while using perf stat with the -x, -e..., and -r metrics to control format, metrics returned, and the number of runs:
for n in $(seq 1 1 1024):
do
python3 generate.py $n 100000 10 > src/loop_$n.c;
gcc src/loop_$n.c -o bin/loop_$n;
sudo perf -x , -e branch-misses -r ./bin/loop_$n 2>>perf.csv;
done
Our perf.csv file will contain the outputted metrics. With a little bit of data processing we can view the branch-misses percentages for each of our runs:
Now that is a much clearer trend! As we increased the sequence length we can see there is an extremely clear mode change in the data around sequence length 11. This is likely due to hitting the limit of the branch prediction "memory" as we get a huge increase in branch miss percentage. Satisfying to see! After that sharp increase the percentage of branch misses tends downward as the sequence length increases, which is expected as they occur less often. In the limit the branch misprediction rate should likely be similar to our small sequences of one or two.
For context, both of these experiments were run on an old 2011 Macbook air with Linux installed on to it. It may not be 100% reproducible on other machines because branch prediction setups change from CPU generation to generation. For example I ran the same experiment (only for the latency metrics, MacOs doesn't have perf stat...) and did not see the exact same trend in the data. Nevertheless we can still see that the CPU has a limit to how many branch results it can keep track of :)
Conclusions
It was pretty satisfying to produce a set of code that actually hit a limit on the number of branches. It goes to show that there is a price to pay for program complexity, even in this day in age when CPUs are getting more and more capable at handling our convoluted programs. Let's keep these sorts of experiments in our backpockets, as you never know when they'll come in handy!
And a random aside - it is worth pointing out that you likely won't have to explicitly think about branch misses when writing most code - branch prediction is generally much more complex than just "memorizing" previous branch results, so more often than not you won't have too many branch misses. Again though, it is useful to know. With tools like perf stat it is straightforward to check if our programs have a ton of branch misses. And to figure out where they are coming from, we can lean on the magic of experimentation.
Thanks for reading, and see you in my next experiment!!