Re: [PATCH 0/4] pack-objects: create new name-hash algorithm

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

Derrick Stolee <stolee@gmail.com> writes:

> The thing that surprised me is just how effective this is for the
> creation of large pack-files that include many versions of most
> files. The cross-path deltas have less of an effect here, and the
> benefits of avoiding name-hash collisions can be overwhelming in
> many cases.

Yes, "make sure we notice a file F moving from directory A to B" is
inherently optimized for short span of history, i.e. a smallish push
rather than a whole history clone, where the definition of
"smallish" is that even if you create optimal delta chains, the
length of these delta chains will not exceed the "--depth" option.

If the history you are pushing modified A/F twice, renamed it to B/F
(with or without modification at the same time), then modified B/F
twice more, you'd want to pack the 5-commit segment and having to
artificially cut the delta chain that can contain all of these 5
blobs into two at the renaming commit is a huge loss.

Compared to that, a whole history clone is a very different story,
as we will have to chomp delta chains at some depth anyway.  Before
the rename, it is reasonable to assume that A/F have evolved
incrementally for number of revisions, and after that rename it is
expected B/F will evolve incrementally for number of revisions
before it gets renamed again.  It is just the matter of choosing
where in that long stretch of content evolution we would cut the
delta chain, and the commit that renamed the path may just be a
good, if not absolute optimal, point.

So I do agree that this is an important case to optimize for.  At
some point, even when taking only the blobs at the same path as
delta base candidates, your true best base may be outside of the
--window in the list of candidates (sorted by size in decreasing
order), but at that point you would be increasing window to find
better delta base, not to skip unrelated blobs that happened to have
thrown into the same hash bucket due to the design that optimizes
for different case, so we can say that it is worth spending the
extra cycle and memory, if you need a larger window to gain even
better packing result.

> Funny you should say that, since the RFC I finally submitted [1]
> actually does just that. The --path-walk option changes the object
> walk to consider batches of objects based on their path, computes
> deltas among that batch, and then does the normal name-hash pass
> later. This seems to really strike the balance that you are
> looking for and solves the issues where small pushes need to stay
> small. It also fixes some problematic cases even when pushing a
> single commit.

;-).