Performance of Array.push vs Array.unshift

Viewed 16421

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:

Array push vs. unshift performance

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)?
1 Answers
Related