Same Big O, Different Speed: The Impact of CPU Cache Locality

We often use Big O notation to reason about algorithm efficiency.

But here's something interesting: Two implementations of the exact same O(n³) algorithm can have drastically different execution times.

The reason? Memory access patterns.

Let's look at matrix multiplication.

The two implementations

Both implementations perform the same matrix multiplication:

[
C[i][j] += A[i][k] \times B[k][j]
]

They perform the same asymptotic amount of work. The only difference is the order of the loops.

1. Column-wise access

// Walk down columns of B
for (int i = 0; i < n; ++i)
    for (int j = 0; j < n; ++j)
        for (int k = 0; k < n; ++k)
            C[i][j] += A[i][k] * B[k][j];

Notice B[k][j].

As k increments, we move down a column of B.

In C++, 2D arrays are typically stored in row-major order. This means elements of the same row are stored contiguously in memory.

Accessing a column therefore means jumping across memory with a stride of n * sizeof(int).

This leads to poor cache locality.

1. Row-wise access

// Walk along rows of B
for (int i = 0; i < n; ++i)
    for (int k = 0; k < n; ++k)
        for (int j = 0; j < n; ++j)
            C[i][j] += A[i][k] * B[k][j];

Now notice B[k][j].

As j increments, we move across a row of B, accessing contiguous memory locations.

This is much more cache-friendly.

Why does this make such a big difference?

This is where CPU caches come into play.

Modern CPUs have multiple levels of cache:

L1 → L2 → L3 → Main Memory (RAM)

L1 is the smallest and fastest. RAM is much slower.

When the CPU accesses memory, it fetches data in blocks called cache lines, typically 64 bytes on modern x86 CPUs.

Assuming 4-byte integers, one cache line can hold 16 consecutive integers.

Consider what happens in each implementation:

Column-wise access:

The CPU accesses B[0][0], then B[1][0], then B[2][0].

Each access jumps to another row, potentially loading a new cache line.

We may use only one integer from each fetched cache line.

Much of the fetched data goes unused, resulting in poor spatial locality and more cache misses.

Row-wise access:

The CPU accesses B[0][0], B[0][1], B[0][2], and so on.

One 64-byte cache-line fetch can provide multiple consecutive integers.

Those values are accessed while they are still in cache.

This makes much better use of each cache-line fetch.

There's another benefit: A[i][k] remains constant while the inner loop runs, so the same value is reused across multiple calculations.

The takeaway

Both implementations are O(n³).

Neither reduces the number of multiplication or addition operations.

The difference is how efficiently they use the hardware.

The speedup comes from better memory access patterns, not from reducing the operation count.

Big O tells us how an algorithm scales as input grows. It doesn't tell us how efficiently that algorithm interacts with the CPU cache, memory hierarchy, or actual hardware.

That's why understanding cache locality matters when writing performance-critical code.

Sometimes, optimizing an algorithm isn't about doing less work. It's about making the hardware do the same work more efficiently.