CPU Cache

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.

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. This entry used to end by saying a column walk gets no reuse under any associativity because there is nothing to reuse, and that is wrong: columns 0 to 7 of one row share a single line, so the neighbouring columns WILL want the bytes already fetched. What stops them here is that the stride maps too many of those lines onto the same slots and the direct-mapped cache evicts them before the walk comes back. That is a conflict miss, not an absence of reuse, and a sufficiently associative cache of this size keeps the lines and closes most of the gap. Direct-mapped caches are not extinct either; they are unusual as the main cache of a high-performance processor and ordinary in simpler and specialised parts.

There is no L1, L2 and L3 here, no prefetcher, no write buffer and no store queue. A modern 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.

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.

This page used to say the layout was “what C, Python and JavaScript all do”, and that was an overclaim an outside reader caught. A C multidimensional array really is contiguous and row-major. A Python list of lists is an array of pointers to separate objects, and Python’s own buffer protocol distinguishes C-contiguous from Fortran-contiguous precisely because neither is assumed. ECMAScript specifies arrays as objects with indexed properties and promises nothing about their arrangement in memory; a typed array is contiguous, an ordinary one need not be. The machine models a row-major array of doubles because that is the layout the effect depends on, and saying which layout is the honest version of saying which languages.