News for hackers. Stuff that matters.
Re:What's wrong with this code, really? by thaumaturgy on Friday September 16, 2011 @10:53AM (#3004638)
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.

Re:What's wrong with this code, really? by bzbarsky on Friday September 16, 2011 @06:45PM (#3006617)
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.

Re:What's wrong with this code, really? by thaumaturgy on Friday September 16, 2011 @07:12PM (#3006684)
Thanks! That explains a lot. I'm actually really surprised that they're implemented that way (pleasantly surprised) -- I didn't think even "high performance" code was generally done like that anymore.
Re:What's wrong with this code, really? by simonsarris on Friday September 16, 2011 @11:10AM (#3004734)
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.
Re:What's wrong with this code, really? by sanderjd on Friday September 16, 2011 @01:23PM (#3005362)
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.
Re:What's wrong with this code, really? by seabee on Friday September 16, 2011 @02:00PM (#3005531)
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