bug-gnulib
[Top][All Lists]
Advanced

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

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


From: Bruno Haible
Subject: Re: xalloc.h (x2nrealloc): Don't always double the buffer size.
Date: Fri, 2 Feb 2007 04:07:52 +0100
User-agent: KMail/1.5.4

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.

> -   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.

Bruno





reply via email to

[Prev in Thread] Current Thread [Next in Thread]