Jeff King <peff@xxxxxxxx> writes:
> In preparation for callers constructing their own ref_array
> structs, let's move our own internal push operation into its
> own function.
>
> While we're at it, we can replace REALLOC_ARRAY() with
> ALLOC_GROW(), which should give the growth operation
> amortized linear complexity (as opposed to growing by one,
> which is potentially quadratic, though in-place realloc
> growth often makes this faster in practice).
Sorry, but I do not quite get the last part this paragraph. Up to
but not including ", though in-place..." I would understand as:
- With ALLOC_GROW(), we are explicit in that we are amortizing
the allocation cost by growing in exponential batches.
- With REALLOC_ARRAY(), we are telling the underlying
realloc(3) that it is OK to pretend that we grow by one, but
if that permission is literally followed, it could end up
quadratic.
So if you have really a bad realloc(3) implementation, switching
to use ALLOC_GROW() is an improvement.
But after that I am not sure what you are getting at. Do you mean
"In practice, a well-done realloc(3) does the amortizing internally
anyway, which makes it faster than the grow-by-one quadratic, so
this change may not make that much of a difference"? Or do you mean
"In practice, a well-done realloc(3) internally amortizes better
than we do manually, so this change may hurt performance"?
In either case, I think this splitting into a helper is obviously a
good move, and using ALLOC_GROW() is conceptually cleaner, as we use
it everywhere and tend to avoid realloc(3) just to add one item.
Other than that small confusion (not even a nit), three patches were
pleasant read. Thanks.
