Re: [PATCH 3/3] ref-filter: factor ref_array pushing into its own function

[Jeff King <peff@peff.net>]

On Mon, Apr 09, 2018 at 08:18:35AM +0900, Junio C Hamano wrote:

> Jeff King <peff@peff.net> 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.

Yes, that's the gist of what I was saying. Though it is not even
necessarily "a bad realloc". At some point you may hit heap segmentation
and need to copy (though I guess if that happens repeatedly then maybe
your realloc really _is_ bad ;) ).

> 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"?

The first. I couldn't measure any speedup on glibc, which makes me think
it's mostly doing in-place expansion.

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

Thanks. Please feel free to expand or clarify the commit message if that
helps.

-Peff