Loop Reordering

constexpr int ROWS = 1000, COLS = 1000; std::vector<std::vector<int>> matrix( ROWS, std::vector<int>(COLS, 1)); for (int i = 0; i < ROWS; ++i) for (int j = 0; j < COLS; ++j) sum += matrix[i][j];

constexpr int ROWS = 1000, COLS = 1000; std::vector<std::vector<int>> matrix( ROWS, std::vector<int>(COLS, 1)); for (int j = 0; j < COLS; ++j) for (int i = 0; i < ROWS; ++i) sum += matrix[i][j];

C/C++ stores 2D arrays in row-major order: matrix[i][j] and matrix[i][j+1] are adjacent in memory. Row-major traversal accesses memory sequentially, making full use of each cache line and enabling hardware prefetching.

Column-major traversal jumps between rows on each access, causing a cache miss for every element when the matrix is large enough. Each access loads a full cache line (64 bytes) but only uses 4 bytes of it before moving to a different cache line.

This is one of the most impactful optimizations in numerical computing. The fix is simple: swap the loop order so the inner loop iterates over the contiguous dimension.

References: