Re: [PATCH v3 0/2] pack-objects mru

From: Junio C Hamano <gitster@pobox.com>
Date: Aug 10, 2016, 16:47 UTC
Message-ID: <xmqqbn107epz.fsf@gitster.mtv.corp.google.com>
In-Reply-To: <20160810115206.l57qpehpabthnl6c@sigill.intra.peff.net>

Jeff King <peff@peff.net> writes:

Show 6 quoted lines

>> This is not new with this change, but I am not quite sure what in
>> the current code prevents us from busting the delta limit for reused
>> ones, though.
>
> I think in the current code you are limited by the depth you might find
> in a single existing pack (since we never reuse cross-pack deltas).

Sorry for going deeper in the tangent, but I vaguely recall raising it long time ago as a potential issue that delta reuse out of an original pack created with deep delta chain may bust a delta chain limit when repacking with shorter delta chain limit; I just do not remember where that discussion went (i.e. decided to be a non-issue? we added code to avoid it? etc.)

Show 13 quoted lines

> However, I think with cross-pack deltas, you could have a situation
> like:
>
>   pack 1: A -> B -> C
>   pack 2: C -> D -> E
>
> and pick A and B from the first pack, and C, D, and E from the second.
> Then you end up with:
>
>   A -> B -> C -> D -> E
>
> in the output. IOW, I think the absolute worst case chain is the
> max_depth times the number of packs.

Also if pack1 and pack2 were created with depth limit of 3 and we are repacking with depth limit of 2, then we are busting the limit already with or without cross-pack chaining, I would think.

> I'm not sure how much we should be worried about it. We could fill in
> the depth values when adding a reused delta, but I don't think we have
> the number handy; we'd have to actually walk the chain (though with
> delta-base-offset, that is reasonably cheap).

True. It is something we may want to keep back in our mind and revisit later. It is definitely not a low-hanging fruit, but something that should go to the leftover-bits list.

Show 6 quoted lines

> The second patch is the same as before, though I tweaked the commit
> message a bit, so please replace what is at the tip of
> jk/pack-objects-optim-mru.
>
>   [1/2]: pack-objects: break delta cycles before delta-search phase
>   [2/2]: pack-objects: use mru list when iterating over packs

Thanks.