Hacker News Reader

Comment by melvinroest | Hacker News Reader

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 :)

View on HN

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/ [2]: https://issues.chromium.org/issues/42202676 [3]: https://github.com/danbev/learning-v8/blob/master/notes/heap...

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)

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.

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

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?

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.

What are you doing with arrays that mutating them is maddening and has limited applications? Is this some kind of a cult?

> Is this some kind of a cult?

Yes, it’s called Functional Programming.

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).

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.

I would expect arrays to be immutable and list type not

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.

I wouldn't say go is exactly ultra new

Reply on news.ycombinator.com