DEV Community

Henry Williams
Henry Williams

Posted on

Populating a pre-allocated array slower than a pushing to a regular array?

For no good reason, I got the urge to do a performance comparison between populating an array by pushing to it vs writing to a buffer. Then, to make things more interesting, I decided to add a static array and a pre-allocated standard array.

Let's just say the results were not what I expected.

Experiment

Populate the 4 data structures by adding 10^8 elements to each and comparing the time it took for each of them.

Candidates

  • Static array - populated by writing directly to the index
  • Pre-allocated dynamic array - array initialized to hold all elements and then populated by setting elements for each index
  • Buffer - populated by writing directly the offset. Should be similar to writing to an index, but there might be some internal overhead
  • Array - empty array populated by pushing elements to it

Expected results (from fastest to slowest)

  1. Static array
  2. Pre-allocated array
  3. Buffer
  4. Array

Actual results (from fastest to slowest)

  1. Static array (228.039ms)
  2. Buffer (1.135s)
  3. Array (2.545s)
  4. Pre-allocated array (6.062s) (Why so slow???)

What I don't understand is why the pre-allocated array performed so poorly. I would expect its performance to be on par with a static array. I definitely didn't expect it to be outperformed by an array built by pushing elements into it.

Code

const NUMBER_OF_ELEMENTS = 10**8
const ELEMENT_LEN_BYTES = 4

const array = []

console.time('array')

for (let i = 1; i <= NUMBER_OF_ELEMENTS; i++) {
    array.push(i)
}

console.timeEnd('array')

const preAllocatedArray = new Array(NUMBER_OF_ELEMENTS)

console.time('pre-allocated array')

for (let i = 1; i <= NUMBER_OF_ELEMENTS; i++) {
    preAllocatedArray[i - 1] = i
}

console.timeEnd('pre-allocated array')

const intArray = new Uint32Array(NUMBER_OF_ELEMENTS)

console.time('int array')

for (let i = 0; i < NUMBER_OF_ELEMENTS; i++) {
    intArray[i] = i + 1
}

console.timeEnd('int array')


const buffer = Buffer.alloc(NUMBER_OF_ELEMENTS * ELEMENT_LEN_BYTES, 0)

console.time('buffer')

for (let i = 1, offset = 0; i <= NUMBER_OF_ELEMENTS; i++) {
    offset = buffer.writeUInt32BE(i, offset)
}

console.timeEnd('buffer')

// Results:
// array: 2.545s
// pre-allocated array: 6.062s
// int array: 228.039ms
// buffer: 1.135s
Enter fullscreen mode Exit fullscreen mode

Edit: It looks like the V8 engine's optimizations favor .push() over direct index assignment. The findings for Chrome in [this (ancient) article] are consistent with my results on Edge, Chrome, and Nodejs; all of which run on top of the v8 engine.

Thanks @alain Van Hout for sharing the link in the comments.

If anyone has any ideas how those optimizations are performed, please do share ­čÖé

Discussion (6)

Collapse
mse99 profile image
Mohamed Edrah • Edited on

The JavaScript engine (as an optimization) uses actual typed arrays behind the scenes, this will not be the case if you use arrays with holes (empty slots i.e the length element is disproportional to the amount of properties (elements) in the array).

JavaScript arrays are objects (technically they're defined as an 'exotic' object in the standard), whenever you try to set (via the assignment operator) or get a property from an object the JS engine has to perform a lookup algorithm which is slow, which is why JavaScript engines use typed arrays and other tricks to speed up getting and setting array elements.

the reason is the pre-allocated array is much slower because it's holey which means that the properties (elements) you're trying to set (or get) don't actually exist on the array, but there's a chance that they might exist on the prototype chain so the runtime will preform a lookup operation which is slow compared to just getting the element from memory and returning it.

also the runtime will probably consult the prototype chain when you try to access an index that doesn't exist on the array (even if the array doesn't have empty slots), lets say you have an array with 3 elements in it.

const arr = [1,2,3];

if you try to set the fourth element using the index it will be much slower than just using the .push function

arr[arr.length] = 4; // would probably be slower
arr.push( 4 ); // should in theory be faster  

the reason behind pushing new items using the length being slower, is the fact that the runtime must perform a [[set]] operation on the object and climb the entire prototype chain of the array, avoid accessing indices that don't exist on the array always do a bounds check before you try to get or set an element in the array, always use .push to append new elements to the array.

avoid using the Array(...) constructor it's terribly uncommon and gets lots of flak from the community for being bug prone because if you pass in only one number argument it will return a holey array, also avoid pushing null or undefined as items as they (in some cases degrade performance).

also if you can you should try to keep the type of values in your arrays the same, if you have an array of numbers don't push a string to it unless you really have to.

Collapse
henryjw profile image
Henry Williams Author

The JavaScript engine (as an optimization) uses actual typed arrays behind the scenes, this will not be the case if you use arrays with holes (empty slots i.e the length element is disproportional to the amount of properties (elements) in the array).

If I understand this correctly, does this mean that new Array(1000) doesn't actually allocate a typed array under the hood?

Collapse
mse99 profile image
Mohamed Edrah

It probably does allocate some sort of array or object behind the scene, It won't be as performant because the runtime will have to do extra work in order to get or set elements, but to answer your question, no allocation does happen one way or another the runtime will create a data structure to represent your program's data.

Collapse
alainvanhout profile image
Alain Van Hout

There seems to be some variation between browsers, with Chrome being the odd one out: blog.scottlogic.com/2010/10/15/jav...

Collapse
henryjw profile image
Henry Williams Author

Thanks for sharing. My assumption is that this behavior is in the V8 engine that Chrome runs. The tests I shared were executed in Node.js, but I see similar behavior in Edge (Chromium version) and Chrome.

I think that optimization makes sense since using .push() is probably a more common way of building an array in web applications.

Collapse
nocnica profile image
No─Źnica Fee

I love this and IÔÇÖm going to try it on stream this week!