4 ms·

Its heavily implementation dependent, but for many implementations of lists and arrays shift is slower than pop. Shift tends to require moving the entire array

Its heavily implementation dependent, but for many implementations of lists and arrays shift is slower than pop. Shift tends to require moving the entire array around, while pop does not. It's rarely the case with doubly-linked lists, or with perl arrays (they do something special, keep the starting offset recorded or something) For you case deleting from either end ought to be fine, but you've made the other implicit tradeoff because merely accessing items in the middle of a linked list will be slow. In the case of something like a JavaScript array, removing from the front is 80% slower than removing from the end: http://jsperf.com/popvsshift http://jsperf.com/popvsshift Same deal with Python lists. From the Python spec: http://docs.python.org/tutorial/datastructures.html#using-lists-as-queues http://docs.python.org/tutorial/datastructures.html#using-li... It is also possible to use a list as a queue, where the first element added is the first element retrieved (“first-in, first-out”); however, lists are not efficient for this purpose. While appends and pops from the end of list are fast, doing inserts or pops from the beginning of a list is slow (because all of the other elements have to be shifted by one).

thaumaturgy 15y ago
Yikes. That's quite a difference in performance ... what I still don't understand though is, why? I've done a little bit of searching and I can't find anything so far on how JS arrays are implemented. Since JS arrays are objects and inherently support things like out-of-order indexes, non-integer indexes and that kind of thing, maybe we can assume it's some kind of hash map? A tree would make sense too, for faster accesses, and if a pop() on the tree meant removing the root node (and rebalancing the tree), then I suppose that would make sense, too. But, honestly, for the majority of stuff in Javascript, I'd be surprised if some kind of hybrid hash-map / ordered skip list weren't being used instead. Ordered skip lists can be about as fast as a binary tree, without the costs associated with rebalancing, and a lot less complexity. You'd have some tradeoffs in memory usage depending on how you want to tune your skip list, but given the absurd memory requirements for modern software, that doesn't seem to be a consideration amongst programmers anymore. So ... I accept that removing items from the head of a list in these higher-level languages is (a lot) more expensive. But I still don't get why.
- deleted 15y ago
  [deleted]
- simonsarris 15y ago
  Most of the time it is simply because a shift operation has to re-address each element in the array (if it is implemented like a ho-hum, classic array) and a pop operation does not have to do this.
  - sanderjd 15y ago
    I think the assumption was that even arrays indexed by integers are stored as JS Objects, which are basically a hashmap style structure, and so they wouldn't be implemented like a ho-hum, classic array. I'm not sure if that assumption is right, but if it is, there would be no need to re-address each element.
    - seabee 15y ago
      If you don't re-address each element, how do you map the value at index 1 to index 0? One way is to leave the indexes intact and keep an offset around, so you may map the nth logical index to the nth physical one. (Add 1 on a shift, subtract 1 on an unshift.) But if you wanted this behaviour, there are more efficient ways: http://en.wikipedia.org/wiki/Circular_buffer http://en.wikipedia.org/wiki/Circular_buffer
- bzbarsky 15y ago
  JS arrays are implemented in a variety of ways in different JS engines, but at least V8 and Spidermonkey have a "fast case" where there's an actual C array (single contiguous chunk of memory) and fall back on a slower representation in the rare cases (large holes in the array, non-integer indices, etc). So in the common case, you are in fact looking at a big memcpy every time you remove an object from the front, unless you do some magic with keeping track of a nonzero offset in your C array. V8 does that magic in some cases but not others, as far as I can tell.
  - thaumaturgy 15y ago

thaumaturgy 15y ago

Yikes. That's quite a difference in performance ... what I still don't understand though is, why? I've done a little bit of searching and I can't find anything so far on how JS arrays are implemented. Since JS arrays are objects and inherently support things like out-of-order indexes, non-integer indexes and that kind of thing, maybe we can assume it's some kind of hash map? A tree would make sense too, for faster accesses, and if a pop() on the tree meant removing the root node (and rebalancing the tree), then I suppose that would make sense, too. But, honestly, for the majority of stuff in Javascript, I'd be surprised if some kind of hybrid hash-map / ordered skip list weren't being used instead. Ordered skip lists can be about as fast as a binary tree, without the costs associated with rebalancing, and a lot less complexity. You'd have some tradeoffs in memory usage depending on how you want to tune your skip list, but given the absurd memory requirements for modern software, that doesn't seem to be a consideration amongst programmers anymore. So ... I accept that removing items from the head of a list in these higher-level languages is (a lot) more expensive. But I still don't get why.

deleted 15y ago
[deleted]
simonsarris 15y ago
Most of the time it is simply because a shift operation has to re-address each element in the array (if it is implemented like a ho-hum, classic array) and a pop operation does not have to do this.
- sanderjd 15y ago
  I think the assumption was that even arrays indexed by integers are stored as JS Objects, which are basically a hashmap style structure, and so they wouldn't be implemented like a ho-hum, classic array. I'm not sure if that assumption is right, but if it is, there would be no need to re-address each element.
  - seabee 15y ago
    If you don't re-address each element, how do you map the value at index 1 to index 0? One way is to leave the indexes intact and keep an offset around, so you may map the nth logical index to the nth physical one. (Add 1 on a shift, subtract 1 on an unshift.) But if you wanted this behaviour, there are more efficient ways: http://en.wikipedia.org/wiki/Circular_buffer http://en.wikipedia.org/wiki/Circular_buffer
bzbarsky 15y ago
JS arrays are implemented in a variety of ways in different JS engines, but at least V8 and Spidermonkey have a "fast case" where there's an actual C array (single contiguous chunk of memory) and fall back on a slower representation in the rare cases (large holes in the array, non-integer indices, etc). So in the common case, you are in fact looking at a big memcpy every time you remove an object from the front, unless you do some magic with keeping track of a nonzero offset in your C array. V8 does that magic in some cases but not others, as far as I can tell.
- thaumaturgy 15y ago