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

From: Junio C Hamano <gitster@pobox.com>
Date: Sep 10, 2024, 16:07 UTC
Message-ID: <xmqq4j6nlcfy.fsf@gitster.g>
In-Reply-To: <0e6dde0f-63e2-4db3-9225-9a8ca5e78eb3@gmail.com>

Derrick Stolee <stolee@gmail.com> writes:

Show 5 quoted lines

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

Show 8 quoted lines

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

;-).