Array.shift optimizations in Firefox's JS Engine
unshift: remove / add items at the front of the array.
push: remove / add items at the end of an array.
I had a scenario where using
shift acted differently than I expected and lead to some interesting results.
How Array.shift works
By definition on MDN:
The shift method removes the element at the zeroeth index and shifts the values at consecutive indexes down, then returns the removed value. If the length property is 0, undefined is returned.
It will take an item off the array and shift every other item over.
Let's have an example with a simple array of size 6 counting the numbers 0-5.
If you ran this code on it:
let arr = [0, 1, 2, 3, 4, 5]array.shift()
It would return the number
0 and the array remaining would be
[1, 2, 3, 4, 5]. Now that's fine for a small array as it shifted the 5 remaining items over.
but what if we had an array of size 100,000? Or what if the items of the array were complex objects? Thinking about this algorithm simply, it does not scale as you would need to traverse a large amount of data every time you ran
I was working on a codebase that ran into this bottleneck, but what perplexed me was how in Firefox it ran almost instantly while in Node / Chrome it took seconds to complete. To figure out how this actually worked, I dug around and found some inner workings of how Firefox implements this function which gives it a huge performance boost.
Perf Boost with Pointers
In the case of Firefox, their engine is called SpiderMonkey which is mainly written in C / C++. With that being the case, arrays in C are pointers that tell a computer at what memory address is the beginning of an array. Up till 2017, the
array.shift method that was implemented in SpiderMonkey was a slow implementation that it had to move items one by one. In 2017, though, some engineers at Mozilla had an idea: what if instead of moving the items one by one in a shift, you just move the pointer or tell the computer a new address to where the array starts.
So now there is just 2 computations in the end.
- Moving the first item off the array.
- Move the pointer of the front of the array over by one.
In terms of time complexity, this reduces a linear process to a constant process (O(n) to O(1)). So no matter the size of the array, on average the shift would happen instantly.
So we found out that
array.shift is now fast in Firefox, so we can stick with it and move on with our day? It would be great, but sadly no. As this project that lead me to discover these details is a universal JS package, it should be able to run on any JS runtime with comparable performance. Chrome has a similar algorithm, but it only works for arrays under size of ~50k items (A story for another day). So in the end,
shift wasn't going to pan out when working with large arrays in this case, but the sleuthing I did provided an example that programming language specifications and implementations can differ and give the creative freedoms for the engineers building these runtimes or compilers to highly optimize these internal functions to great extents.