5

I was wondering if there is a reason to choose 

array.push(element)

over 

array[array.length] = element

or vice-versa.

Here's a simple example where I have an array of numbers and I want to make a new array of those numbers multiplied by 2:

var numbers = [5, 7, 20, 3, 13];

var arr1 = [];
var len = numbers.length;
for(var i = 0; i < len; i++){
    arr1.push(numbers[i] * 2);
}
alert(arr1);

var arr2 = [];
for(var i = 0; i < len; i++){
    arr2[arr2.length] = numbers[i] * 2;
}
alert(arr2);
Tom
  • 4,422
  • 3
  • 24
  • 36

1 Answers1

1

The fastest way to do it with current JavaScript technology, while also using minimal code, is to store the last element first, thereby allocating the full set of array indices, and then counting backwards to 0 while storing the elements, thereby taking advantage of nearby memory storage positions and minimizing cache misses.

var arr3 = [];
for (var i = len; i>0;){
    i--;
    arr2[i] = numbers[i] * 2;
}
alert(arr2);

Note that if the number of elements being stored is "big enough" in the view of the JavaScript engine, then the array will be created as a "sparse" array and never converted to a regular flat array.

Yes, I can back this up. The only problem is that JavaScript optimizers are extremely aggressive in throwing away calculations that aren't used. So in order for the results to be calculated fairly, all the results have to be stored (temporarily). One further optimization that I believed to be obsolete, but actually improves the speed even further is to pre-initialize the array using new Array(*length*). That's an old-hat trick that for a while made no difference, but no in the days of extreme JavaScript engine optimizations, it appears to make a difference again.

<script>
function arrayFwd(set) {
var x = [];
for (var i = 0; i<set.length; i++)
x[x.length] = set[i];
return x;
}

function arrayRev(set) {
var x = new Array(set.length);
for (var i = set.length; i>0;) {
i--;
x[i] = set[i];
}
return x;
}

function arrayPush(set) {
var x = [];
for (var i = 0; i<set.length; i++)
x.push(set[i]);
return x;
}

results = []; /* we'll store the results so that
optimizers don't realize the results are not used
and thus skip the function's work completely */
function timer(f, n) {
return function(x) {
var n1 = new Date(), i = n;
do { results.push(f(x)); } while (i-- > 0); // do something here
return (new Date() - n1)/n;
};
}

set = [];
for (i=0; i<4096; i++)
set[i] = (i)*(i+1)/2;

timers = {
forward: timer(arrayFwd, 500),
backward: timer(arrayRev, 500),
push: timer(arrayPush, 500)
};
for (k in timers) {
document.write(k, ' = ', timers[k](set), ' ms<br />');
}
</script>

Opera 12.15:

forward = 0.12 ms backward = 0.04 ms push = 0.09 ms

Chrome (latest, v27):

forward = 0.07 ms backward = 0.022 ms push = 0.064 ms

(for comparison, when results are not stored, Chrome produces these numbers: forward = 0.032 ms backward = 0.008 ms push = 0.022 ms

This is almost four times faster versus doing the array forwards, and almost three times faster versus doing push.)

IE 10: forward = 0.028 ms backward = 0.012 ms push = 0.038 ms

Strangely, Firefox still shows push as faster. There must be some code re-writing going on under the hood with Firefox when push is used, because accessing a property and invoking a function are both slower than using an array index in terms of pure, un-enhanced JavaScript performance.

Joseph Myers
  • 6,434
  • 27
  • 36
  • 3
    Can you back this up? – Tom Jun 06 '13 at 02:11
  • 1
    In fact, it will create a sparse array first, change the length of the array and then fill up each of the elements in reverse order, and then only when the `0` index is filled, then it is converted to a "regular" array. In my testing, when allocating an array, this method is in fact slower than a forward loop. Also, your code isn't completely optimised. – Qantas 94 Heavy Jun 06 '13 at 02:17
  • 1
    @user2246674 There's really no consistency across browsers, so it's not really worth it to try. Differences occur between sizes of the array, browser, and the way `[]` is used. Some people use `[i]` in a loop, some use `[array.length]`, which have different implications – Ian Jun 06 '13 at 02:22
  • +1 on asking for a back up on "the fastest way to do it" – leopic Jun 06 '13 at 02:33
  • 2
    @Qantas94Heavy You are right that this works differently today than it did the last time I tested it. Before, doing it backwards was always a big winner. Now it seems that browsers still create a sparse array as you say, in particular Firefox, which performs more quickly with push. In principle, doing it backwards should be the fastest, because it does the same thing as initializing the full array and then storing adjacent elements. But due to JavaScript engine optimizations, what is written in code is not what actually happens in the background. – Joseph Myers Jun 06 '13 at 02:47
  • In a lot of my benchmarks, looping through an array forwards often ends up faster than `i--`, probably because of engine optimizations that expect you to do it that way – Ben Gubler Apr 03 '19 at 01:51