Cache

Learn CPU cache effects and data locality.

Cache

The cache is a small fast memory between the CPU and main memory. Data is loaded in cache line blocks (usually 64 bytes). Access to neighboring data in the same block is fast.

That is why spatial locality matters: sequential access to an array is cache-friendly; random-index access forces a new cache line load each time. Cache misses are expensive; they cost hundreds of cycles. Keeping data sequential improves performance significantly.

Locality kinds

There are two locality kinds: spatial locality — access to neighboring addresses, and temporal locality — re-access to recently used data. Both increase the cache hit rate.

Sequential array access gives spatial locality. Keeping a frequently used variable in a loop gives temporal locality. Keeping the structure small and compact (struct of arrays) is cache-friendly; more related data fits in one cache line.

Exercise Sum an array sequentially

In main define int data[4] = {1, 2, 3, 4}; and int sum = 0;. Write the loop for (int i = 0; i < 4; ++i) sum += data[i];. Then write std::cout << sum;.

Show example solution

#include <iostream>

int main() {
    int data[4] = {1, 2, 3, 4};
    int sum = 0;
    for (int i = 0; i < 4; ++i) sum += data[i];
    std::cout << sum;
    return 0;
}

Test yourself

Complete the loop bound

for (int i = 0; i < ____; ++i) sum += data[i];

Show answer

for (int i = 0; i < size; ++i) sum += data[i];

Which access pattern is cache-friendly?
```
int data[100];
for (int i = 0; i < 100; ++i) sum += data[i];
```
- Random-index access
- Sequential-index access
- Only even-index access
- Strided access
Show answer

Sequential-index access — Sequential access gives spatial locality; the cache line is loaded once.
Match each concept to its role

cache line

64-byte block
spatial locality

Neighbor data access
temporal locality

Repeated access
cache miss

Load from memory

Next lesson: Vectorization

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies