Hacker News Reader

Comment by lifthrasiir | Hacker News Reader

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

View on HN

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

Decreasing capacity wouldn't affect the theoretical complexity of algorithms using it - same concept as increasing capacity during push still being amortized O(1)

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

I'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_...

You have a good point. Unless JS exposes some API to directly control the capacity, we have to guess which use cases are more common and which use cases are fine to ignore. On the other hands though, JS's lack of capacity control means that developers are not conscious about the memory usage after all and JS engines have to do something about that anyway. Indeed, if you look at the actual bug [1], one commentator does mention exactly what I have said:

> This is a great idea! Both shift() and pop() can treat the elements array as a dequeue. A "shrink capacity to 1/2 when usage is <1/3" would give us O(1) amortized performance for shift() and pop(), while avoid edge cases where we keep shrinking/growing for alternating add/remove ops around the shrink/grow boundary.

[1] https://bugzilla.mozilla.org/show_bug.cgi?id=1348772

I don't quite understand how it avoids the case for code that pushes lots of stuff to a vector, then shifts its all out, and then does this again—which, to me, doesn't seem like an edge-case at all.

Do any languages automatically reduce vector size when elements are removed from it? If this is the first one, then arguably it would be a bit surprising behaviour.

I disagree entirely on the 'reasonable' implementation part. If something was that big the memory was already allocated, and it's not unlikely to grow again. Shifting memory/resources within a lifespan of a particular instance (likely used as a queue) to another resource (and staying unchanged afterwards) is a rare occurrence in practice.

Reply on news.ycombinator.com