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)?

Answer 1

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, everytime 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 your graph has more an quadratic or even a slight exponential look to it.

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 datastructures 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 datastructures and some differences/advancements between them