34

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)?
Community
  • 1
  • 1
le_m
  • 17,771
  • 9
  • 60
  • 73
  • Did you mean to say *"[...] with **constant** runtime similar to `push` [...]"*? Above you are saying that `push` is constant and `unshift` is linear. Or am I misunderstanding something here? – Felix Kling May 17 '17 at 17:45
  • @FelixKling Yep, thanks. Edited the question. – le_m May 17 '17 at 17:46
  • 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

1 Answers1

42

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

japrescott
  • 4,347
  • 3
  • 22
  • 34
  • 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
  • 1
    `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