Hacker News Reader

Comment by fearthetelomere | Hacker News Reader

>- 2 is not the best growth factor because it makes it harder for the memory allocator to reuse memory. More modern implementations use smaller growth factors: https://en.wikipedia.org/wiki/Dynamic_array#Growth_factor

I've often wondered about this, so I'm curious to learn more. I agree in principle we should be more clever to ensure we have better memory use. However, half the implementations in the list you've linked use a growth factor of 2, so I'm confused about your point.

If it's not the best, what is? Do you know why these implementations opt for 2 if it's not the best choice?

View on HN

The better memory usage argument is not as one sided as it may appear. The issue related to using a growth factor of 2 appear when you have a single very big array, but for many smaller ones it's not really an issue. Meanwhile allocators generally tend to like power of 2 sizes, and non-2 growth factors produce non-power of 2 sizes. Some data structures are also easier to implement when the size is a power of 2 because you can efficiently wrap around by using bitwise operations rather than an expensive remainer.

> The issue related to using a growth factor of 2 appear when you have a single very big array

And a linear coalescing allocator of which that collection is essentially the only user.

That is, the allocator needs to be a single bytes array, and it needs to be able to reuse and merge freed allocations, and there can’t be other objects being allocated between your collection’s allocations (or they need to be freed before your collection needs to realloc).

> Do you know why these implementations opt for 2 if it's not the best choice?

Probably a mix of simplicity, not knowing or not caring. Most software is not optimal.

> If it's not the best, what is?

In theory, the best value is a bit less than the golden ratio, so 1.5 is quite good.

https://archive.li/Z2R8w#selection-119.7-135.119

In practice, unknown factors can influence the result, so it is best to benchmark your code and try a bunch of values until you find the fastest configuration.

That theoretical result of the golden ratio is completely entirely useless for any practical scenario, and, even for its extremely-contrived scenario where the only allocations ever happening are from a single array being expanded, and using an extremely dumb allocator, it's just optimizing memory usage, not performance.

Amusingly, it looks at Java, which typically uses pointer bumping for the allocator and can do compacting GC, making the argument entirely meaningless.

IIRC libstdc++ benchmarked the golden ratio and found it worse for the loads they were interested in, so they stuck with a growth factor of 2.

Reply on news.ycombinator.com