JavaScript: native forEach vs native forEach

Question

I noticed that native forEach sometimes occurs to be too slowly even for small arrays. Look at this example:

var a = [], b = []; 
a[1234567] = 'foo'; 
b[10] = 'bar'; 

a.forEach(function(arg1, arg2) { console.log(arg1, arg2); }); //1
//vs 
b.forEach(function(arg1, arg2) { console.log(arg1, arg2); }); //2

In my Chromium (25.0.1364.160 Ubuntu 12.04) execution times of line 1 and line 2 are different order of magnitude. I know than lenght of a is equal to 1234568, and for b it is equal just to 10. But does native forEach implementation is such naive? Both a and b are consist of only one element. How this behavior could be explained?

Answer 1

That is because a's length is actually 1234568, so you have to loop over 1234568 elements because how else can you be sure the elements aren't there?

var a = []
a[1234567] = 'foo'
console.log(a.length) // 1234568

So, it is looping over 1234566 of nothing and 1 'foo', vs array b which is only looping over 9 "nothing"s and a 'bar'.

When foreach tries to read a[0], it realizes it's not there, because a has nothing at index 0. Therefore, foreach thinks like this:

I'm going to see what a[0] is!
Oh no! It's not there!
I'm going to see what a[1] is!
Oh no! It's not there!
I'm going to see what a[2] is!
Oh no! It's not there!
...
I'm going to see what a[1234567] is!
Yaaaaay! I found it! Now I'll print it!

That's why it takes so much longer.

Answer 2

forEach iterates over the full length of the array, skipping non-existent elements on the way. Although a and b only contain one element, their length is big so you're giving forEach a hard time iterating.

After all, it's in the specification! An excerpt of ES5 15.4.4.18 Array.prototype.forEach:

6) Let k be 0.

7) Repeat, while k < len

To demonstrate this, let's see how Firefox's SpiderMonkey implements these steps:

/* Steps 6-7. */
/* Steps a (implicit), and d. */
for (var k = 0; k < len; k++) {
    /* Step b */
    if (k in O) {
        /* Step c. */
        callFunction(callbackfn, T, O[k], k, O);
    }
}

You can clearly see the loop of k from 0 to len which lies at the base of your performance troubles. For almost all k, k in O yields false but you still feel the impact of a million iterations and a million k in O tests.

For reference, here are the links to the SpiderMonkey and V8 implementations at the time of writing.

Answer 3

But [is] the native forEach implementation [so] naive? Both a and b [consist] of only one element. How [could] this behavior […] be explained?

It is specified so in the ECMAScript Language Specification, 5.1 Edition, §15.4.4.18:

When the forEach method is called with one or two arguments, the following steps are taken:

1. Let O be the result of calling ToObject passing the this value as the argument.
2. Let lenValue be the result of calling the [[Get]] internal method of O with the argument "length".
3. Let len be ToUint32(lenValue).
4. If IsCallable(callbackfn) is false, throw a TypeError exception.
5. If thisArg was supplied, let T be thisArg; else let T be undefined.
6. Let k be 0.

7. Repeat, while k < len

   a. Let Pk be ToString(k).

   b. Let kPresent be the result of calling the [[HasProperty]] internal method of O with argument Pk.

   c. If kPresent is true, then

   i. Let kValue be the result of calling the [[Get]] internal method of O with argument Pk.

   ii. Call the [[Call]] internal method of callbackfn with T as the this value and argument list containing kValue, k, and O.

   d. Increase k by 1.

8. Return undefined.

Steps 6 and 7 require a conforming implementation to iterate through all indexes, from the first index 0 to the last one, a.length - 1, regardless whether there is an array element with that index. Which explains why the forEach method call takes so long if the last index is a large number.

However, because in step 7b (the implementation of) the [[HasProperty]] internal method must return false for indexes for which there is no array element, the callback callbackfn is not called for those indexes. Which explains why there is only one console.log call when executing the forEach method call.