Re: [PATCH] Dynamic growable arrays for internal use

[Carlos O'Donell <carlos at redhat dot com>]

On 05/20/2017 08:43 PM, Paul Eggert wrote:
> 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.

The growth factor is related to the underlying storage being used by 
the dynamic array. If the storage had such properties that the array
could be grown in-place and to any size with zero cost, then the growth
could be incredibly small and size kept optimal. Since no underlying storage
has those properties at all times we choose a growth factor that maps to the
properties that are present. Here, those properties are a function
of the underlying system allocator, how it calls mmap, when, how often,
and the costs associated with it. In general I'm surprised to see that 1.5
is a universally good constant, then again, most OS have similar subsystems
when it comes to allocators and virtual memory.

I don't know that having the caller ask for different growth is going to be
initially useful in glibc so I'm not going to ask for this in the API.

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

OK. Thanks for the data point here.

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

I see your point. Having the caller convey that no information is relevant
in the context allows the implementation to choose something optimal given
the backing store. And we have some use cases like this in the loader.
At most we know we have say one link map, but how many more there are after
is completely unknown (unless we had statistical data to guide us).
 
> 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

Before I look...

What license do these files have?

-- 
Cheers,
Carlos.