Re: [PATCH 2/3] commit-slab: avoid large realloc

From: Junio C Hamano <gitster@pobox.com>
Date: Apr 14, 2013, 18:51 UTC
Message-ID: <7vk3o554jn.fsf@alter.siamese.dyndns.org>
In-Reply-To: <20130414152842.GB1544@sigill.intra.peff.net>

Jeff King <peff@peff.net> writes:

Show 11 quoted lines

> On Sat, Apr 13, 2013 at 11:04:48PM -0700, Junio C Hamano wrote:
>
>> Instead of using a single "slab" and keep reallocating it as we find
>> that we need to deal with commits with larger values of commit->index,
>> make a "slab" an array of many "slab_piece"s. Each access may need
>> two levels of indirections, but we only need to reallocate the first
>> level array of pointers when we have to grow the table this way.
>
> 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.

Also "you can now take a pointer" you illustrated (but I snipped from here) is a good point.

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