On Mon, Apr 09, 2018 at 08:18:35AM +0900, Junio C Hamano wrote: > Jeff King <p...@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
