Tuning Software for Cache Locality

In this lesson, you will learn how to refactor your code and data layouts to ensure the CPU finds data in the cache rather than waiting on slow main memory.

Understanding Cache Locality

We know from our study of cache hierarchies that memory access is fastest when the data requested is already in the cache. When our software fails to keep data in the cache, we trigger a "cache miss," forcing the CPU to stall while it fetches data from higher-latency main memory. Tuning software for cache locality means organizing our code and data to exploit Spatial Locality (using data near recently accessed data) and Temporal Locality (reusing the same data frequently).

Array Access Patterns

In C/C++, multi-dimensional arrays are stored in row-major order. If we iterate through an array in a way that jumps across memory rows, we force the cache to constantly evict and reload lines.

Compare these two loops:

// Bad: Strided access
for (int col = 0; col < 100; col++) {
    for (int row = 0; row < 100; row++) {
        sum += matrix[row][col]; 
    }
}

// Good: Contiguous access
for (int row = 0; row < 100; row++) {
    for (int col = 0; col < 100; col++) {
        sum += matrix[row][col];
    }
}

In the "Bad" example, every access jumps to a different memory row, likely causing a cache miss every time. In the "Good" example, we access memory sequentially. Because the cache loads data in "blocks" (or lines), the first access pulls the entire row into the cache, making the subsequent col iterations effectively free because the data is already waiting in the cache.

Struct Packing

Similarly, if you have a struct with fields you rarely use together, you increase the chance that the cache will be polluted with unused data. By grouping frequently accessed variables together in your data structures, you ensure that when one field is loaded into a cache line, its neighbors are also loaded, maximizing your "hit" rate. In performance-critical embedded systems, keeping your "hot" data structures small enough to fit within the cache size is the ultimate goal.

Key Takeaway: Align your data access patterns to match memory layout and group frequently used data together to maximize the efficiency of each cache line loaded.