Performance of Array.push vs Array.unshift

Question

I was reading about runtime complexities of array operations and learned that...

the ECMAScript specification does not mandate a specific runtime complexity, so it depends on the specific implementation / JavaScript engine / runtime behavior [1] [2].
Array.push() runs in constant andArray.unshift() in linear time for sparse arrays implemented by a hash-table like data structure [3].

Now I was left wondering whether push and unshift have the same constant respectively linear time complexity on dense arrays. Experimental results in Firefox/Spidermonkey confirm that:

Now my questions:

Are there official docs or references confirming the observed runtime performance for Firefox/Spidermonkey and Chrome/Node/V8?
Why has unshift not been implemented with constant runtime similar to push (and e.g. maintaining an index offset; similar to perl arrays)?

related? http://stackoverflow.com/questions/12250697/time-complexity-of-unshift-vs-push-in-javascript — Louis Loudog Trottier, May 17 '17 at 17:52
@LouisLoudogTrottier That's one of the questions linked above for reference. My question is specific to the chosen implementation, not the time complexity mandated by the spec (i.e. none). — le_m, May 17 '17 at 17:54

score 50 · Answer 1 · edited Jan 23 '23 at 14:20

To understand this, there needs to be some knowledge about how a Stack (in JavaScript, an Array) is designed in computer science and is represented within your RAM/memory. If you create a Stack(an Array), essentially you are telling the system to allocate a space in memory for a stack that eventually can grow.

Now, every time you add to that Stack (with push), it adds to the end of that stack. Eventually the system sees that the Stack isn't going to be big enough, so it allocates a new space in memory at oldstack.length*1.5-1 and copies the old information to the new space. This is the reason for the jumps/jitters in your graph for push that otherwise look flat/linear. This behavior is also the reason why you always should initialize an Array/Stack with a predefined size (if you know it) with var a = new Array(1000) so that the system doesn't need to "newly allocate memory and copy over".

Considering unshift, it seems very similar to push. It just adds it to the start of the list, right? But as dismissive this difference seems, its very big! As explained with push, eventually there is a "allocate memory and copy over" when size runs out. With unshift, it wants to add something to the start. But there is already something there. So it would have to move the element at position N to position N+1, N1 to N1+1, N2 to N2+1 etc. Because that is very inefficient, it actually just newly allocates memory, adds the new Element and then copies over the oldstack to the newstack. This is the reason why your graph has more a quadratic or even slightly exponential look.

To conclude:

push adds to the end and rarely needs reallocate memory + copy over.
unshift adds to the start and always needs to reallocate memory and copy data over

/edit: regarding your questions why this isn't solved with a "moving index" is the problem when you use unshift and push interchangeably, you would need multiple "moving indexes" and intensive computing to figure out where that element at index 2 actually resides in memory. But the idea behind a Stack is to have O(1) complexity.

There are many other data structures that have such properties (and more features) but at a tradeoff for speed, memory usage, etc. Some of these datastructures are Vector, a Double-Linked-List, SkipList or even a Binary Search Tree depending on your requirements

Here is a good resource explaining data structures and some differences/advancements between them

Thanks! *This is the reason for the jumps/jitters in your graph* - seems so, but I wonder why these jitters appear at a somewhat constant, not logarithmic rate (compare e.g. with the 'steps'). Might have to do with garbage collection? *So it would have to move the element at position N to position N+1* - or it could increment an index offset which is then added when accessing array elements by their index (that's what I meant by 'and e.g. maintaining an index offset'). Still looking for the 'why' here and references. — le_m, May 17 '17 at 18:16
for your second question, please see my updated answer about other datastructures. Regarding your first; the jitters are pretty sure related to GC or other programms running on your system. As you see it is very constant increase, thus linear -> more elements in -> more time spent. Logarithmic would mean more elements -> less time. Exponential means more element -> muchmuch more time. — japrescott, May 17 '17 at 18:25
But the idea behind a Stack is to have O(1) complexity - perhaps my explanation was too short; it is definitely possible to maintain O(1) for appending in both directions; compare to e.g. perl arrays perlmonks.org/?node_id=17890 - regarding the jitter; agree with your update. A growth factor of around ~2 causes the 'steps', the jitter might have to do with GC. Thanks for the valuable discussion! — le_m, May 17 '17 at 18:47
`new Array(1000)` causes other problems though, because it creates a "holy array", it cannot be optimized as well as an array that does not have holes. If you're creating the array once but using it many times, `push` may still be faster. Another option is to use `new Array(1000)` to create the array, then after filling it make a copy with `myArray = JSON.parse(JSON.stringify(myArray))`, since this copy will not have holes. — Yay295, Apr 15 '19 at 22:04
A common optimisation that can be used when having a looping algorithm using unshift calls is to use `Array.push` instead and reverse the elements at the end with `Array.reverse`. — Vincent Pazeller, Mar 27 '20 at 09:20
`.push` being mostly quick but sometimes slow is called amortization in computer science: https://stackoverflow.com/questions/11102585/what-is-amortized-analysis-of-algorithms — Sámal Rasmussen, Sep 02 '22 at 10:02

Performance of Array.push vs Array.unshift

1 Answers1

Linked