8 ms·
Array.shift Optimizations in Firefox's JavaScript Engine (2020)
- melvinroest 2y agoI'm surprised to read that for less than 50K elements it's likely to be O(1). It's a clever trick to just move the memory address one element further :)
- melvinroest 2y agoSome more technical info that browsers nowadays have O(1) behavior when using Array.shift() [1]. [1] https://bugzilla.mozilla.org/show_bug.cgi?id=1348772 https://bugzilla.mozilla.org/show_bug.cgi?id=1348772
- DaiPlusPlus 2y agoDisclaimer: when I worked on Internet Explorer in its twilight years I built a fork of BingBot that surveyed JS API usage and delivered a report to a Partner-level SE, whom I was in awe of, that I shared a team-room with. In my experience, Array.prototype.shift() had limited applications because it mutates the source-array. I gathered it exists because at the time it was specc’d in the late 1990s the other cool kids, bash and perl, both had had args shift and JS didn’t want to feel left-out. How different would the world be today if Array.prototype.shift instead froze the array and returned a reference to a +1 slice of the array instead? There was a fantastic opportunity to introduce FP and immutability to a whole generation of software people - which we (as an industry) squandered to our detriment. Ultra-new languages like Go and Zig still default to in-place mutable data and it’s maddening! What hath shell scripts wrought?
- dumbo-octopus 2y agoDo you think Array.prototype.push() also has limited applications? It too mutates the source array, but must be the most commonly used Array method there is. And the two combined make for a lovely FIFO. Anyone is certainly free to use Array.prototype.slice() if they want a view.
- pipe01 2y agoI wouldn't say go is exactly ultra new
- dchest 2y agoWhat are you doing with arrays that mutating them is maddening and has limited applications? Is this some kind of a cult?
- chatmasta 2y ago> Is this some kind of a cult? Yes, it’s called Functional Programming.
- eyelidlessness 2y agoHey now. In that cult (of which I’m a member), mutation is definitely maddening but its application is by no means limited (which is a non-small factor in it being maddening).
- recursive 2y agoSounds like it would go about as well as making me appreciate Shakespeare by forcing me to read it. It didn't work at all. Do you enjoy reasoning about stale references in react? Now you can experience this joy everywhere with the power of immutability.
- xxs 2y agoI'd take mutability for an array as given. If I wanted functional style data structures I'd use them. Personally I see zero reason for immutability of an array, imagine every add/push had to create a new instance of the said array.
- merb 2y agoI would expect arrays to be immutable and list type not
- matharmin 2y agoIt's actually not exactly 50K, and likely varies across Chrome/V8 versions, operating system and/or machine architecture. On my browser the threshold is around 22500 elements. For a quick test, see [1]. The difference in V8 appears to be based on whether or not the array is stored in "large object space" [2], which seems to be used when the object is somewhere between 64kb and 128kb [3] (once again can depend on lots of factors). I wonder how many other optimizations depend on that? [1]: http://www.lonniebest.com/BadShiftPerformance/ http://www.lonniebest.com/BadShiftPerformance/ [2]: https://issues.chromium.org/issues/42202676 https://issues.chromium.org/issues/42202676 [3]: https://github.com/danbev/learning-v8/blob/master/notes/heap.md#pagesize-in-v8 https://github.com/danbev/learning-v8/blob/master/notes/heap...
- rat9988 2y agoIt has been a long time since I have read v8 source code, but I remember it depended on if the array is holey or not, so it would switch back to object based array instead of a contiguous array. (there were other conditions but it's the notable one I remember)
- mettamage 2y agoReading ff source code, I saw something similar with a hole variable. I haven’t spent enough time on what happens though. A good way to search the ff source code is to look at uniquely named JS functions and take it from there. I searched on reduceRight and found shift because of it.
- yxhuvud 2y agoSome other languages also perform this optimization, for example Ruby and Crystal.
- lifthrasiir 2y agoIt is important that such optimization will keep the array's full capacity when naively implemented. For example, calling `Array.shift` 999,000 times to an array with 1,000,000 elements will reduce it to 1,000 elements but its capacity will be at least 1,000 times that. A reasonable implementation would shrink the capacity when some threshold is reached [1]. [1] This threshold should be much lower than the growth threshold in order to prevent an unnecessary copying when the number of elements is around the threshold.
- _flux 2y agoI don't think it's so clear-cut that the capacity should be decreased in that case, because it not only destroys the theoretical complexity of algorithms using it, but also because in practice there can be cases where an array gets increased to 1000000 elements, then it gets consumed to 0 elements, after which it again is increased to 1000000 elements for the next round of operations. Converting the array to be backed by a smaller allocation is not free. Indeed, which case is even more common: large arrays getting smaller and then kept that way, or large arrays getting smaller to grow again later? I suppose some more complicated metric (e.g. keeping track of reallocations per array) could help with the most common cases.
- csjh 2y agoDecreasing capacity wouldn't affect the theoretical complexity of algorithms using it - same concept as increasing capacity during push still being amortized O(1)
- _flux 2y agoI don't think it works that way when a container can grow and shrink, because an algorithm can trigger those operations any number of times, not just O(log(n)) times.
- csjh 2y agoI'm not sure where you're getting O(logn) from here. If it couldn't work that way when a container can grow and shrink, then arrays wouldn't be able to have both amortized O(1) push and pop as they do in most relevant implementations. As long as the expensive O(n) resize operation happens at some frequency relative to the size of the container rather than every constant size difference (i.e. capacity doubles when length == capacity and halves when length == capacity/2) then it will amortize out to O(1). There's a proof available in section 2.1.2 of this textbook: https://opendatastructures.org/ods-java/2_1_ArrayStack_Fast_Stack_O.html https://opendatastructures.org/ods-java/2_1_ArrayStack_Fast_...
- parhamn 2y ago> it should be able to run on any JS runtime with comparable performance How long until every app ships their own wasm js runtime to ensure consistent performance characteristics?
- harrygeez 2y agoif you are at a stage where this matters you will not be using Array.shift or even Array for that matter. JavaScript has lower level facilities for this.
- andyferris 2y agoDo you mean Uint8Array etc and ArrayBuffer and so on? Or something else?
- danybittel 2y agoWhile it's clever, it is also counter intuitive. I would expect an array to be 0(n) when inserting from the beginning. If I wanted something fast from both side, I'd use a double ended queue[1]. This, as the author shows, lead to unexpected behavior. [1] https://en.wikipedia.org/wiki/Double-ended_queue https://en.wikipedia.org/wiki/Double-ended_queue
- Karellen 2y agoIsn't this kind of negated by the fact that `delete arr[n]` working the way it does has required JavaScript arrays to never have been "real" arrays, in the entire history of the language?
- eyelidlessness 2y agoI don’t think so. There’s a little bit more nuance to it (because it involves array “holes”—almost a third kind of null), but delete on an array index is semantically closer to assigning undefined to the index. It doesn’t actually delete the presence of the index.
- Karellen 2y ago> It doesn’t actually delete the presence of the index. Doesn't it? Try: a = [ 6, 7, 8, 9, 10 ] delete a[2] for (x in a) { console.log(x) }
- eyelidlessness 2y agoIt doesn’t. It deletes the property “2”, but the index 2 remains present as a “hole” (like I mentioned before, almost a third kind of null). That removes it from iteration over the array object’s properties (i.e. your for-in loop), but doesn’t remove the index from the array or its iterable value representation: https://www.typescriptlang.org/play/?#code/MYewdgziA2CmB0w4EMBOAKAlAWAFB9EgBcACZEgXhIG0SA2AGhIHYmAOJgTiYEYAGEgF0A3HgLgoceNBABzdACIARrABmIVLAVNk02GFlEAFjpz5c61CXSEIpAB4kQqsphIBvPCW8lbMBDLy9jrwAJZgACaw9gDyquj2mGYAvmLmUXBEsGTUAEyCaX5SgYrIqlmo2mR6BsamaZbWtg5OLshunrg+vhL+0nIJIeFRsfGJKXhAA https://www.typescriptlang.org/play/?#code/MYewdgziA2CmB0w4E... If you click run there and look at the logged output, you’ll see: 1. The length remains the same after the delete statement 2. The items after index 2 keep their index 3. The for-of loop continues to iterate over index 2 (which now produces an undefined value on read)