4 ms·
My favorite one of these in JavaScript is building an array by unshifting onto it: var array = []; for (...) { array.unshift(whatever); }
by pcwalton 12y ago
My favorite one of these in JavaScript is building an array by unshifting onto it:
var array = [];
for (...) {
array.unshift(whatever);
}
jQuery (at least used to) do this all over the place, to disastrous results. IIRC, in fact, V8 has special optimizations that allow arrays to grow backwards if there's room in the heap, just because this is so common in JavaScript :(
(Solving this in your code is usually trivial, by the way: just replace unshift with push and use Array.reverse at the end.)
- wfunction 12y agoIMO all arrays should be double-ended.
- aidos 12y agoBut wouldn't that slow down all arrays in the general case....?
- wfunction 12y agoMaybe by like 2 CPU instructions? Javascript isn't C; that level of performance is noise in JS...
- pcwalton 12y agoYou'd be surprised. Adding 2 instructions to every array operation would probably kill your engine's relative SunSpider or V8 score. JS performance is extremely competitive.
- wfunction 12y agoSure, I can believe it'd affect the score, but I can't believe anyone would actually care about it. It's not like Javascript was designed for performance to begin with.
- nightcracker 12y agoI'm working on a data structure that is not slower: https://github.com/orlp/devector https://github.com/orlp/devector
- lilyball 12y agoOn a related note, NSArray, the standard array class in Cocoa, is actually implemented as a circular array under the hood, allowing you to unshift/shift just as efficiently as you can push/pop. The reason it's able to do this is because it doesn't have any API that exposes a pointer to its object storage. Without the need to have a pointer to its storage, there's no need to ensure the objects are actually stored contiguously and in-order, which means using a circular array is a trivial optimization. There are other data structures it could use instead, such as a sequence of fixed-length arrays like (common implementations of) std::deque, but I guess a circular buffer was chosen because it meets all of the complexity guarantees and is still pretty simple. Although I'm also generalizing a bit, because it turns out that NSArray/CFArrayRef actually changes the implementation it uses when the array gets large enough (I don't remember precisely where to find it, but there's a blog post out there with details on the observed performance of NSArray/CFArrayRef as it grows). But in most cases, it's probably a circular array. On that note, I'd think that using a circular array would be an obvious optimization for any JavaScript implementation. JavaScript doesn't have any need to store its values contiguously and in-order (since JavaScript doesn't have pointers so it can't possibly expose a pointer to its storage). I would expect that unshifting arrays (and shifting them) is common enough that this optimization is an obvious win for all engines.
- nightcracker 12y agoI'm working on a data structure that is double-ended as well as contiguous: https://github.com/orlp/devector https://github.com/orlp/devector
- eridius 12y agoInteresting. I do wonder what pathological performance is like, though. I would imagine that you can design an access scenario that does pushes/pops and shifts/unshifts in the right order to cause it to keep shuffling elements back and forth within the storage (without reallocating) indefinitely even though the number of elements never grows beyond a set amount.
- 12y ago
- TazeTSchnitzel 12y agoOf course, it depends on the language. If you're using a language with linked lists, appending is the wrong way to do it. :) On a different note: it's nice to see this here, it validates my choice to .reverse() and .push() when using an array as a queue today.
- wfunction 12y agoLinked lists are only useful in very few situations and this is not one of them.
- Niksko 12y agoI've been terrified of linked structures since I saw a video (I think it was here) from a C++ conference talking about how horrible their performance is.
- adsr 12y agoYou could keep pointers to both the head and tail in the list object though. Then adding and removing stuff would be O(1) for both ends.
- thaumaturgy 12y agoYep, and that used to be idiomatic, years and years ago when people still wrote their own linked lists. I'd be surprised if it isn't still the standard behavior for that data structure.