Why can changing loop order make code 86x faster?

Because the access pattern decides cache behavior: row-major (sequential) access stays in cache, column-major access thrashes it — an enormous speed difference.

* Walking a 2D array along rows follows how C and Java lay it out in memory, so it hits cache; striding down columns thrashes it. *

Original code (slow):

for (i=0; i<N; i++) {
    for (j=0; j<N; j++) {
        // Column-major access
        sum[j][i] = A[j][i] + B[j][i];
    }
}
// Average runtime: 1,716,543,444

Optimized code (fast):

for (j=0; j<N; j++) {
    for (i=0; i<N; i++) {
        // Row-major access
        sum[j][i] = A[j][i] + B[j][i];
    }
}
// Average runtime: 19,948,247

Speedup: 86x faster!

Why: Arrays are stored row-by-row in memory. Accessing by rows keeps data in cache (spatial locality). Accessing by columns jumps around memory, causing cache misses.

Tip: In C/Java, arrays are row-major. Always iterate with the rightmost index changing fastest: arr[i][j] where j is the inner loop.

Go deeper:

• Loop interchange (Wikipedia) — reordering nested loops to match array layout so accesses walk memory sequentially and hit cache.
• Row- and column-major order (Wikipedia) — why C's row-major storage makes inner-loop order decisive for cache behaviour.