Re: [PATCH v2 7/7] pack-objects: use mru list when iterating over packs

From: Jeff King <peff@peff.net>
Date: Aug 8, 2016, 16:51 UTC
Message-ID: <20160808165127.fvhnkcfsj4vif7iu@sigill.intra.peff.net>
In-Reply-To: <xmqq8tw7gr82.fsf@gitster.mtv.corp.google.com>

On Mon, Aug 08, 2016 at 09:28:29AM -0700, Junio C Hamano wrote:

Show 29 quoted lines

> Jeff King <peff@peff.net> writes:
> 
> > Here's a list of approaches I think we can use to fix this:
> >
> >   1. squelch the warning and ignore it. The downside here, besides not
> >      warning the user about true in-pack cycles, is that we have no
> >      opportunity to actually find a new delta (because we realize the
> >      problem only after the delta-compression phase).
> >
> >      My test repository is a bad packing of all of the forks of
> >      torvalds/linux, with 3600 packs. I'm happy to share it if anybody
> >      wants to see it, but note that it is 11GB.
> >
> >      The space overhead of the resulting pack in this case is ~3.2%
> >      (versus a pack generated by the original code, using the static
> >      pack order).  Which is really not that bad, but I'm sure there are
> >      more pathological cases (i.e., there were on the order of hundreds
> >      or maybe thousands of cycles that needed broken, out of about 15
> >      million total objects; but one could imagine the worst case as
> >      nr_of_objects/2).
> > ...
> >
> >     So I dunno. I really like the MRU approach if we can salvage it.
> 
> I think I share the same feeling.  As long as the chance is small
> enough that the pack reordering creates a new cycle, the resulting
> pack would not become too bloated by the last-ditch cycle breaking
> code and finding a replacement delta instead of inflating it may not
> be worth the trouble.

Let me see how complicated it is to do the cycle-detection earlier. It really shouldn't be that hard (we don't even need an auxiliary data structure; we can just smudge the index value like write_object does). I'm very curious to see the pack resulting pack size.

> It worries me a lot to lose the warning unconditionally, though.
> That's the (only) coal-mine canary that lets us notice a problem
> when we actually start hitting that last-ditch cycle breaking too
> often.

The dedicated cycle-detection will lose that warning, too (it doesn't touch that code, but it's effectively checking the same thing earlier).

I agree it's unfortunate to lose. On the other hand, it is being lost because we are correctly handling the cycles, and there is nothing to warn about. So it ceases to be a problem, and starts being a normal, acceptable thing.

-Peff