Re: [Bug-gnulib] checking for overflow

[Paul Eggert]

Jim Meyering <address@hidden> writes:

> Doubling is fine for small sizes, but becomes unreasonable beyond
> a certain point.  If an application is using a 100MB-buffer and needs to
> append a few kilobytes, doubling the buffer size sounds like overkill.

There is an argument for doubling the buffer size, though: it results
in O(N log N) behavior for large N.  If we simply add a constant K to
the size each time we realloc, we get O(N**2) behavior, because
realloc in general needs to copy the buffer O(N) times.

>   N += MIN (N + 10, 4 * 1024 * 1024);
>   (but with overflow-checking, of course)

There may be applications for which it's important to not falsely
report a memory overflow when allocating (say) 3/4 of SIZE_MAX would
have succeeded, and where we don't know ahead of time how big the
buffer needs to be.  However, I suspect these cases are rare or even
nonexistent, and so we needn't worry about it now.

If we do need to handle such a case in the future, we should use
binary search if the largest allocatable size lies between SIZE_MAX/2
and SIZE_MAX, so that the program doesn't have quadratic behavior.
(Ouch.  I hope this never comes up....)