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

[Derrick Stolee <stolee@gmail.com>]

On 11/4/24 7:11 PM, Junio C Hamano wrote:
> Jeff King <peff@peff.net> writes:
> 
>> On Mon, Nov 04, 2024 at 10:48:49AM -0500, Derrick Stolee wrote:
>>> I disagree that all environments will prefer the --full-name-hash. I'm
>>> currently repeating the performance tests right now, and I've added one.
>>> The issues are:
>>>
>>>   1. The --full-name-hash approach sometimes leads to a larger pack when
>>>      using "git push" on the client, especially when the name-hash is
>>>      already effective for compressing across paths.
>>
>> That's interesting. I wonder which cases get worse, and if a larger
>> window size might help. I.e., presumably we are pushing the candidates
>> further away in the sorted delta list.

I think the cases that make things get worse with --full-name-hash are:

   1. The presence of renames, partitioning objects that used to fit into
      the same bucket (in the case of directory renames).

   2. Some standard kinds of files may appear several times across the
      tree but do not change very often and are similar across path.

   3. Common patterns across similar file types, such as similar includes
      in .c and .h files or other kinds of boilerplate in different
      languages.

A larger window size will always expand the range of possible deltas, at
a cost to the time taken to compute the deltas. My first experiment in
these repositories was to increase the window size to 250 (from the default
10). This caused a very slow repack, but the repositories shrunk.

For example, the big Javascript monorepo that repacked to ~100 GB with
default settings would repack to ~30 GB with --window=250. This was an
indicator that delta compression would work if we can find the right pairs
to use for deltas.

The point of the two strategies (--full-name-hash and --path-walk) is
about putting objects close to each other in better ways than the name
hash sort.

>>>   2. A depth 1 shallow clone cannot use previous versions of a path, so
>>>      those situations will want to use the normal name hash. This can be
>>>      accomplished simply by disabling the --full-name-hash option when
>>>      the --shallow option is present; a more detailed version could be
>>>      used to check for a large depth before disabling it. This case also
>>>      disables bitmaps, so that isn't something to worry about.
>>
>> I'm not sure why a larger hash would be worse in a shallow clone. As you
>> note, with only one version of each path the name-similarity heuristic
>> is not likely to buy you much. But I'd have thought that would be true
>> for the existing name hash as well as a longer one. Maybe this is the
>> "over-emphasizing" case.

I'm confused by your wording of "larger hash" because the hash size
is the exact same: 32 bits. It's just that the --full-name-hash option
has fewer collisions by abandoning the hope of locality.

In a depth 1 shallow clone, there are no repeated paths, so any hash
collisions are true collisions instead of good candidates for deltas.
The full name hash is essentially random, so the delta compression
algorithm basically says:

   1. Sort by type.
   2. Within each type, sort the objects randomly.

With that sort, the delta compression scan is less effective than the
standard name hash.

> I too am curious to hear Derrick explain the above points and what
> was learned from the performance tests.  The original hash was
> designed to place files that are renamed across directories closer
> to each other in the list sorted by the name hash, so a/Makefile and
> b/Makefile would likely be treated as delta-base candidates while
> foo/bar.c and bar/foo.c are treated as unrelated things.  A push
> of a handful of commits that rename paths would likely place the
> rename source of older commits and rename destination of newer
> commits into the same delta chain, even with a smaller delta window.

> In such a history, uniformly-distributed-without-regard-to-renames
> hash is likely to make them into two distinct delta chains, leading
> to less optimal delta-base selection.

Yes. This is the downside of the --full-name-hash compared to the
standard name hash. When repacking an entire repository, the effect
of these renames is typically not important in the long run as it's
basically a single break in the delta chain. The downside comes in
when doing a small fetch or push where the rename has more impact.

The --path-walk approach does not suffer from this problem because
it has a second pass that sorts by the name hash and looks for
better deltas than the ones that already exist. Thus, it gets the
best of both worlds.

The performance impact of the two passes of the --path-walk
approach is interesting, as you'd typically expect this to always
be slower. However:

  1. The delta compression within each batch only compares the
     objects within that batch. We do not compare these objects to
     unrelated objects, which can be expensive and wasteful. This
     also means that small batches may even be smaller than the
     delta window, reducing the number of comparisons.

  2. In the second pass, the delta calculation can short-circuit if
     the computed delta would be larger than the current-best delta.
     Thus, the good deltas from the first pass make the second pass
     faster.

> A whole-repository packing, or a large push or fetch, of the same
> history with renamed files are affected a lot less by such negative
> effects of full-name hash.  When generating a pack with more commits
> than the "--window", use of the original hash would mean blobs from
> paths that share similar names (e.g., "Makefile"s everywhere in the
> directory hierarchy) are placed close to each other, but full-name
> hash will likely group the blobs from exactly the same path and
> nothing else together, and the resulting delta-chain for identical
> (and not similar) paths would be sufficiently long.  A long delta
> chain has to be broken into multiple chains _anyway_ due to finite
> "--depth" setting, so placing blobs from each path into its own
> (initial) delta chain, completely ignoring renamed paths, would
> likely to give us long enough (initial) delta chain to be split at
> the depth limit.
> 
> It would lead to a good delta-base selection with smaller window
> size quite efficiently with full-name hash.>
> I think a full-name hash forces a single-commit pack of a wide tree
> to give up on deltified blobs, but with the original hash, at least
> similar and common files (e.g. Makefile and COPYING) would sit close
> together in the delta queue and can be deltified with each other,
> which may be where the inefficiency comes from when full-name hash
> is used.

Yes, this is a good summary of why this works for the data
efficiency in long histories. Your earlier observations are why
the full-name hash has demonstrated issues with smaller time scales.

These numbers are carefully detailed in the performance tests in
the refreshed series [1]. The series also has a way to disable the
full-name hash when serving a shallow clone for this reason.

[1] https://lore.kernel.org/git/pull.1823.git.1730775907.gitgitgadget@gmail.com/

Thanks,
-Stolee