Re: [PATCH v2 00/17] pack-objects: add --path-walk option for better deltas

[Derrick Stolee <stolee@gmail.com>]

On 10/29/24 2:02 PM, Taylor Blau wrote:
 > On Mon, Oct 28, 2024 at 03:46:11PM -0400, Derrick Stolee wrote:
 >> On 10/28/24 1:25 PM, Taylor Blau wrote:
 >>> Unfortunately, there is no easy way to reuse the format of the existing
 >>> hashcache extension as-is to indicate to the reader whether they are
 >>> recording traditional name-hash values, or the new --path-walk hash
 >>> values.
 >>
 >> The --path-walk option does not mess with the name-hash. You're thinking
 >> of the --full-name-hash feature [1] that was pulled out due to a lack of
 >> interest (and better results with --path-walk).
 >>
 >> [1] https://lore.kernel.org/git/pull.1785.git.1725890210.gitgitgadget@gmail.com/
 >
 > Ah, gotcha. Thanks for clarifying.
 >
 > What is the incompatibility between the two, then? Is it just that
 > bitmaps give us the objects in pack- or pseudo-pack order, and we don't
 > have a way to permute that back into the order that --path-walk would
 > give us?

The incompatibility of reading bitmaps and using the path-walk API is
that the path-walk API does not check a bitmap to see if an object is
already discovered. Thus, it does not use the reachability information
from the bitmap at all and would parse commits and trees to find the
objects that should be in the pack-file.

It should also be worth noting that using something like 'git repack
--path-walk' does not mean that future 'git pack-objects' executions
from that packfile data need to use the --path-walk option. I expect
that it should be painless to write bitmaps on top of a packfile created
with 'git repack -adf --path-walk', but since most places doing so also
likely want delta islands, I have not explored this option thoroughly.

(Delta islands are their own challenge, since the path-walk API is not
spreading the reachability information across the objects it walks.
However, this could be remedied by doing a separate walk to identify
islands using the normal method. I believe Peff had an idea in that
direction in another thread. This requires some integration and testing
that I don't have the expertise to provide.)

 > If so, a couple of thoughts:
 > ...

Since the incompatibility is in a different direction, I don't think
these thoughts were relevant to the problem.

 > OTOH, the order in which we pack objects is extremely important to
 > performance as you no doubt are aware of. So changing that order to more
 > closely match the --path-walk option should be done with great care.

This is a place where I'm unsure about how the --path-walk option adjusts
the object order within the pack. The packing list gets resorted to match
the typical method, at least for how the delta compression window works.

This would be another good reason to consider the --path-walk option in
server environments very carefully. My patch series puts up guard rails
specifically because it makes no claim to be effective in all of the
dimensions that matter for those scenarios. Hopefully, others will be
motivated enough to determine if the compression that's possible with
this algorithm could be achieved in a way that is compatible with server
needs.

 > Anyway. All of that is to say that I want to better understand what does
 > and doesn't work together between bitmaps and path-walk. Given my
 > current understanding, it seems there are a couple of approaches to
 > unifying these two things together, so it would be nice to be able to
 > do so if possible.

I think this is an excellent opportunity for testing and debugging to
build up more intuition with how the path-walk API works. When I submit
the next version later tonight, the path-walk algorithm will be better
documented.

That said, I don't have any personal motivation to integrate the two
together, so I don't expect to be contributing that integration point
myself. I think that the results speak for themselves in the very
common environment of a Git client without bitmaps.

Thanks,
-Stolee