cpu-cache
Why does the order of the loops affect performance when iterating over a 2D array?
As others have said, the issue is the store to the memory location in the array: x[i][j]. Here’s a bit of insight why: You have a 2-dimensional array, but memory in the computer is inherently 1-dimensional. So while you imagine your array like this: 0,0 | 0,1 | 0,2 | 0,3 —-+—–+—–+—- 1,0 | 1,1 … Read more
What is a “cache-friendly” code?
Preliminaries On modern computers, only the lowest level memory structures (the registers) can move data around in single clock cycles. However, registers are very expensive and most computer cores have less than a few dozen registers. At the other end of the memory spectrum (DRAM), the memory is very cheap (i.e. literally millions of times … Read more