English is currently available.
Computer Engineering DISCUSSION
I sum a 4096 × 4096 array of 4-byte integers in C, declared as int a[4096][4096]. With the row index in the outer loop the sum takes a fraction of the time it takes with the column index in the outer loop. Both versions perform the same 16.7 million additions.
I know the answer is supposed to be the cache, but I would like to understand the mechanism. What exactly is a cache line, and why does the order of two loops change how well it works?
C stores a 2D array in row-major order: all of row 0, then all of row 1, and so on, in one contiguous block of 64 MiB in your case. The cache does not fetch single integers from memory; it fetches fixed-size blocks called cache lines, 64 bytes on most current processors, which hold 16 of your integers.
Going along a row, the first access to a line misses and the next 15 are hits, and the hardware prefetcher recognises the sequential pattern and fetches upcoming lines before you ask. Going down a column, consecutive accesses are 4096 × 4 = 16,384 bytes apart, so every single access lands on a different line. You fetch 64 bytes and use 4 of them.
Two further effects pile on in the column order. First, the stride is a power of two. A typical 32 KiB, 8-way first-level cache has 64 sets, selected by address bits 6 to 11. A stride of 16,384 bytes leaves those bits unchanged, so every element of a column maps to the same set, which can hold only 8 lines. The column evicts itself continuously.
Second, 16,384 bytes is four 4 KiB pages, so every access is on a new page. The first-level TLB holds only some tens of page translations, so the column walk also misses the TLB constantly and adds page-table lookups to the cache misses.
The cost difference per access is what turns this into a large factor. A first-level cache hit takes about 4 or 5 cycles and is largely hidden by the pipeline. A load that has to come from main memory takes on the order of 100 ns, a few hundred cycles. The row-order loop pays that at most once per 16 elements, and usually not even then thanks to prefetching; the column-order loop can pay a miss at some cache level on every element.
The array size matters as well. If the whole array fitted in the first-level cache, say 64 × 64 integers at 16 KiB, both orders would run at nearly the same speed.
The fix is to make the inner loop run along memory: for (i...) for (j...) sum += a[i][j];. Compilers can sometimes interchange loops themselves, but do not rely on it. For algorithms that need both directions, such as matrix multiplication or a transpose, process the data in blocks small enough to stay in cache, a technique called loop blocking or tiling.
Remember that the fast order depends on the language. Fortran, MATLAB and Julia store arrays column-major, so there the first index should vary fastest. NumPy uses C order by default but can hold either.
The same 64-byte granularity explains two other common performance effects. An array of large structures of which the loop uses one field wastes most of each line; splitting hot fields into their own array (structure of arrays) packs more useful data per line.
With threads, two variables that share a line cause false sharing: each write by one core invalidates the line in the other core's cache even though the variables are unrelated. Aligning per-thread data to 64 bytes, for example with alignas(64), removes it. On Linux, perf stat -e cache-misses or Valgrind's cachegrind tool lets you confirm which case you have.
