Cache Performance and Data Access Patterns

1. The Principle of Locality

The entire premise of caching hinges on a predictable behavior of most programs known as the principle of locality. This principle isn't a strict law of physics, but a powerful empirical observation about how code tends to access memory. It has two main facets.

To begin, let's get formal definitions for these two concepts.

As you just read, we can break down locality into two types:

• Temporal Locality: If a program accesses a piece of data, it is very likely to access that same piece of data again soon. Think of a loop counter variable or the sum in an accumulation loop. Keeping this data in a fast cache avoids repeated trips to slow main memory.
• Spatial Locality: If a program accesses a piece of data, it is very likely to access data at nearby memory addresses soon. This is evident when iterating through an array or accessing the fields of a struct. Fetching an entire cache line at once anticipates these future requests.

2. Spatial Locality in Action: Structuring Data and Loops

Spatial locality is perhaps the more intuitive of the two principles to visualize. Because data is loaded in 64-byte cache lines, accessing memory sequentially is incredibly efficient. Let's see a dramatic example.

The result from the video is stark. When you access the vector's elements in order (v[0], v[1], v[2], ...), the first access to v[0] triggers a cache miss. The hardware fetches the 64-byte cache line containing v[0] through v[15] (assuming 4-byte integers). The next 15 reads are then lightning-fast cache hits. This pattern repeats, resulting in a very high cache hit rate.

In contrast, accessing elements randomly (v[9], v[54], v[1], ...) almost guarantees a cache miss on every single access. The hardware can't predict your next move, and the pre-fetched data in a cache line is useless. The program becomes bound by the latency of main memory.

Matrix Multiplication Loop Ordering

This same principle applies to multi-dimensional data, like the matrices that are central to AI workloads. As you know from your C/C++ experience, a 2D array is stored linearly in memory in row-major order. This means the second row directly follows the first row in memory.

Consider the standard three-loop matrix multiplication C = A * B. The order of these loops does not change the mathematical result, but it has a colossal impact on cache performance.

Let's revisit the mCoding video, which demonstrates this perfectly.

The key insight is to arrange the loops so that the innermost loop traverses memory contiguously. In the i, j, k ordering, the access to B[k][j] jumps by an entire row's worth of bytes on each iteration. This is terrible for spatial locality. By swapping the loops to i, k, j, the inner j loop walks across a row of C and a row of B sequentially, leading to a much higher cache hit rate and a significant performance boost.

Data Layout: Array-of-Structs (AoS) vs. Struct-of-Arrays (SoA)

Spatial locality also influences how you should design your data structures. This leads to a classic systems programming trade-off: Array-of-Structs vs. Struct-of-Arrays.

Imagine you have a particle simulation with one million particles, each with a position (x, y, z) and velocity (vx, vy, vz).

Array-of-Structs (AoS): This is the typical object-oriented approach.

struct Particle {
    float x, y, z;
    float vx, vy, vz;
};

Particle particles[1000000];

The memory layout is [p0.x, p0.y, p0.z, p0.vx, ...], [p1.x, p1.y, ...]. This is great if you frequently access all the data for a single particle at once.

Struct-of-Arrays (SoA): This approach flips the structure.

struct Particles {
    float x[1000000];
    float y[1000000];
    float z[1000000];
    float vx[1000000];
    float vy[1000000];
    float vz[1000000];
};

Particles particles;

The memory layout is [p0.x, p1.x, ...], [p0.y, p1.y, ...], .... This layout is far superior if your computation involves operating on only one field at a time across all particles. For example, an update step that only modifies the x position:

// In an SoA layout, this is a beautiful sequential scan
for (int i = 0; i < 1000000; ++i) {
    particles.x[i] += particles.vx[i] * dt; 
}

In this loop, the accesses to particles.x and particles.vx are both perfectly sequential. The CPU fetches a cache line of x positions and uses them all, then fetches the next. The same happens for vx. In an AoS layout, this same operation would "hop" over the y, z, vy, and vz fields for each particle, polluting the cache with useless data and drastically reducing the number of useful values per cache line.

