lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]




On Thu, Jul 21, 2022 at 1:36 PM Adam Higerd <chighland@gmail.com> wrote:
The idea here is that while exponential growth is provably optimal for minimizing the number of reallocations, linear growth minimizes overallocation, and there comes a time where overallocation becomes a bigger problem than reallocation.


The time complexity of growing the buffer becomes quadratic once you hit the linear growth bound, the whole reason for the doubling is to keep the time complexity linear. By the time you've built a 4GB string out of small chunks (smaller than 1MB) you'll have copied the growing buffer over 4000 times, this adds up to many terabytes of memory to memory copies. With the doubling strategy you only copy twice the size of the maximum string length, or 8GB for a 4GB string.

I'd suggest growing the buffer by not doubling once you hit a certain threshold, but by growing the buffer by 20% or so, it will be slower but the behavior is still linear and the amount of unused space is lower.

--