2

In running performance benchmarks on Array#push() and Array#unshift(), push vastly outperforms unshift, and the running time seems tied to the length of the array. This performance gap seems to be apparent across browsers.

Given the difference, I'm curious to know what types of data structures do V8 and OdinMonkey use to represent arrays, and how that prevents an unshift operation that runs in O(1) time.

fny
  • 31,255
  • 16
  • 96
  • 127
  • Well, both V8 and OdinMonkey are open source, so... [Here's the V8 project](http://code.google.com/p/v8/), [SpiderMonkey is here](https://developer.mozilla.org/en-US/docs/Mozilla/Projects/SpiderMonkey). – T.J. Crowder Mar 27 '14 at 16:47
  • Take a look at the implementation for the v8 here: http://izs.me/v8-docs/classv8_1_1Array.html – Alec Moore Mar 27 '14 at 16:48
  • @AlecMoore V8's implementation of storage of indexed properties is entirely separate to that of the Array object. Notably, the same representation is used for the indexed properties in `{0: 1, 1: 2, 2: 3}` as in `[1,2,3]`. – gsnedders Mar 27 '14 at 17:07
  • possible duplicate of [Are javascript Arrays actually implemented as arrays?](http://stackoverflow.com/questions/9233814/are-javascript-arrays-actually-implemented-as-arrays) – gsnedders Mar 27 '14 at 17:25
  • 1
    Consider what has to happen in both cases: push - add a *single* index; unshift - and an index and update *every other* index. That is, the bounds of these two operations are *amortized* as `O(1)` and `O(n)`, pretty much irrespective of the implementation when using a contiguous - be it actual underlying array indexes or "keys" - approach is used. – user2864740 Mar 27 '14 at 18:29
  • @user2864740 It's only O(n) if each property stores its index. If it were to be stored in linked list, insertion could be done in O(1) time (though a linked list would have O(n) lookup time). – gsnedders Mar 27 '14 at 18:44
  • @gsnedders "when using a contiguous .. approach" (this includes keys functioning as indices). However, since an index operation must also be supported (and it's widely assumed to be O(1), although I don't think it's mandated) *and* arrays must be able to support "missing keys" (i.e. be sparse), I doubt that there are standard LL ("non-contiguous", which would avoid having to update each *index*) implementations in use. In any case, it seems like a poor example/use-case for trying to reason about the underlying implementation, given the other restriction and semantic differences. – user2864740 Mar 27 '14 at 18:53
  • @user2864740 Oh, I got lost over the dashed part. :) FWIW, in several implementations (Carakan definitely, SpiderMonkey from memory, and I think JSC too?) sparse arrays are binary search trees, and hence indexing isn't always O(1). – gsnedders Mar 27 '14 at 18:53
  • @gsnedders Ah, *now* that's darn interesting :) – user2864740 Mar 27 '14 at 18:54
  • Indexing is definitely not uniform: http://jsperf.com/many-unshifts. – fny Mar 27 '14 at 22:38

0 Answers0