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)
- Static array
- Pre-allocated array
- Buffer
- Array
Actual results (from fastest to slowest)
- Static array (228.039ms)
- Buffer (1.135s)
- Array (2.545s)
- 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
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 🙂
Top comments (6)
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.
if you try to set the fourth element using the index it will be much slower than just using the
.pushfunctionthe 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.pushto 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.
If I understand this correctly, does this mean that
new Array(1000)doesn't actually allocate a typed array under the hood?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.
There seems to be some variation between browsers, with Chrome being the odd one out: blog.scottlogic.com/2010/10/15/jav...
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.I love this and I’m going to try it on stream this week!