Cache Performance: Spatial and Temporal Locality

The Principle of Locality

Caches work because programs don't access memory randomly. Instead, they exhibit a property called the principle of locality. This principle has two main facets.

To start, let's get a clear and concise definition of these concepts.

Let's formalize those definitions:

1. Temporal Locality (Locality in Time): The tendency to reuse a specific piece of data within a short time frame. If a memory location is accessed, it's highly likely to be accessed again soon.

   • How caches exploit this: By storing recently accessed data, caches ensure that subsequent accesses become fast hits instead of slow misses. A loop variable or a running sum are great examples.

2. Spatial Locality (Locality in Space): The tendency to access data at memory locations near other recently accessed locations. If a memory location is accessed, it's highly likely that nearby addresses will be accessed soon.

   • How caches exploit this: Memory is not fetched byte-by-byte. Instead, it's loaded into the cache in fixed-size blocks called cache lines (typically 64 bytes). When you have a miss and request one byte, the hardware gives you the entire 64-byte line it belongs to, pre-loading adjacent data for free.

Locality in Action: The Matrix Traversal Example

Understanding locality is one thing, but seeing its impact is what makes the concept stick. Let's look at a classic example that reveals the dramatic performance implications of writing cache-friendly code.

Consider traversing a 2D matrix stored in row-major order, which is the default for C++.

// Row-major layout: elements of a row are contiguous in memory
int matrix[ROWS][COLS];

// Traversal 1: Row-major access
for (int i = 0; i < ROWS; ++i) {
    for (int j = 0; j < COLS; ++j) {
        sum += matrix[i][j]; // Accessing matrix[i][0], matrix[i][1], ...
    }
}

// Traversal 2: Column-major access
for (int j = 0; j < COLS; ++j) {
    for (int i = 0; i < ROWS; ++i) {
        sum += matrix[i][j]; // Accessing matrix[0][j], matrix[1][j], ...
    }
}

Both loops perform the exact same number of additions and access the same memory locations, just in a different order. Intuitively, their performance should be similar. The reality is starkly different.

As the video makes clear:

• Row-major traversal exhibits excellent spatial locality. When matrix[i][0] is accessed, a cache miss may occur, but the hardware loads a cache line containing matrix[i][0], matrix[i][1], matrix[i][2], etc. The subsequent loop iterations find the data already in the cache, resulting in fast hits. This is a linear, predictable access pattern that hardware loves.
• Column-major traversal exhibits poor spatial locality. Accessing matrix[0][j] and then matrix[1][j] involves jumping across memory by an entire row's worth of bytes (the stride). If the stride is larger than a cache line, every access could result in a new cache miss, fetching a 64-byte line only to use a single integer from it.

This difference between a stride-1 access (row-major) and a large-stride access (column-major) is one of the most important patterns to recognize when analyzing code for cache performance.

A Framework for Analysis: Types of Cache Misses

When analyzing performance, it's useful to categorize why a miss occurred. This helps you reason about potential solutions.

Let's summarize the key categories:

• Compulsory (or Cold) Miss: The very first access to a block of data. These are unavoidable; the data has to be loaded into the cache at least once. Prefetching can help hide the latency, but the miss itself will happen.
• Capacity Miss: The cache cannot contain all the data needed by the program. A block was loaded, then evicted because the cache was full, and is now needed again. This happens when the program's "working set" (the data it's actively using) is larger than the cache.
• Conflict Miss: The miss occurs because too many active data blocks map to the same cache set (or line in a direct-mapped cache), causing them to evict each other. This can happen even when the cache is not full. This is the type of miss that increasing associativity, as we discussed in the last lesson, is designed to reduce.

The other two misses mentioned, True and False sharing, are related to multi-core systems and will become critical when we discuss parallel programming in a later module.

Hands-On Analysis

Now it's time to apply these concepts. Let's analyze a few code snippets. For each one, consider the memory access pattern and try to predict:

1. What type(s) of locality does it exhibit?
2. What kind of cache misses are likely to dominate?

We'll use the exercises from the Cache Memories, Cache Complexity PDF you just looked at. Assume sizeof(int) is 4 bytes and a cache line is 64 bytes. This means one cache line can hold 64 / 4 = 16 integers.

Exercise 1: Sequential Access

#define S (1 << 20) // 1,048,576
int A[S];

for (int i = 0; i < S; i++) {
    read A[i]; 
}

• Your Analysis: How does this loop access memory? What kind of locality does it have? What will the hit/miss pattern look like?

Exercise 2: Repeated Access

#define S (1 << 20)
int A[S];

for (int i = 0; i < S; i++) {
    read A[0]; 
}

• Your Analysis: What's the access pattern here? What locality does it show?

Exercise 3: Strided Access

This one is trickier. What if the stride is not 1?

#define S (1 << 20)
#define N 14 // Assume 14 <= N
int A[1 << N];

for (int i = 0; i < S; i++) {
    // Note the stride of 16 integers (64 bytes)
    read A[(i * 16) % (1 << N)];
}

• Your Analysis: The loop accesses elements A[0], A[16], A[32], etc. Each step jumps 16 integers, which is exactly 64 bytes. What does this mean for spatial locality?

Conclusion

In this lesson, we bridged the gap between cache hardware and program behavior. You now have the conceptual tools to look at a piece of code and reason about its performance in the memory hierarchy.

Key Takeaways:

• Temporal Locality: Reusing the same data soon. Caches exploit this by keeping recent data around.
• Spatial Locality: Accessing nearby data soon. Caches exploit this by fetching data in blocks called cache lines.
• Stride matters: A stride of 1 (sequential access) is ideal for spatial locality. Large strides that jump across cache lines are inefficient.
• The performance difference between a cache-friendly (row-major) and cache-unfriendly (column-major) matrix traversal can be an order of magnitude or more.
• Cache misses can be categorized as Compulsory, Capacity, or Conflict, which helps in diagnosing performance issues.

Preview of the Next Lesson

We have learned to qualitatively analyze code for cache hits and misses. In our next lesson, we will move to quantitative analysis. We will learn how to calculate cache performance metrics: hit rate, miss penalty, and average memory access time (AMAT). This will allow us to put concrete numbers on the performance impact of the access patterns we analyzed today.