CSci 2021 Lab 0xC: Code Optimization and Branch Prediction

In this lab we will continue to practice profiling tools. In particular we will explore optimizations for branch prediction using cachegrind's branch simulation tool. Recall the effect of branches on performance. Modern processors often have speculative execution, meaning they load instructions preemptively based on a prediction about which side of a branch to take. Branch mispredictions can be costly. On the other hand, modern processors are quite proficient at finding patterns in the data to accurately predict most branches. In these problems you will explore the performance implications of avoiding branches and/or making them more predictable.

There are four parts to the lab, each contained in a separate function. You call each function by passing the corresponding number as an argument to the lab0xC program. Each of these functions accomplishes some task using code written in an imperative style that should be familiar to you. Your task is to identify lines in this code that could be optimized with respect to branch prediction.

cp /web/classes/Fall-2018/csci2021-010/labs/0xC/{lab0xC.c,stringSrc.h,vectorSrc.h,solution} .

compile with : gcc lab0xC.c -o lab0xC -lm

You will be using the cachegrind tool that was introduced previously, but with one modification. Add --branch-sim=yes to enable branch simulation. The full command line will look like this

valgrind --tool=cachegrind --branch-sim=yes ./lab0xC function# [N]

You may use kcachegrind to help you profile:

./kcachegrind callgrind.out.[some number]

Look for places where unnecessary branches can be removed (after all, any extra processing is a drain on peformance. Also look for branches that can be avoided by instead writing a conditional move (followup question: why do conditional moves not incur penalties for branch prediction?). Finally, see if you can make any of the branches more predicatble. How do your changes affect the overall performance and branch prediction?