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

[Junio C Hamano <gitster@pobox.com>]

Jeff King <peff@peff.net> writes:

>> 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.

> 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.