3. Temporal Locality in Action: Reusing Data with Tiling

While spatial locality is about arranging data, temporal locality is about structuring algorithms to reuse data while it's still "hot" in the cache.

Let's return to matrix multiplication. Even with the optimal i, k, j loop order, if the matrices are too large to fit in the cache, we still have a problem. By the time we start processing the second row of A, the elements of B we used for the first row may have already been evicted from the cache. We lose the opportunity for reuse.

The solution is a powerful technique called tiling (or blocking). Instead of processing the entire matrices, we break them into smaller sub-matrices or "tiles" that are guaranteed to fit into the cache. We then perform all the necessary computations on a single set of tiles before moving to the next.

The logic is as follows:

1. Load an s x s tile from A and an s x s tile from B into the cache.
2. Perform s^3 multiplications and additions to fully compute the contribution of these tiles to the corresponding s x s tile of C.
3. Each element from the A and B tiles is now reused s times.
4. By choosing s such that 3 * s^2 (the space for three tiles) is smaller than the cache size M, we guarantee high temporal locality. The data is used intensely before being evicted.

This single technique improves the cache performance of matrix multiplication by a factor of $\sqrt{M}$, which can be thousands on a modern CPU. It is one of the most important optimizations in high-performance computing.

4. A Taxonomy of Cache Misses

We've seen how good access patterns lead to cache hits. But what happens when we have a miss? Not all misses are created equal. Understanding the type of miss is critical for diagnosing performance problems. Cache misses are typically categorized into the "3 Cs".

1. Compulsory (Cold) Miss: The very first time a memory location is accessed. The data is not in the cache, so it must be fetched. These are unavoidable.
2. Capacity Miss: The cache is not large enough to hold all the data required by the program's working set (the data it's actively using). The data was in the cache at some point but was evicted to make room for other data, and is now needed again. The tiling optimization we just saw is a direct strategy to reduce capacity misses by restructuring the algorithm to have a smaller working set at any given time.
3. Conflict Miss: This is the most subtle type. A conflict miss occurs when data is evicted because another piece of data maps to the same cache set, even though other parts of the cache are empty. This is a direct consequence of the cache's set-associative nature that we touched on in the last lesson.

Conflict misses can cause pathological performance issues if your data access stride aligns poorly with the cache geometry. Let's look at a classic, worst-case example.

This example is a powerful lesson. When the stride between consecutive memory accesses (in this case, the size of a row, 2^15 bytes) is a large power of two, it can happen that the low-order bits of the address used for the cache set index don't change. All your accesses "conflict" for the same few slots in the cache, causing constant evictions, even if the rest of the cache is empty. This is a prime example of how a deep understanding of hardware is essential for diagnosing certain performance bugs.

Conclusion

In this lesson, we have moved from the "what" of cache architecture to the "why" of cache performance. You have seen that writing fast code is not just about algorithmic complexity (Big-O notation), but about structuring data and computation to align with the hardware.

Key Takeaways:

• Principle of Locality: Caches work because programs exhibit spatial locality (accessing nearby data) and temporal locality (reusing the same data).
• Exploiting Spatial Locality:
  • Access memory sequentially (e.g., iterating through arrays).
  • Organize nested loops to make the innermost loop's access contiguous (e.g., matrix multiplication).
  • Choose the right data layout (AoS vs. SoA) based on your access patterns.
• Exploiting Temporal Locality:
  • Use techniques like tiling (blocking) to break large problems into smaller chunks that fit in the cache, allowing for intense data reuse.
• Cache Miss Types: Understanding whether a miss is compulsory, capacity, or conflict is key to diagnosing and fixing performance issues.

We have now established how to feed the CPU with data efficiently. The next question is, what does the CPU do to process that data faster? In the next lesson, we will shift our focus from memory to computation and explore Instruction-Level Parallelism (ILP), the collection of techniques modern CPUs use to execute multiple instructions simultaneously.