Loop Unrolling and Tiling

In this lesson, you will learn how to manually reorganize loop execution to maximize cache residency and minimize instruction overhead.

Loop Unrolling

Modern CPUs are pipelined machines that struggle when loop iterations are too short, as the branch predictor and increment logic introduce overhead. Unrolling expands the loop body to process multiple elements per iteration.

// Standard loop
for i in 0..n { sum += data[i]; }

// Unrolled (processing 4 elements at once)
let mut i = 0;
while i < n - 3 {
    sum += data[i] + data[i+1] + data[i+2] + data[i+3];
    i += 4;
}
// Handle remainder...

By reducing the number of jumps and increments, we increase the ratio of "work" to "bookkeeping," effectively keeping the CPU pipeline saturated.

Loop Tiling (Blocking)

While unrolling helps with instructions, tiling addresses the limitations of your CPU cache hierarchy. If you iterate over a large matrix, by the time you reach the end of a row, the beginning may have been evicted from the L1 or L2 cache. Tiling breaks a large dataset into smaller "blocks" (or tiles) that fit entirely within the cache.

Consider a matrix multiplication where we access memory in blocks:

const BLOCK_SIZE: usize = 32;

for i in (0..n).step_by(BLOCK_SIZE) {
    for j in (0..n).step_by(BLOCK_SIZE) {
        // Process only this small sub-grid (tile)
        for ii in i..i + BLOCK_SIZE {
            for jj in j..j + BLOCK_SIZE {
                result[ii][jj] = compute(matrix_a[ii], matrix_b[jj]);
            }
        }
    }
}

By constraining the working set to BLOCK_SIZE, you ensure that the data remains in high-speed cache throughout the computation. Instead of repeatedly pulling data from the slower main memory (RAM), the CPU performs its operations on the "warm" data already inside the cache hierarchy. When selecting your BLOCK_SIZE, always aim for a size that accounts for your architecture’s specific L1/L2 cache capacity to avoid thrashing.

Key Takeaway: Loop unrolling reduces instruction-level overhead, while tiling transforms your memory access patterns to ensure your data stays resident in the cache, preventing the high cost of main memory latency.