Optimizing Loops for Cache and Performance

Loop Interchange: Optimizing for Cache Locality

In the module on memory hierarchy, we established that main memory (RAM) is slow, and CPUs rely on small, fast caches to hide this latency. We also learned about spatial locality: the principle that if a program accesses a memory location, it's likely to access nearby locations soon. To exploit this, CPUs fetch data from RAM in chunks called cache lines (typically 64 bytes).

The key to good performance is to access memory in a way that makes full use of each cache line fetched. For C++ code, this means remembering one crucial fact: multi-dimensional arrays are stored in row-major order.

This image shows a 2D array and how it's flattened into linear memory. In row-major order, used by C/C++, all elements of a row are contiguous. Accessing A[0][0], A[0][1], A[0][2]... is a sequential memory access (stride of 1), which is ideal for the cache.

When a loop accesses memory with a large, non-unit stride, it "jumps" through memory, fetching a new cache line for each access and using only one element from it. This is incredibly inefficient. Loop interchange is the technique of reordering nested loops to ensure the innermost loop iterates with a stride of 1, maximizing cache line utilization.

A Classic Example: Matrix Multiplication

Matrix multiplication is the canonical example for demonstrating loop interchange. Consider the following naive implementation: C = A * B.

// Naive i-j-k loop order
for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
        for (int k = 0; k < N; k++) {
            // C[i][j] += A[i][k] * B[k][j];
        }
    }
}

Let's analyze the access pattern in the innermost loop (the k loop):

• C[i][j]: Constant within the k loop. Excellent locality.
• A[i][k]: k is the fastest-changing index, and it's in the last dimension. This access is sequential (row-major). Excellent spatial locality.
• B[k][j]: k is the fastest-changing index, but it's in the first dimension. Each increment of k jumps N elements forward in memory. This is a non-unit stride access. Terrible spatial locality.

To fix this, we can interchange the j and k loops.

// Optimized i-k-j loop order
for (int i = 0; i < N; i++) {
    for (int k = 0; k < N; k++) {
        for (int j = 0; j < N; j++) {
            // C[i][j] += A[i][k] * B[k][j];
        }
    }
}

Now let's analyze the new innermost loop (the j loop):

• A[i][k]: Constant within the j loop. Excellent locality.
• C[i][j]: j is the fastest-changing index, and it's in the last dimension. Sequential access. Excellent.
• B[k][j]: j is the fastest-changing index, and it's in the last dimension. Sequential access. Excellent.

By simply swapping the order of two loops, we've transformed one of our memory accesses from cache-hostile to cache-friendly. The performance impact can be dramatic.

To reinforce this concept with more data and a slightly different perspective, the following article provides a written explanation and includes performance stats from the perf tool, which clearly shows the reduction in cache misses.

Loop Unrolling: Optimizing for Instruction Scheduling

While loop interchange optimizes for the memory system, loop unrolling primarily optimizes for the CPU's pipeline.

As we've learned, modern CPUs can execute multiple instructions at once (instruction-level parallelism), but they are often limited by data dependencies and loop control logic. A typical loop has a very small body, which doesn't give the instruction scheduler much to work with.

Loop unrolling involves replicating the body of the loop and adjusting the loop control variables accordingly.

The main benefits of loop unrolling are:

1. Increased Instruction-Level Parallelism (ILP): A larger loop body contains more instructions. If these instructions are independent of one another (e.g., they operate on different data), the CPU's scheduler can issue them in parallel to different execution units, hiding latencies and increasing throughput.
2. Reduced Loop Overhead: Fewer iterations mean fewer increment/decrement instructions, fewer conditional tests, and fewer branches. This not only saves instructions but also reduces the potential for branch mispredictions.

The video below explains this concept in detail, going down to the assembly level to show how unrolling helps resolve pipeline stalls.

As the video highlighted, loop unrolling is not a free lunch. The main drawbacks are:

• Increased Code Size: A larger binary can lead to more instruction cache misses if the loop body becomes too large.
• Increased Register Pressure: The unrolled loop needs more registers to hold the intermediate values of the multiple operations happening in parallel. If the CPU runs out of registers, it has to "spill" them to the stack (memory), which can negate the performance gains.

Choosing the right unrolling factor is a balancing act, and modern compilers are often quite good at performing this optimization automatically. However, manual unrolling can be beneficial in performance-critical code where you have specific knowledge about the hardware target.

Synthesis: Combining Interchange and Unrolling

Loop interchange and loop unrolling are not mutually exclusive. A very common and effective optimization strategy is to first use loop interchange to improve cache locality, and then use loop unrolling on the new, cache-friendly innermost loop to improve instruction throughput.

Let's return to our i-k-j matrix multiplication. The innermost loop is now:

// Innermost loop of the i-k-j version
for (int j = 0; j < N; j++) {
    r[i][j] = r[i][j] + a[i][k] * b[k][j]; 
}

We can unroll this j loop by a factor of 4:

// Innermost j-loop, unrolled by 4
for (int j = 0; j < N; j+=4) {
    r[i][j+0] = r[i][j+0] + a[i][k] * b[k][j+0];
    r[i][j+1] = r[i][j+1] + a[i][k] * b[k][j+1];
    r[i][j+2] = r[i][j+2] + a[i][k] * b[k][j+2];
    r[i][j+3] = r[i][j+3] + a[i][k] * b[k][j+3];
}

In this unrolled version, a[i][k] can be loaded into a register once and reused four times. The four r[i][j+...] updates are independent of each other and can be aggressively scheduled by the CPU. This combines the benefits of both techniques.

The following resource provides a summary of these techniques and their benefits.

Conclusion

In this lesson, we moved from theory to practice, learning two fundamental loop optimization techniques that make your code work with the hardware, not against it.

Key Takeaways:

• Loop Interchange reorders nested loops to make the innermost loop access memory sequentially (unit stride). This maximizes spatial locality and dramatically improves cache hit rates. It primarily targets the memory system.
• Loop Unrolling expands the body of a loop to reduce overhead and, more importantly, to increase the number of independent instructions available. This allows the CPU's instruction scheduler to better exploit Instruction-Level Parallelism (ILP). It primarily targets the CPU's pipeline and execution units.
• A powerful strategy is to combine these techniques: first, use interchange to get the memory access right, then use unrolling on the new inner loop to improve pipeline throughput.
• Both techniques have trade-offs. Unrolling increases code size and register pressure, so the unroll factor must be chosen carefully.

Preview of the Next Lesson

We have now learned how to optimize for a single level of the cache. But modern systems have a deep memory hierarchy (L1, L2, L3 caches). What if our data is too large to fit in L1, but fits in L2? Simple loop interchange and unrolling might not be enough. In our next lesson, we will tackle this problem by learning about loop tiling (or blocking), an advanced technique that optimizes for multiple levels of the memory hierarchy at once.