2

var t1 = new Date().getTime()
for (let i = 0; i < 100; i++) {
  for (let j = 0; j < 1000; j++) {
    for (let k = 0; k < 10000; k++) {
    }
  }
}
var t2 = new Date().getTime()
console.log('first time', t2 - t1)

for (let i = 0; i < 10000; i++) {
  for (let j = 0; j < 1000; j++) {
    for (let k = 0; k < 100; k++) {

    }
  }
}
var t3 = new Date().getTime()
console.log('second time', t3 - t2)

As you can see, it looks like the above two for-loops will have the same execution time. But in fact the second loop will take more time to execute than the first one does. What makes the difference under the hood?

deceze
  • 510,633
  • 85
  • 743
  • 889
James Lam
  • 145
  • 2
  • 8
  • Can you add some outputs from the code above? – schteppe Jul 06 '20 at 08:45
  • switching the order of the loops does not change the result for me, so i guess looping 1000 times inside a 100 times loop is more performant than looping 100 times inside a 1000 timesloop – john Smith Jul 06 '20 at 08:47
  • JavaScript implentations are free to optimize code before they run it. This is likely a difference in optimizations. But it is completely irrelevant as the code does not do anything anyway. If you do something in the inner-most loop, the processing time will likely be approximately the same. – str Jul 06 '20 at 08:49
  • @schteppe first time is 257 and the second time is 586 in my console. – James Lam Jul 06 '20 at 08:53

1 Answers1

5

In the first loop, you are executing:

  • let j=0; //100 times
  • let k=0; //100*1000=100000 times

In the second loop, you are executing:

  • let j=0; //10000 times
  • let k=0; //10000*1000=10000000 times

The second loop has 9909900 more variable initializations and therefore is expected to run longer.

Zaenille
  • 1,384
  • 9
  • 16
  • This is incorrect. 100*1000*10000 === 10000*1000*100. – str Jul 06 '20 at 08:53
  • @str You don't execute `let k=0;` for each run of the innermost loop. – Zaenille Jul 06 '20 at 08:55
  • @str The number of loops is the same, but the number of *variable initialisations* is not. – deceze Jul 06 '20 at 08:55
  • @Zaenille Ah, I mistunderstood what you are saying. But this is hardly making a real difference. For example, try adding a variable increment `count++` into both innermost loops and the execution time will be approximately the same. – str Jul 06 '20 at 08:57
  • @str Yes that is true, but that is not the question asked above. – Zaenille Jul 06 '20 at 08:59
  • It might not be the same scenario, but it still kinda refutes your answer (or at least shows that it is not generally applicable to nested loops). If the number of variable initializations has such a massive influence on the running time, then why doesn't it make a difference in the scenario with `count++`? My assumption is that the compilers optimize it differently and less aggressively as the loop does not do anything in the first place. – str Jul 06 '20 at 12:17
  • I found a sentence in MDN: _An expression (including assignment expressions) or variable declaration evaluated **once** before the loop begins_. FYI: [for statement](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Statements/for) – James Lam Jul 07 '20 at 02:17
  • @str My answer is that loop 2 has significantly more variable initializations than loop 1. I never claimed the number of variable initializations has a massive performance impact.If you put any action in the innermost loop, yes, the effect of the increased variable initializations is insignificant, **but you are still running them nonetheless**. – Zaenille Jul 07 '20 at 03:11