You write two loops that add up the same grid of numbers. One goes across each row, the other goes down each column. Both add exactly the same numbers, yet on a big grid one of them can take around ten times longer. Nothing in the maths explains that. The explanation is a small, fast piece of memory inside your processor called a cache.

Memory is slow, and the processor knows it

Your program's data lives in RAM (the computer's main memory). The CPU, the chip that runs your instructions, can do an addition in a fraction of a nanosecond, but fetching a value from RAM takes far longer. If the CPU waited for RAM on every single read, it would spend most of its life doing nothing.

So the CPU keeps a small helper memory right next to it, the cache. It is much faster than RAM but much smaller. When the CPU asks for a value, it checks the cache first. If the value is there, that is a hit and the answer comes back quickly. If not, that is a miss: the CPU has to go to RAM.

The cache fetches neighbours too

Here is the key trick. On a miss, the cache does not copy just the one value you asked for. It copies a whole block of neighbouring memory, called a cache line. A line is commonly 64 bytes on current x86 processors (some chips use 128), and 64 bytes is 16 ints of 4 bytes each. The bet is that if you read one item, you will probably read the next one soon.

A 2D grid is stored in memory as one long strip, one row after another (this is called row-major order, and C, C++, Rust, and NumPy by default all do it). So the items in a row sit side by side, and the items in a column are a whole row apart.

Watch it happen

Below is a tiny model: a grid of 64 numbers, a cache line of 8 neighbouring items, and a cache that can hold a few lines at once. When it is full, it throws out the line used least recently. Pick how to walk the grid and press Step. Orange is a miss (a trip to RAM), green is a hit.

Row by row Column by column

Cache holds 2 lines

Step Run all Reset

hits 0

misses 0

step 0/64

Press Step to read the first item.

Try row by row first: you get 8 misses and 56 hits, because every miss loads a line that the next 7 reads use. Now switch to column by column with a cache of 2 lines. Every read lands in a different line, and by the time you come back to a line it has already been thrown out, so all 64 reads miss. Then drag the slider up to 8 lines and run the column walk again: the first column misses 8 times, but after that every line is already in the cache and the other 56 reads hit. The access pattern and the cache size together decide the result.

The same thing in real code

This C program sums a 4096 by 4096 grid of ints (about 64 MB, far bigger than any cache) in both orders. It is compiled with gcc -O1, a light optimisation level, so the compiler does not quietly swap the loops for you.

for (int r = 0; r < N; r++)
    for (int c = 0; c < N; c++)
        s += a[r * N + c];      // row by row

for (int c = 0; c < N; c++)
    for (int r = 0; r < N; r++)
        s2 += a[r * N + c];     // column by column

On the cloud machine this was tested on, one run printed:

sums 16777216 16777216
row by row:       0.011 s
column by column: 0.127 s

Both loops produce the same sum. The column walk was about 11 times slower, purely because of the order of memory reads. Your numbers will differ with your processor, but the direction will not.

What this means for your own code

You do not need to think about caches every day. But a few habits are worth knowing:

Walk memory in the order it is stored. For a grid stored row by row, make the inner loop go along a row. Languages differ: Fortran and MATLAB store columns together, so there the rule flips.

Contiguous beats scattered. A plain array of numbers is friendly to the cache. A structure that hops between many separate objects through pointers (a linked list, say) often is not, because each hop can be a miss.

Measure before you worry. In a language like Python, each list item is a pointer to a separate object, and the interpreter does much more work per step, so this effect is usually hidden. Reach for it when you work with big arrays of numbers, for example with NumPy, or when profiling shows a hot loop.

Recap

A cache is a small, fast memory that keeps recently used data close to the CPU. It loads neighbours along with the item you asked for, so reading things that sit next to each other is fast, and jumping around is slow. Same numbers, same sum, very different speed.