This is the mail archive of the
libc-alpha@sourceware.org
mailing list for the glibc project.
Re: [PATCH] Dynamic growable arrays for internal use
- From: Paul Eggert <eggert at cs dot ucla dot edu>
- To: Carlos O'Donell <carlos at redhat dot com>, Florian Weimer <fweimer at redhat dot com>, GNU C Library <libc-alpha at sourceware dot org>
- Date: Sat, 20 May 2017 17:43:53 -0700
- Subject: Re: [PATCH] Dynamic growable arrays for internal use
- Authentication-results: sourceware.org; auth=none
- References: <edae68d6-998b-58a6-a8df-82703341da23@redhat.com> <ce479249-6362-6a58-ec9b-d6227ef99db9@redhat.com>
Carlos O'Donell wrote:
The dynamic array growth factor appears to be a value of 2, and that doesn't
match best practice nor academic literature. I would be happier with a growth
factor closer to 1.5.
For what it's worth, Gnulib (which has supported dynamically growabable arrays
for some time) generates the new size via "n += n / 2 + 1;" by default. This
guarantees growth even if N is zero, and approximates the growth factor of 1.5
that you're suggesting. (The code also checks for integer overflow of course.)
The caller can ask for a different amount of growth, if necessary.
Can we make the choice to have dynarray always heap allocated?
In Gnulib we've found it better to support initial buffers on the stack, as an
option. Commonly these initial buffers are already big enough, which is a
performance win in the typical case.
I dont like defaults for this interface. I think the user should
explicitly request a size or this should fail.
Why impose this requirement? In Gnulib the caller can specify an initial size,
but this is optional. The default initial size is chosen to be efficient for the
underlying malloc implementation. It would seem odd to require callers to know
this implementation detail.
As a general point, I suggest looking at Gnulib's lib/xalloc.h and lib/xmalloc.c
for ideas. It has many of the ideas of the proposal (including some type
safety). It's not as fancy as the proposal, but it does have the advantage of
widespread use and implementation experience.
http://git.savannah.gnu.org/cgit/gnulib.git/tree/lib/xalloc.h
http://git.savannah.gnu.org/cgit/gnulib.git/tree/lib/xmalloc.c