Hacker News new | ask | show | jobs
by scaramanga 1567 days ago
Power of two reallocs are usually there to prevent append in a loop from becoming accidentally quadratic so I guess it's either a bug or a feature depending on if you're going to do that.
2 comments

As long as there is a non-zero multiplier, it does not matter the size of the constant factor, and it does not even need to be constant. I spent a while recently looking at the shape of this non-typical allocation growth curve, which ended up going with `n₁ = n₀ + 4n₀^(7/8) + n₀/8` using only integer math:

    // compute maxsize = maxsize + 4*maxsize^(7/8) + maxsize/8
    // for small n, we grow faster than O(n)
    // for large n, we grow at O(n/8)
    // and as we reach O(memory) for memory>>1MB,
    // this means we end by adding about 10% of memory each time
And was graphed, discussed, and approved here:

https://github.com/JuliaLang/julia/pull/40453/files#diff-fb6...

Python is similar[1]

>The growth pattern is: 0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...

https://github.com/python/cpython/blob/3.7/Objects/listobjec...

Any multiplier > 1 is enough to keep a "grow by constant each iteration" loop from becoming quadratic.