How CPU Cache and Locality of Reference Make Programs Faster

Modern CPUs are fast, but memory is still relatively slow. To speed things up, CPUs use a special type of memory called cache which is small, fast memory located close to the processor.

Get Ye Wint Naing’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

To make this cache useful, the CPU uses a principle called locality of reference. This explains why some code runs much faster than others, even if they do the same job.

What Is Locality of Reference?

Locality of reference means programs usually don’t access memory randomly. Instead, they:

• Reuse the same data again and again → this is called temporal locality.
• Use nearby memory locations together → this is called spatial locality.

The CPU detects these patterns and uses them to keep data in the cache instead of always going back to main memory (RAM).

Temporal vs Spatial Locality

• Temporal Locality
• If you use some data now, you’ll probably use it again soon. Example: A variable updated many times inside a loop.
• Spatial Locality If you use data at one memory location, you’ll probably use nearby data next. Example: Iterating through an array, element by element.

Both of these help the CPU avoid repeated, slow RAM accesses by keeping useful data in the cache.

A Simple Experiment

Let’s see this in action. Below is a C++ program you can run (works on macOS with CLion). It compares accessing the same element repeatedly (good temporal locality) versus accessing random elements (poor locality).

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <mach/mach_time.h>

#define SIZE 10000000

int main() {
    static int arr[SIZE];
    uint64_t start, end;
    uint64_t elapsed;

    // Fill array so it's allocated in memory
    for (int i = 0; i < SIZE; i++) arr[i] = i;

    volatile int x; // prevent compiler optimization

    // Cached repeated access
    start = mach_absolute_time();
    for (int i = 0; i < 1000000; i++) {
        x = arr[0]; // same index every time
    }
    end = mach_absolute_time();
    elapsed = end - start;
    printf("Cached repeated access: %llu ns\n", elapsed);

    // Random scattered access
    start = mach_absolute_time();
    for (int i = 0; i < 1000000; i++) {
        x = arr[rand() % SIZE]; // scattered across array
    }
    end = mach_absolute_time();
    elapsed = end - start;
    printf("Random scattered access: %llu ns\n", elapsed);

    return 0;
}

Output

Cached repeated access: 13050 ns
Random scattered access: 191516 ns

The second case is more than 10x slower, even though both loops have the same time complexity (O(n)). The difference comes from how memory is accessed

How the CPU Uses Cache

Here’s how the flow works

1. CPU tries to access data.
2. Cache checks if that data is already stored (cache hit).
3. If not, it fetches a block of memory (cache line) from RAM.
4. If the program accesses memory sequentially (e.g., arr[i]), the cache stays warm and performance is fast.

References

Here are some useful resources :

1. CPU Cache: What it is and how it works — Storedbits
2. Understanding Locality of Reference — Wikipedia
3. Cache Hierarchy — Wikipedia
4. Locality of Reference and Cache Operation in Cache Memory