Quantum Physics Of Java

Question

Today i came across a fascinating slide here. It compares two for loops given below.

First

for (int i=0; i<n; i++) {
    a[i] * = 3;
}

Second

for (int i=0; i<n; i+=16) {
    a[i] * = 3;
}

Here if the first loop will take 8ms the second should be taking only 1ms, at least that's what I expected. But the slide concludes differently. Can anyone please explain why my code may behave like this?

Answer 1

This blog post explains the phenomenon in details. Essentially:

• the first loop does 6x more work than the second
• but they run in the same amount of time (roughly)

The reason is that the first loop has better cache locality, resulting in less cache misses. There are many questions on the subject on SO such as:

• What is "cache-friendly" code?
• Spacial Locality in loops