Re: [PATCH 2/3] commit-slab: avoid large realloc
- From
Jeff King <peff@peff.net>
- Date
- Apr 14, 2013, 19:19 UTC
- Message-ID
- <20130414191947.GB4599@sigill.intra.peff.net>
- In-Reply-To
- <7vk3o554jn.fsf@alter.siamese.dyndns.org>
On Sun, Apr 14, 2013 at 11:51:40AM -0700, Junio C Hamano wrote:
Show 8 quoted lines
> > I don't know if shrinking the size of the realloc is all that big a > > deal. We are doubling, so the allocation cost is already amortized > > constant time. > > I was more disturbed about copying the actual bytes. One of the > envisioned use of the mechanism is to give us unbound number of flag > bits to paint the history, and also this could be later used to > store larger structures per commit.
Right; your solution does lower the constant factor. I just don't know that it matters all that much, since the allocations are so few (i.e., log2(N) to get to N items). And you are hurting the "hot path" of every access of the flags to do it (by introducing the extra division and indirection). Probably the extra work on lookup doesn't matter on modern processors due to pipelining. I'd like to measure a few cases to be sure, but I probably won't get to it today.
> Also "you can now take a pointer" you illustrated (but I snipped > from here) is a good point.
Yeah, assuming the timings are equal, I'd take your solution on that principle alone.
Show 19 quoted lines
> >> struct commit_slab {
> >> - int *buf;
> >> - int alloc;
> >> + int piece_size;
> >> + int piece_count;
> >> + struct commit_slab_piece **piece;
> >> };
> >
> > Is there a reason to make piece_size a struct member? It must be
> > constant after any pieces are allocated. Is the intent that callers
> > could do:
> >
> > slab_init(&s);
> > /* I know ahead of time we are going to need N of these. */
> > s.piece_size = n;
>
> The piece_size (later slab_size) is to hold the number of commits
> each slice (i.e. the piece of memory s->slab[nth_slab] points at)
> handles.Yes, but isn't that a constant:
(512*1024-32) / sizeof(struct commit_slab_piece)
Leaving it as such lets the compiler optimize better, and is safe from anybody changing it at runtime. But I think the answer to my question is "yes, that would be the best thing for patch 2, but patch 3 will allow a run-time stride parameter anyway". Correct?
-Peff