1965-1990s

CPU Cache

Wilkes called it a slave memory in 1965; the word cache arrives with the IBM System/360 Model 85 three years later. Everybody has been told that walking an array down its columns is slower than walking along its rows. The arithmetic underneath that is three lines long and almost nobody is shown it, so here it is with the knobs left on: a read does not fetch a value, it fetches a line, and how much of that line you use before throwing it away is the entire difference. Nothing here is timed. Every number is counted.

Two loops over the same array, in a different order

1 Every element, row by row

An array of doubles, laid out row by row, which is what C, Python and JavaScript all do. Walking along a row walks straight through memory.

The array: 64 by 64 (4,096 elements, 32 KiB)

The first eight reads walking along a row: which element, its byte address, which line it falls in, and whether it hit
element	address	line	outcome
[0][0]	0	line 0	miss
[0][1]	8	line 0	hit
[0][2]	16	line 0	hit
[0][3]	24	line 0	hit
[0][4]	32	line 0	hit
[0][5]	40	line 0	hit
[0][6]	48	line 0	hit
[0][7]	56	line 0	hit

2 The same elements, column by column

The same array and the same elements, taken down the columns instead. Consecutive elements of a column are a whole row apart in memory.

The first eight reads walking down a column: which element, its byte address, which line it falls in, and whether it hit
element	address	line	outcome
[0][0]	0	line 0	miss
[1][0]	512	line 8	miss
[2][0]	1,024	line 16	miss
[3][0]	1,536	line 24	miss
[4][0]	2,048	line 32	miss
[5][0]	2,560	line 40	miss
[6][0]	3,072	line 48	miss
[7][0]	3,584	line 56	miss

the stride: 512 bytes between one element of a column and the next, against a line of 64

That stride is at least a whole line, so every read down a column lands in a line nothing else will use.

3 The line, which is what a read actually fetches

A read fetches a whole line. Make the line longer and each miss brings back more of the row you are about to want; it does nothing at all for the column.

The line: 64 bytes, which is 8 elements

The cache: 8 KiB

does the array fit in the cache: no, the array is 4.0 times the size of the cache

4 Why the second one costs an order of magnitude more

elements read: 4,096 either way
misses, row by row: 512
misses, column by column: 4,096
the difference: 8.0 times as many

Same 4,096 elements, same addresses, different order, 3,584 more misses. A read does not fetch a value, it fetches 8 of them, and walking down a column throws away 7 of every 8.

the simulation and the arithmetic agree: 512 and 4,096

What this page checked when it loaded.

Each claim, whether it held, and the values behind it
claim	held	measured
both walks read exactly the same number of elements	yes	4096 reads each
the simulated row-major misses match the arithmetic	yes	512 simulated, 512 predicted
and so do the column-major misses	yes	4096 simulated, 4096 predicted
one miss per line along a row, not one per element	yes	8 elements to a line
the column walk misses several times more often	yes	512 against 4096

What is real here, and what is not

Nothing on this page is timed, and that is deliberate

There is no clock here. Every number is a count of simulated misses, exact and derived from the access pattern. Timing anything from JavaScript in a browser would measure the engine, the garbage collector, the operating system and whatever else is running, and would produce a number that changes on every reload. The one thing this page therefore does NOT demonstrate is the step from misses to wall-clock time; it shows the mechanism and asks you to take the last inch on trust.

The cache is direct mapped, which no modern cache is

A block goes in exactly one slot, chosen by a division you can do in your head. Real caches are set associative — typically eight ways — which changes the eviction behaviour and rescues some patterns this simulation punishes. It does not change what the page is about: a column walk with a stride of a whole line gets no reuse under any associativity, because there is nothing to reuse.

One level, where a real machine has three

There is no L1, L2 and L3 here, no prefetcher, no write buffer and no store queue. A real processor would also spot a constant stride and start fetching ahead of the loop, which recovers a good deal of what the column walk loses. That prefetcher is the reason the measured penalty on a modern machine is often smaller than the miss counts here suggest, and it is fair to say the page overstates the gap for that reason.

The array fitting in the cache is the case usually left out

Shrink the array below the cache size and the two orders cost exactly the same, because every line is fetched once whichever way you walk. That is not a quirk of this model: it is why a benchmark on a small array shows nothing, and why the demonstration in a textbook always uses an array chosen to be too large. The knobs are here so you can watch the effect turn off.

Sources

Logical Art builds interactive explanations of difficult machines.

The machines:

1935-1991 RangekeeperThe answer is on both sides of the equation, so it had to be a machine.
1964-1990s AbendThe loop you did not write, and the day it cost to get it wrong.
1975 Front PanelA working 1975 Altair 8800 you program by flipping switches.
1980s 300 BaudA real dial-up modem and the BBS on the other end of it.
1994 WinsockThe two seconds after the modem stopped screeching, before anything worked.
2020s LLM LabTrain a tiny language model and watch every number as it learns.

Smaller pieces, on the studio itself: Morse, Baudot, Punch Cards, Interlace, Bitwise, Stored Program, Trigger, Bit, Nibble, Byte, Transistor, Hamming, Huffman, Core Memory, The Interrupt, Score Reel, CRC, Page Fault, ASCII, CPU Cache, Race, Fifteen Planes, B-tree, Backoff, Checkout, Diffie-Hellman, Fringes, LZ77, Zero Address, Signature, Z-Characters, Merkle Proof, Branch Prediction, Interleave, Eight Sprites, DNS, Floating Point, Slow Start, UTF-8, Masking, PageRank, Merge Collapse, Count Distinct.

A Logical Art machine by RoamingPigs, Inc. Built by Cisco Caceres in Las Vegas, NV.