Re: [PATCH 0/6] PATH WALK I: The path-walk API

From: Junio C Hamano <gitster@pobox.com>
Date: Nov 11, 2024, 22:29 UTC
Message-ID: <xmqq1pzhbe19.fsf@gitster.g>
In-Reply-To: <20241111215502.GC5019@coredump.intra.peff.net>

Jeff King <peff@peff.net> writes:

Show 6 quoted lines

>> Yes.  Due to --depth limit, we need to break delta chains somewhere
>> anyway, and a rename boundary is just as good place as any other in
>> a sufficiently long chain.
>
> We don't necessarily have to break the chains due to depth limits,
> because they are not always linear. They can end up as bushy trees,

True. And being able to pair blobs before and after a rename will give us more candidates to place in a single bushy tree, so in that sense, with a short segment of history, it is understandable that the full-name hash fails to have as many candidates as the original hash gives us. But with sufficiently large number of blobs at the same path that are similar (i.e. not a "pushing a short segment of history", but an initial clone), splitting what could be one delta family into two delta families at the rename boundary is not too bad, as long as both halves have enough blobs to deltify against each other.

Show 27 quoted lines

> I'm not sure in practice how often we find these kinds of deltas. If you
> look at, say, all the deltas for "Makefile" in git.git like this:
>
>   git rev-list --objects --all --reflog --full-history -- Makefile |
>   perl -lne 'print $1 if /(.*) Makefile/' |
>   git cat-file --batch-check='%(objectsize:disk) %(objectname) %(deltabase)'
>
> my repo has 33 full copies (you can see non-deltas by grepping for
> "0{40}$" in the output) out of 4473 total. So it's not like we never
> break chains. But we can use graphviz to visualize it by piping the
> above through:
>
>   perl -alne '
>     BEGIN { print "digraph {" }
>     print "node_$F[1] [label=$F[0]]";
>     print "node_$F[1] -> node_$F[2]" if $F[2] !~ /^0+$/;
>     END { print "}" }
>   '
>
> and then piping it through "dot" to make an svg, or using an interactive
> viewer like "xdot" (the labels are the on-disk size of each object). I
> see a lot of wide parts of the graph in the output.
>
> Of course this may all depend on packing patterns, too. I did my
> investigations after running "git repack -adf" to generate what should
> be a pretty reasonable pack. You might see something different from
> incremental repacking over time.

That is very true. I forgot that we do things to encourage bushy delta-base selection. One thing I also am happy to see is the effect of our "clever" delta-base selection, where the algorithm does not blindly favor the delta-base that makes the resulting delta absolutely minimal, but takes the depth of the delta-base into account (i.e. a base at a much shallower depth is preferred over a base near the depth limit, even if it results in a slightly larger delta data).

> I'm not sure what any of this means for --path-walk, of course. ;)
> Ultimately we care about resulting size and time to compute, so if it
> can do better on those metrics then it doesn't matter what the graph
> looks like.

True, too. Another thing that we care about is the time to access data, and favoring shallow delta chain, even with the help of the in-core delta-base cache, has merit.

Thanks.