So far so good. Our test case works as follows: build a linked list where the nodes live sequentially in contiguous memory, then see how long it takes to sum them all up:

On a server with a relatively old Xeon E5-1650 v3, running sum1 with the sample data takes 0.36 milliseconds, which means that we’re processing our linked list at roughly 14GB/s. In the rest of the post will will identify the bottleneck and get around it with value speculation, bringing the throughput for this dataset to 30GB/s.

The impact of the fix varies depending on the size of the dataset. If it is already entirely in the CPU cache, the improvement is much more pronounced, since otherwise we are quickly constrained by how fast we can read data from RAM. This graph shows the performance improvement over differently sized datasets (higher is better):

The chart shows the performance of sum1 together with the performance of two improved functions, sum2 and sum3. We go from a throughput of 14GB/s in sum1 to more than 45GB/s in sum3 if the data fits entirely in the L1 cache (the 16kB dataset), with the performance decreasing slightly for datasets fitting in the L2 and L3 cache (128kB and 5MB datasets). If the dataset does not fit entirely in any CPU cache (~4GB dataset) we go from 10GB/s to 15GB/s, which is as fast as the RAM allows.

and its very readable assembly version:

The loop body is made out of 4 instructions, the last of which a jump. Without special measures, every instruction up to the jne must be executed before proceeding to the next instruction, since we need to know if we’ll go to the beginning of the loop or continue. In other words the conditional jump would introduce a barrier in the instruction level parallelism internal to the CPU.

However, executing many instructions at once is so important that dedicated hardware – the branch predictor – is present in all modern CPUs to make an educated guess on which way we’ll go at every conditional jump. The details of how this works are beyond the scope of this blog post, but conceptually your CPU observes your program as it runs and tries to predict which branch will be taken by remembering what happened in the past.

Even without knowing much about the branch prediction, we expect the predictor to do a great job for our test case – we always go back to the beginning of the loop apart from when we stop consuming the list. On Linux, we can verify that this is the case with perf stat:

$ perf stat ./value-speculation-linux
...
         2,507,580      branch-misses             #    0.04% of all branches

The branch predictor gets it right 99.96% of the time. So the CPU can parallelize our instructions with abandon, right? …right?

To increment value (rax), we need to know the value of node (rdi), which depends on the mov in the previous iteration of the loop. The same is true for the mov itself – it is also dependent on the result of the previous mov to operate. So there’s a data dependency between each iteration of the loop: we must have finished reading node->next ([rdi + 8]) at iteration n before we can start executing the add and mov at iteration n+1.

Moreover, reading the node->next ([rdi + 8]) is slower than you might think.

16kB, 10000 iterations
  sum1:  8465052097154389858,  1.12us,  14.25GB/s,  3.91 cycles/elem,  1.03 instrs/cycle,  3.48GHz,  4.01 instrs/elem
128kB, 10000 iterations
  sum1:  6947699366156898439,  9.06us,  14.13GB/s,  3.95 cycles/elem,  1.01 instrs/cycle,  3.49GHz,  4.00 instrs/elem
5000kB, 100 iterations
  sum1:  2134986631019855758,  0.36ms,  14.07GB/s,  3.96 cycles/elem,  1.01 instrs/cycle,  3.48GHz,  4.00 instrs/elem
4294MB, 1 iterations
  sum1: 15446485409674718527,  0.43 s,   9.94GB/s,  5.60 cycles/elem,  0.71 instrs/cycle,  3.48GHz,  4.00 instrs/elem

The important numbers are cycles/elem and instrs/cycle. We spend roughly 4 cycles per list element (that is to say, per loop iteration), corresponding to a throughput of roughly 1 instruction per cycle. Given that the CPU in question is designed for a throughput of 4 instructions per cycle, we’re wasting a lot of the CPU magic at our disposal, because we’re stuck waiting on the L1 cache.

This looks quite bizarre. We are still reading node->next in the comparison node != next to make sure our guess is right. So at first glance this might not seem like an improvement.

This is where the branch predictor comes in. In the case of lists where most nodes are next to each other (as is the case in our test code), the branch predictor will guess that the if (node != next) { ... } branch is not taken, and therefore we’ll go through loop iterations without having to wait for the L1 read.

Note that when the branch predictor is wrong (for example when the list ends, or if we have non-contiguous nodes) the CPU will need to backtrack and re-run from the failed branch prediction, which is costly (15 to 20 cycles on our processor). However, if the list is mostly contiguous, the trick works and makes our function 50-200% faster.

However there is one last challenge remaining to reach the final code and show you numbers – convincing compilers that our code is worth compiling.

Both gcc and clang easily deduce that the guessing is semantically pointless, and compile our trick away, making the compiled version of faster_sum the same as sum1. This is an instance where the compiler smartness undoes human knowledge about the underlying platform we’re compiling for.

Per Vognsen’s gist uses the following trick to get compilers to behave – this is the first improvement to our sum1, sum2:

However gcc still doesn’t fully fall for it, as explained in the comment. Moreover, clang’s generated loop is not as tight as it could, taking 10 instructions per element. So I resorted to manually writing out a better loop, which we’ll call sum3:

The code relies on the fact that node can’t be NULL after we increment it if it is equal to next, avoiding an additional test, and taking only 5 instructions per element (from loop_body to je loop_body in the happy path).