Complexity of David

Data Science, Machine Learning, Artificial Intelligence, Visualization, and Complex Systems.

Why Is the for Loop Faster in This Javascript?

I’ve measured and tested and what not javascript loops and always came to the conclusion that we don’t know how Javascript is going to behave.

In the following example function f1 is substantially faster than function f2. Can’t understand why.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
function tic() {
the_time = performance.now()
}

function toc() {
console.log(performance.now() - the_time)
}

function f1(z) {
let len = z;
let buff = []
for (let i = 0; i < len; i++) {
buff[i] = i;
}
return buff;
}

function f2(z) {
let len = z;
let buff = []
while (len--) {
buff[len] = len;
}
return buff
}
tic(); f1(2 << 20); toc();
tic(); f2(2 << 20); toc();

Your Results:

Normally I would say that the reversed while would be faster. It has been in other instances. But in this case we want to create an array with numbers from 0 to z-1. In this case the for loop is much faster (tested in Chrome, Firefox, Opera). What is going on? Is it a caches problem where JS engines expect the “straight” order and not the reverse one?

update

What if we pre-allocate the size of the buffer before iterating over it as in function f2. This would lead to the new function f2_new

1
2
3
4
5
6
7
8
9
function f2_new(z) {
var len = z;
var buff = [];
buff.length=len;
while (len--) {
buff[len] = len;
}
return buff;
}

Notice that I’m creating a buffer with the correct length before looping over it. If you run this version you’ll get the fastest while loop.

This version is now on par with the for loop and in some benchmarks it is substantially faster. So, order restored in the realm of Javascript. Me happy again.