Build and measure
This loop nest adds up every number in a grid g of N × N ints. Swap the two for lines and the sum is exactly the same. Yet on a big grid one order runs much faster. This lesson shows why.
GCC and Clang do not optimise unless you ask: -O0 is the default. Build with -O2 and the compiler keeps values in registers and removes needless work, as long as the result stays the same. Only time optimised builds.
Before you change anything, measure. Time the work with std::chrono::steady_clock, or let a profiler such as perf show where the time goes. Usually a few hot loops take most of it, so fix those first.
Memory and the cache
A std::vector keeps its elements side by side in memory. The grid is stored row by row: row 0, then row 1, and so on. So g[r * N + c] is row r, column c, and its right-hand neighbour is the next int.
The cache is a small, fast memory next to the CPU. When a value is not there (a miss), the CPU copies a whole cache line from main memory: 64 bytes on most x86-64 chips, 16 ints. Here a line holds 4.
With r outside, the loop reads g[0], g[1], g[2], g[3]: one miss brings the line, then three hits. The whole grid costs 4 misses for 16 reads, because every line is used fully before it leaves.
Swap the loops and it reads g[0], g[4], g[8], g[12]: every read lands in a different line. This cache holds only 2 lines, so each is thrown out before it is used again. 16 reads, 16 misses.
Making it fast
A hit in the nearest cache takes a few CPU cycles. A miss that goes all the way to main memory can take a hundred or more. On a real grid much bigger than the cache, column order keeps the CPU waiting.
So walk data in the order it is stored, and prefer contiguous containers like std::vector for hot loops: std::list nodes can sit anywhere. Then measure again, and keep a change only if the numbers say it helped.
What happens
;; step 1/9 · same-sum 1 for (int r = 0; r < N; ++r) 2 for (int c = 0; c < N; ++c) 3 sum += g[r * N + c]; g a std::vector<int> of N * N numbers r the row, c the column swap lines 1 and 2: same sum, different speed
The figure's cache is a toy: 2 lines of 4 ints, throwing out the least recently used line. Real caches hold hundreds of 64-byte lines in several levels (L1, L2, L3), but a real grid is also far bigger: for N = 4096 one column touches 4096 lines (256 KiB), more than an L1 data cache holds. Cache lines are 64 bytes on current Intel and AMD x86-64 chips; some Arm chips, such as Apple's M-series, use 128 bytes. C++17's std::hardware_destructive_interference_size gives the compiler's hint for your target.