-1

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?

RBz
  • 896
  • 3
  • 17
  • 34
  • This may be an interesting experiment but the two loops don't do the same thing so you can't really compare them... – assylias Nov 04 '15 at 09:22
  • 3
    Comparing the speed of two pieces of code which **do different things** is wrong, thus you get downvotes. – Manu Nov 04 '15 at 09:26
  • 1
    Actually the slide says that both run in the same time (when you may expect the first one to be 16x slower). – assylias Nov 04 '15 at 09:26
  • @RBz as explained by Eran, the second loop does less work so you would expect it to run in less time - you say the first loop takes 8ms vs 1ms for the second so there is nothing surprising in there. But the presentation you linked says that both loops run in the same time. So I'm not sure what slide you are referring to but your question does not seem to match the presentation which is confusing... – assylias Nov 04 '15 at 09:33
  • 1
    @RBz http://igoro.com/archive/gallery-of-processor-cache-effects/ – assylias Nov 04 '15 at 09:51

1 Answers1

2

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:

Community
  • 1
  • 1
assylias
  • 321,522
  • 82
  • 660
  • 783