Students should understand the importance of the memory hierarchy, including how caches use temporal and spatial locality to tremendously speed up memory accesses. Otherwise, a student would not know there is any difference between:
for (int i = 0; i < 1000000; i++) {
for (int j = 0; j < 1000000; j++) {
arr[i] += j;
}
}
and the logically equivalent reordered code:
for (int j = 0; j < 1000000; j++) {
for (int i = 0; i < 1000000; i++) {
arr[i] += j;
}
}
The difference is that, in the first piece of code, each array element is retrieved from memory once and placed in either a register or the cache, from which it is operated on a million times. Ignoring spatial locality (which would apply equally to both versions), the total number of reads from memory would be 1,000,000, and the total number of writes would be 1,000,000.
With the second version of code, each array element is fetched from memory once for each value of j
. The total number of reads from memory would be 1,000,000 x 1,000,000 (10^12); the total number of writes would be the same.
Per Latency Numbers Every Programmer Should Know, a main memory access takes about 100 ns; an L1-cache reference takes .5 ns. Accessing a register adds no time to instruction execution.
Ignoring the times for the writes (which may not be in the critical path) and spatial locality (which applies the same to both versions) and assuming that a[i]
is stored in a register, the data memory access time for the first is 10^6 * 100 ns = .1 s. The data memory access time for the second is 10^12 * 100 ns = 10^5 s.