From: Eric Wong <e@80x24.org>
Date: Thu, 26 May 2016 08:02:36 GMT
Subject: Re: [RFC] fast-import: invalidate pack_id references after loosening
Message-ID: <20160526080236.GA27652@dcvr.yhbt.net>
In-Reply-To: <20160525230913.GB2634@sigill.intra.peff.net>

Jeff King <peff@peff.net> wrote:
> On Wed, May 25, 2016 at 10:54:02PM +0000, Eric Wong wrote:
> > +	for (h = 0; h < ARRAY_SIZE(object_table); h++) {
> > +		struct object_entry *e;
> > +
> > +		for (e = object_table[h]; e; e = e->next)
> > +			if (e->pack_id == id)
> > +				e->pack_id = MAX_PACK_ID;
> > +	}

<snip>

> This looks pretty straightforward. I do notice that we never shrink the
> number of items in the object table when checkpointing, and so our
> linear walk will grow ever larger. So if one were to checkpoint every
> k-th object, it makes the whole operation quadratic in the number of
> objects (actually, O(n^2/k) but k is a constant).

Good point, I'll work on a separate patch to fix it.

> That's probably OK in practice, as I think the actual pack-write already
> does a linear walk of the object table to generate the pack index. So
> presumably nobody checkpoints often enough for it to be a problem. And
> the solution would be to keep a separate list of pointers to objects for
> the current pack-id, which would trivially fix both this case and the
> one in create_index().  So we can punt on it until somebody actually
> runs into it, I think.

I might checkpoint that much and run into the problem soon :)
Too tired now; maybe in a day or two I'll be able to make sense
of C again :x