Memory Hierarchy
Scanning the 2D C array a[i][j] with j in the inner loop, as above, tends to be faster than with i in the inner loop. Why?
for (i = 0; i < N; i++)
for (j = 0; j < N; j++)
sum += a[i][j];- AThe array is stored row-major, so consecutive addresses are read in order and each cache line is fully used
- BThe compiler removes the additions inside the loop altogether and skips the computation entirely at run time
- CWith j inside, the TLB is never consulted, so translating virtual addresses to physical addresses is no longer needed
Show answer and explanation
Answer: A. The array is stored row-major, so consecutive addresses are read in order and each cache line is fully used
C stores 2D arrays in row-major order, so a[i][0], a[i][1] and so on are adjacent in memory. With j in the inner loop, consecutive addresses are read in order, so the rest of each 64-byte cache line fetched on a miss is used right away. With i inside, accesses jump a whole row apart, and lines tend to be evicted after only a small part has been used. The TLB is still used, and address translation is not eliminated.
- A. Correct. Reading consecutive addresses uses the whole of each fetched line.
- B. The addition is not skipped; both orders perform the same computation.
- C. The TLB is still used and addresses are still translated.