Memory Hierarchy and Cache Memory

TL;DR

Computers use a memory hierarchy to balance speed, cost, and size, with faster, smaller, more expensive memory closer to the CPU. Cache memory acts as a small, very fast buffer for frequently accessed data, significantly speeding up program execution. Understanding how caches work is crucial for writing efficient code.

1. The Mental Model

Think of memory as storage for your CPU. The faster the storage, the closer it is to the CPU. The further away, the slower but bigger and cheaper it gets. Cache memory is like your CPU's super-fast scratchpad, holding what it thinks it'll need next.

2. The Core Material

Your computer's memory isn't just one big block. It's organized into a hierarchy based on speed and cost. At the top, closest to the CPU, you have the fastest, most expensive, and smallest memory. As you go down, memory gets slower, cheaper, and larger.

Here's a common hierarchy, from fastest to slowest:

1. CPU Registers: Tiny, super-fast storage directly inside the CPU, holding data the CPU is actively working on.
2. Cache Memory (L1, L2, L3): Small, very fast memory layers that store copies of data from main memory that the CPU is likely to need soon.
   • L1 Cache: Smallest and fastest, often split into instruction cache and data cache, built directly into the CPU core.
   • L2 Cache: Larger and a bit slower than L1, typically shared by multiple cores or located on the CPU chip.
   • L3 Cache: Largest and slowest of the caches, shared across all CPU cores.
3. Main Memory (RAM): The primary working memory for your computer. Much larger than cache but significantly slower.
4. Secondary Storage (SSD/HDD): Persistent storage, much slower than RAM, used for long-term data like your operating system and files.

The goal of this hierarchy is to minimize the "memory wall" – the performance gap between fast CPUs and slower memory. When the CPU needs data, it first checks the fastest memory (L1 cache). If it's there, that's a cache hit, and the data is accessed very quickly. If not, it checks L2, then L3. If it's still not found, that's a cache miss, and the CPU has to go to slower main memory. When data is fetched from slower memory, it's typically brought into the faster cache layers as well, in anticipation of future use.

How Cache Memory Works

Photo by William Warby on Pexels

Caches exploit two key principles of memory access:

• Temporal Locality: If a piece of data is accessed now, it's likely to be accessed again soon. (e.g., loop variables)
• Spatial Locality: If a piece of data is accessed now, data near it in memory is likely to be accessed soon. (e.g., elements in an array)

When a cache miss occurs and data is fetched from main memory, it's not just a single byte that's brought into the cache. Instead, an entire block (or cache line) of data surrounding the requested byte is brought in. This anticipates future requests based on spatial locality.

Caches are organized into sets, and each set can hold multiple cache lines. The way a specific main memory address maps to a cache set is determined by the cache's mapping policy:

• Direct Mapped: Each main memory block can only go into one specific cache location. Simple but can lead to frequent conflicts if two frequently used blocks map to the same location.
• Fully Associative: A main memory block can go into any cache location. Very flexible but expensive and complex to implement.
• Set Associative: A compromise. Each main memory block can go into any location within a specific set of cache lines. This is the most common approach (e.g., 2-way, 4-way, 8-way set associative).

graph TD
    CPU[CPU] --> L1Cache[L1 Cache (fastest)]
    L1Cache -- Cache Hit --> CPU
    L1Cache -- Cache Miss --> L2Cache[L2 Cache]
    L2Cache -- Cache Hit --> L1Cache
    L2Cache -- Cache Miss --> L3Cache[L3 Cache]
    L3Cache -- Cache Hit --> L2Cache
    L3Cache -- Cache Miss --> MainMemory[Main Memory (RAM)]
    MainMemory -- Data fetched --> L3Cache
    MainMemory -- Data fetched --> L2Cache
    MainMemory -- Data fetched --> L1Cache
    MainMemory -- Cache Miss --> SecondaryStorage[Secondary Storage (SSD/HDD)]
    SecondaryStorage -- Data fetched --> MainMemory

