[PATCH] Dynamic growable arrays for internal use

[Paul Eggert]

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