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

[Taylor Blau <me@ttaylorr.com>]

On Mon, Oct 28, 2024 at 03:46:11PM -0400, Derrick Stolee wrote:
> On 10/28/24 1:25 PM, Taylor Blau wrote:
> > On Mon, Oct 28, 2024 at 01:13:15PM -0400, Derrick Stolee wrote:
>
> > > You are correct that this is not compatible with those features as-is.
> > > _Maybe_ there is potential to integrate them in the future, but that
> > > would require better understanding of whether the new compression
> > > mechanism valuable in enough cases (final storage size or maybe even
> > > in repacking time).
> >
> > I think the bitmap thing is not too big of a hurdle. The .bitmap file is
> > the only spot we store name-hash values on-disk in the "hashcache"
> > extension.
> >
> > 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?

If so, a couple of thoughts:

  - You could consider storing the path information for each blob and
    tree object in the bitmap using a trie-like structure. This would
    give you enough information to reconstruct the path-walk order (I
    think) at read-time, but at significant cost in terms of the on-disk
    size of the .bitmap.

  - Alternatively, if you construct the bitmap from a pack or packs that
    were generated in path-walk order, then you could store a
    permutation between pack order and path-walk order in the bitmap
    itself.

  - Alternatively still: if the actual pack *order* were dictated solely
    by path-walk, then neither of these would be necessary.

That all said, I'm still not sure that there is a compatibility blocker
here. Is the goal is to ensure that packs generated with
--use-bitmap-index are still compact in the same way that they would be
with your new --path-walk option?

If so, I think matching the object order in a pack to the path walk
order would achieve that goal, since the chunks that you end up reusing
verbatim as a result of pack-reuse driven by the bitmap would already be
delta-ified according to the --path-walk rules, so the resulting pack
would appear similarly.

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.

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.

Thanks,
Taylor