성능과 튜닝 JavaScript Array.push Performance

I was recently reading Google’s JavaScript Style Guide when I came across the following claim:

“Note that since assigning values to an array is faster than using push() you should use assignment where possible.”

I had always used push to assign a value to the end of an array, so thought I’d investigate this a little bit further to determine the performance of each of the methods. There are 3 distinct ways to do this:

1. Array.push(element) ? Defined on the native Array object, this is the method challenged by Google.

2. array[i] = element ? Assigning an element to a specific index of the array. The requirement of this method is that you must have a pointer to the last location. Other than that it’s a simple assignment.

3. array[array.length] = element ? Similar to the previous, but this involves a lookup for situations where you don’t have access to a pointer.

4. I also defined a fourth function to test. I put a function on the Array prototype called mypush, which carried out step 3 above. It was defined as such:

     Array.prototype.mypush = function(element) {
       this[this.length] = element;
     };

This short article will document my testing of these different methods on several browsers.

The Tests

I put together a small HTML page to execute the different methods of adding an element to the end of an array alongside some method of timing how long each took.

The tests consisted of adding 400,000 elements to an empty Array using the different methods described above. I performed the test 10 times for each method, and took the average. For example, here’s a look at the test for Array.push:

  function testPush() {
    var result = 0;
    var a = [];
 
    for (var i = 0; i<10; i++) { // run the test 10 times
      a = []; // we start with an empty array each time
      var start = new Date().getTime(); // get the start time of the test
 
      for (var j = 0; j<400000; j++) {
        a.push(i);
      }
 
      var end = new Date().getTime();
      result += end - start;  // and the result is the end time minus the start time
    }
 
    alert('Result for Array.push is ' + (result / 10)); // take the average
  }

I then repeated the same logic for the other methods.

The Results

The tests yielded the following results in the following browsers:

Conclusion

The results speak for themselves: using an index outperforms using Push in every browser with the exception of Google’s own. If cross-compatibility is a big concern for you, the utilitarian approach would be to use an index wherever possible.

To look at the situation a little deeper, we could consider steps the Closure Compiler takes to handle these situations. If we run the following code in the Compiler:

var a = [];
 
function push(i) {
  a.push(i);
}
 
for(var i = 0; i<10; i++) {
  a.push(i);
}

We observe the following output:

  for(var a=[],b=0;b<10;b++)a.push(b);

Showing that the Compiler doesn’t do anything about push statements in pre-compiled code. However, with an improved performance in most browsers, you might expect it to.

However, it wouldn’t be as simple as converting all pushes to index assignments as there is a subtle difference between the two; Array.push returns the length of the array after the element has been added (something you don’t get with array[array.length]). Converting all Array.push statements would cause semantic problems if the user has assigned that statement to a variable. For example:

var a = [];
var b = [];
 
var i = a.push('test'); // i is 1
 
var j = b[b.length] = 'test'; // j is 'test'

However, we could examine the case where the result of Array.push is not assigned to anything. In this scenario, the Compiler should be able to replace the push with an array.length index without side effects.

The problem then lies in the fact that the performance varies between browser. Although, on the whole, indexing performs better than push, that is not the case in Google Chrome. Unlike GWT, where you can deploy a certain condition for a certain browser, Closure Compiler just generates one JavaScript file for every browser.

Given the differences between Chrome’s results, and the extremely poor performance in some other browsers, it may be worth sacrificing some performance in Chrome for much better performance in other browsers.

This entry was posted on Friday, October 15th, 2010 and is filed under Blog.

You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site .

6 Responses to “JavaScript Array.push Performance”

1. Drew says:

   Very interesting results ? what is up with Firefox taking 7 times longer to use your my push method??

   I’m always a little skeptical about Google’s programming tips, they did a YouTube video a while back stating that using ‘ instead of ” in PHP would make a big difference to performance! Sort of reminds me of; http://www.codinghorror.com/blog/2009/01/the-sad-tragedy-of-micro-optimization-theater.html

   Reply
2. Johnny Cardy says:

   Hi Steven, it looks like V8′s Array.push function uses “this[this.length] = x;”. Given that, how can it be so fast? Any clues?

   Reply
   • Steven Hall says:

     Hi Johnny,

     I’ve taken a look at the source for the Push method on the V8 engine and it looks to do something slightly different to

     this[this.length] = x;

     The source shows that they’re indexing to a non-existent index, and then updating the length.

     One thing to note is Chrome was so fast (or the test case was so insignificant in comparison to the power of its JavaScript engine), that the numbers between certain tests varied to the point where one would outperform the other in certain cases. Although the average yielded the above results, there was only a slight different in performance between the 4. I think another interesting test would be to increase the number of elements added and to compare the different methods in Chrome.

     Reply
3. Mark Rhodes says:

   I guess it would be bad form to actually use this in practice? I guess you’d always just use the standard function and hope that at some point in the future they’ll get round to making it faster!

   Just wondering though ? I’m not sure if the scripting engine does something similar underneath but, if this was any other programming language with real arrays rather than “hacked on” ones, then you probably want to increase it’s size by more than 1 each time you pushed a new element on. I don’t think this makes sense in Javascript but might look something like:

   Array.prototype.size = 0;
   Array.prototype.myPush = function(value) {
       var arrayToReturn = this; 
       if(this.size == this.length){   
           arrayToReturn = this.concat(new Array(Math.max(10, this.size)));
           arrayToReturn.size = this.size;
       }
       arrayToReturn[arrayToReturn.size] = value;
       arrayToReturn.size++;
       return arrayToReturn;
   };
   //then to use it..
   var array = [];
   array = array.myPush(1);

   Too bad that you’d need to set the array to be the returned result unlike the real push method, but I don’t think this can be helped. If there is some magic going on which makes “new Array(10)” faster than just setting each element individually than it might make sense. Don’t suppose you know if this is the case?

   Disclaimer ? by the way I’m not suggesting anyone would actually use the above code! It’s pretty ugly and anything which relies on the length of the array would break e.g. array.pop().

   Reply
   • Steven Hall says:

     Yes. Despite Google’s advice, the Array insert function they have defined in the Closure Library still uses Array.push [source].

     Like you said, I’m not sure that increasing an array by a constant value on each push makes sense in JavaScript, mainly because it’s not consistent with the language specification. The following example could cause some confusion and is generally inconsistent with JavaScript arrays:

       var a = [];
       a.myPush(1) // this code has no side effects if you don't assign it back to a. a hasn't changed
       a = a.myPush(1) // length is now 11, but the array is [1]

     You now have to introduce a size property to keep track of how many elements are in the Array, which doesn’t fit the specification.

     To answer your question about improving new Array().. I would stick to using array literals. You wouldn’t need to use the Array constructor as it’s generally considered to be more bloated than the literal notation (the extra overhead incurred with finding the constructor etc.). You could just increase the length of arrayToReturn by 10.

       var a = [];
       a.length = a.length + 10;
       // a.length = 10
      
       a = [];
       a = a.concat(new Array(10));
       // a.length = 10

     Reply