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

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