3 ms·

I'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 ago
Some 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 ago
  Disclaimer: 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 ago
    Do 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 ago
    I wouldn't say go is exactly ultra new
  - dchest 2y ago
    What 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 ago
        Hey 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 ago
    Sounds 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 ago
    I'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 ago
      I would expect arrays to be immutable and list type not
matharmin 2y ago
It'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 ago
  It 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 ago
    Reading 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.

melvinroest 2y ago

Some 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 ago
Disclaimer: 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 ago
  Do 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 ago
  I wouldn't say go is exactly ultra new
- dchest 2y ago
  What 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 ago
      Hey 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 ago
  Sounds 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 ago
  I'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 ago
    I would expect arrays to be immutable and list type not

matharmin 2y ago

It'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 ago
It 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 ago
  Reading 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.