When a cache line needs to be replaced (because a new line needs to come in and the set is full), a replacement policy is used. Common policies include:

• LRU (Least Recently Used): Evicts the cache line that hasn't been used for the longest time.
• FIFO (First-In, First-Out): Evicts the cache line that has been in the cache the longest.
• Random: Evicts a random cache line.

Writing Cache-Friendly Code

Photo by Mathews Jumba on Pexels

You can influence cache performance by writing code that exhibits good temporal and spatial locality:

• Process data in contiguous blocks: When iterating through arrays, access elements in order (e.g., array[0], array[1], array[2]). This benefits from spatial locality.
• Reuse data: If you're going to use a variable or piece of data multiple times, try to do so within a short time frame to benefit from temporal locality.
• Avoid large strides: Jumping far ahead in memory (e.g., array[0], array[1000], array[2000]) can lead to more cache misses.
• Understand matrix order: In C/C++, matrices are stored in row-major order. Accessing matrix[i][j] then matrix[i][j+1] is cache-friendly. Accessing matrix[i][j] then matrix[i+1][j] is not, as it jumps to a new row, potentially missing spatial locality benefits.

3. Worked Example

Let's consider a simple scenario of iterating through a 2D array (matrix) in C. Assume a cache line size of 64 bytes and ints are 4 bytes. This means a cache line can hold 16 integers (64 / 4).

Consider a 100x100 integer matrix A.

Scenario 1: Row-major traversal (Cache-friendly)

// int A[100][100];
// Initialize A with some values

long long sum = 0;
for (int i = 0; i < 100; i++) {
    for (int j = 0; j < 100; j++) {
        sum += A[i][j]; // Accesses A[i][0], A[i][1], ..., A[i][99]
    }
}

When A[i][0] is accessed, an entire cache line containing A[i][0] through A[i][15] (assuming contiguous memory and a 16-int cache line) is brought into cache. The subsequent accesses to A[i][1], A[i][2], etc., will be cache hits until A[i][16] is requested, causing a new cache line to be fetched. This makes good use of spatial locality.

Scenario 2: Column-major traversal (Cache-unfriendly)

// int A[100][100];
// Initialize A with some values

long long sum = 0;
for (int j = 0; j < 100; j++) {
    for (int i = 0; i < 100; i++) {
        sum += A[i][j]; // Accesses A[0][j], A[1][j], ..., A[99][j]
    }
}

When A[0][j] is accessed, a cache line containing A[0][j] and its neighbours A[0][j+1] to A[0][j+15] is brought in. However, the next access is A[1][j], which is in a completely different row and very likely not in the current cache line. This will likely result in a cache miss for almost every access, significantly slowing down the operation.

4. Key Takeaways

• Memory hierarchy balances speed, cost, and size, with faster memory closer to the CPU.
• Cache memory (L1, L2, L3) is a small, fast buffer that stores frequently used data from main memory.
• Cache hits are fast; cache misses require fetching data from slower memory.
• Caches exploit temporal locality (reuse data soon) and spatial locality (data near current data is needed soon).
• Data is moved into cache in fixed-size "cache lines" when a miss occurs.
• Cache performance depends on mapping policies (direct, set associative, fully associative) and replacement policies (LRU, FIFO).
• You can optimize code by ensuring data access patterns utilize spatial and temporal locality.
• Iterating through arrays in their stored order (e.g., row-major for C/C++ arrays) is crucial for cache efficiency.

5. Now Try It

Choose a small C/C++ program that performs matrix multiplication (e.g., two 100x100 matrices). Implement two versions: one that iterates through the matrices in a cache-friendly way (row-major for inner loops) and another that deliberately iterates in a cache-unfriendly way (column-major for inner loops where it harms locality). Compile both versions with optimizations disabled (-O0) to prevent the compiler from fixing your mistakes, and measure their execution times. You should see a significant performance difference. Success looks like observing a noticeably faster execution time for the cache-friendly version, demonstrating the practical impact of memory hierarchy and cache awareness.