Re: xalloc.h (x2nrealloc): Don't always double the buffer size.

[Jim Meyering]

Bruno Haible <address@hidden> wrote:
> Jim Meyering wrote:
>> I've just changed xalloc's x2nrealloc to do n = 3n/2, rather than n *= 2,
>
> Which means that the time needed for realloc() will grow by a factor of 1.7
> on average. If it matters - haven't measured it -, I would suggest to use
>    - n = 2*n for n < 1000000,
>    - n = 3*n/2 for n >= 1000000,
> so as to not penalize the frequent small allocations.

If you (or anyone) find a trend in applications where that slight
increase in the number of realloc calls makes a significant difference,
please let us know.  But bear in mind that having to *re*allocate is
relatively unusual.  Minimizing the cost of the much more frequent range
and overflow tests is important too.

>> -   In the following implementation, nonzero sizes are doubled so that
>> -   repeated reallocations have O(N log N) overall cost rather than
>> -   O(N**2) cost, but the specification for this function does not
>> -   guarantee that sizes are doubled.
>> +   In the following implementation, nonzero sizes are increased by a
>> +   factor of approximately 1.5 so that repeated reallocations have
>> +   O(N log N) overall cost rather than O(N**2) cost, but the
>> +   specification for this function does not guarantee that rate.
>
> How do you arrive at O(N log N) cost? I get
> O(N) + O(N/c) + O(N/c^2) + O(N/c^3) + ... = O(N) + O(log N) = O(N)
> where c is = 2 or = 1.5 respectively.

I didn't, but I should have noticed.  That comment was there before,
and I knew that changing a constant (c) would not affect big-O.

Thanks for the correction.