Jeff King <peff@xxxxxxxx> 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
--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html