JavaScript: native forEach vs native forEach

Question

I noticed that native forEach sometimes happens too slowly even for small arrays. Take a 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), the runtimes of lines 1 and 2 differ in order of magnitude. I know that the length of a is 1234568, and for b it is only 10. But does native forEach make the implementation so naive? Both a and b consist of only one element. How can this behavior be explained?

Answer 1

This is because the length a is actually 1234568, so you need to iterate over 1234568 elements, because how else can you be sure that the elements are not there?

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

Thus, it loops on 1234566 from nothing and 1 'foo' , vs array b , which only loops on 9 'nothing' and 'bar' .

When foreach tries to read a[0] , it implements it in the wrong place, because a nothing at index 0 . Therefore foreach thinks this way:

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

That is why it takes a lot longer.

Answer 2

forEach iterates over the entire length of the array, skipping non-existent elements along the way. Although a and b contain only one element, their length large, so you give forEach complicated iteration time.

In the end, it's in the specification! Excerpt 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 SpiderMonkey implements the following 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 cycle k from 0 to len , which underlies your performance problems. For almost all k , k in O gives false , but you still feel the impact of a million iterations and millions of k in O tests.

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

Answer 3

But [is] the built-in forEach implementation is [so] naive? And a and b [consist] of only one element. How could this behavior be explained [...]?

It is specified 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 performed:

• Let O be the result of calling ToObject passing the this value as an argument.
• Let lenValue be the result of calling the [[Get]] O internal method with argument "length" .
• Let len ​​be ToUint32 ( lenValue ) .
• If IsCallable ( callbackfn ) false , throw a TypeError exception.
• If thisArg was provided, let T be Arg; otherwise let T be undefined .
• Let k be 0.

• Repeat while k <Len

  a. Let Pk ToString ( k ) .

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

  with. If kPresent is true , then

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

  II. Call the internal method callbackfn [[Call]] with T as this and an argument list containing the values ​​of kValue, k and O.

  e. Increase k by 1.

• Return undefined .

Steps 6 and 7 require a consistent implementation for iterating over all indices: from the first index 0 to the last, a.length - 1 , regardless of whether there is an array element with this index. This explains why calling the forEach method takes so long if the last index is a large number.

However, since in step 7b (implementation), the [[HasProperty]] internal method must return false for indexes for which there is no array element, callbackfn is not called for these indexes. This explains why there is only one console.log call when making a call to the forEach method.