4 ms·

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

• manwe150 5y ago
  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-fb625ea37f59dbae7d0f5e5f7b70b887b9785a354179fab07eb4d2083fdb51b4R766-R772 https://github.com/JuliaLang/julia/pull/40453/files#diff-fb6...
  • _dain_ 5y ago
    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/listobject.c#L55 https://github.com/python/cpython/blob/3.7/Objects/listobjec...
• anamax 5y ago
  Any multiplier > 1 is enough to keep a "grow by constant each iteration" loop from becoming quadratic.