The same loops, swapped
Here are two ways to add up every number in a large grid.
// Version A
for (int row = 0; row < N; row++)
for (int col = 0; col < N; col++)
sum += grid[row][col];// Version B
for (int col = 0; col < N; col++)
for (int row = 0; row < N; row++)
sum += grid[row][col];They visit exactly the same cells and do exactly the same additions. The only difference is which loop is on the outside. By every rule of Big-O, they are identical.
On a large grid, Version B can be several times slower.
The reason has nothing to do with the code, and everything to do with where the numbers physically live.
Memory is far away
A processor works in fractions of a nanosecond. Fetching a value from main memory takes roughly a hundred times longer than doing arithmetic on it. If the processor fetched each value from memory as it needed it, it would spend nearly all its time waiting.
So it keeps a small, very fast store of recently used memory right next to it: the cache.
Two facts about the cache explain everything on this page.
It fetches memory in chunks, not single values
When the processor needs one value, it brings in that value and its neighbours: a block called a cache line, usually 64 bytes. That is 8 or 16 numbers at once.
It is small
When it is full, loading a new line means throwing an old one out.
The bet is that if you just used a value, you will probably want the one next to it soon. When that bet is right, the next several reads cost almost nothing.
How a grid sits in memory
Memory is one long line of slots. A two-dimensional grid has to be laid out along it somehow. C, Java, and NumPy by default do it row by row: all of row 0, then all of row 1, and so on.
So grid[0][0] and grid[0][1] are neighbours in memory. grid[0][0] and grid[1][0] are a whole row apart.
Watch the cache
In this small model, each row is one cache line, and the cache holds two lines.
Start. A 6 × 8 grid, stored row after row in memory. Reading one value from memory brings its whole row (one cache line) into the cache. The cache holds 2 lines.
- Values read
- 0 / 48
- Already in cache
- 0
- Slow fetches
- 0
Row by row moves through memory in a straight line. The first read of a row is slow and brings in the whole row. The next seven reads are already there. One slow fetch in eight.
Column by column jumps a full row ahead on every single step. Each read lands on a line that is not in the cache. By the time the loop comes back to a row, that row was thrown out long ago. Every read is a slow fetch.
Same cells, same sums. One order rides the cache and the other fights it.
The general lesson: locality
Code that uses memory close to what it just used is said to have good locality. It is one of the biggest influences on real-world speed, and Big-O does not see it at all.
- Arrays beat linked lists for walking. An array's items are side by side, so one fetch brings in several. A linked list's nodes can be scattered anywhere, so each step may be a fresh fetch. Both walks are O(n), and the array can be many times faster.
- Loop in the order the data is stored. For a row-by-row grid, the row loop goes on the outside.
- Keep related data together. Fields that are used together should sit together.
- Smaller is faster. Data that takes less room means more of it fits in the cache.
Example
Check your own language
The layout is a property of the language or library, not a law. C, C++, Java and NumPy store rows together, so iterate rows on the outside. Fortran, MATLAB and Julia store columns together, so there the fast order is the opposite.
When to care
Not for a 10 × 10 grid, and not for code that runs once. Care when you are looping over a lot of data in a tight loop: image and video processing, numerical work, game engines, databases. There, getting the order right can be the cheapest large speed-up available, because it changes nothing about what the code computes.
Key takeaways
- Fetching from main memory is very slow compared with computing, so processors keep a small fast cache.
- Memory is loaded in lines of neighbouring values, so reading one value makes its neighbours nearly free.
- A grid stored row by row is fast to walk row by row and slow to walk column by column.
- Both orders have the same Big-O. The difference is locality: using memory near what you just used.
- It matters for large data in tight loops, and it is why arrays usually outrun linked lists.