On Sun, Oct 20, 2024 at 01:43:13PM +0000, Derrick Stolee via GitGitGadget wrote:
> Updates in v2
> =============
>
> I'm sending this v2 to request some review feedback on the series. I'm sorry
> it's so long.
>
> There are two updates in this version:
>
>  * Fixed a performance issue in the presence of many annotated tags. This is
>    caught by p5313 when run on a repo with 10,000+ annotated tags.
>  * The Scalar config was previously wrong and should be pack.usePathWalk,
>    not push.usePathWalk.

Thanks. I queued the new round. As an aside, I would like to find the
time to review this series in depth, but haven't been able to do so
while also trying to keep up with the volume of the rest of the list.

I know that this topic was split out of a larger one. It may be worth
seeing if there is a way to split this topic out into multiple series
that are more easily review-able, but still sensible on their own.

I haven't looked in enough depth to know myself whether such a cut
exists, but it is worth thinking about if you haven't done so already.

Thanks,
Taylor

On 10/21/24 5:43 PM, Taylor Blau wrote:
> On Sun, Oct 20, 2024 at 01:43:13PM +0000, Derrick Stolee via GitGitGadget wrote:
>> Updates in v2
>> =============
>>
>> I'm sending this v2 to request some review feedback on the series. I'm sorry
>> it's so long.
>>
>> There are two updates in this version:
>>
>>   * Fixed a performance issue in the presence of many annotated tags. This is
>>     caught by p5313 when run on a repo with 10,000+ annotated tags.
>>   * The Scalar config was previously wrong and should be pack.usePathWalk,
>>     not push.usePathWalk.
> > Thanks. I queued the new round. As an aside, I would like to find the
> time to review this series in depth, but haven't been able to do so
> while also trying to keep up with the volume of the rest of the list.
> > I know that this topic was split out of a larger one. It may be worth
> seeing if there is a way to split this topic out into multiple series
> that are more easily review-able, but still sensible on their own.

I'll see what I can do. I needed to re-roll after discovering an issue
when trying to integrate the algorithm with shallow clones. The solution
ends up simplifying the code, which is nice.

> I haven't looked in enough depth to know myself whether such a cut
> exists, but it is worth thinking about if you haven't done so already.

In the current series, there's a natural cut between patches 1-4
and the rest, if we want to put the API in without a non-test consumer.

I could also split out the 'git repack' changes into a third series.

Finally, the threading implementation could be done separately, but I
think it's not complicated enough to leave out from the first version
of the --path-walk option in 'git pack-objects'.

Thanks,
-Stolee

On Thu, Oct 24, 2024 at 09:29:02AM -0400, Derrick Stolee wrote:
> > I know that this topic was split out of a larger one. It may be worth
> > seeing if there is a way to split this topic out into multiple series
> > that are more easily review-able, but still sensible on their own.
>
> I'll see what I can do. I needed to re-roll after discovering an issue
> when trying to integrate the algorithm with shallow clones. The solution
> ends up simplifying the code, which is nice.

It's always nice when that happens :-).

Should we avoid reviewing the current round in anticipation of a
somewhat restructured series, or would you like us to review the current
round as well?

> > I haven't looked in enough depth to know myself whether such a cut
> > exists, but it is worth thinking about if you haven't done so already.
>
> In the current series, there's a natural cut between patches 1-4
> and the rest, if we want to put the API in without a non-test consumer.
>
> I could also split out the 'git repack' changes into a third series.
>
> Finally, the threading implementation could be done separately, but I
> think it's not complicated enough to leave out from the first version
> of the --path-walk option in 'git pack-objects'.

I'd suggest erring on the side of more smaller series rather than a
single large one. If you feel like there are cut points where we can
review them in isolation and still see some benefit, or at least
clearly how they each fit into the larger puzzle, I think that is worth
doing.

But I trust your judgement here, so if you think that the series is best
reviewed as a whole, then that's fine too. Just my $.02 :-).

Thanks,
Taylor

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

On Mon, Oct 28, 2024 at 12:54:04PM -0700, Jonathan Tan wrote:
> "Derrick Stolee via GitGitGadget" <gitgitgadget@gmail.com> writes:
> > This new walk is incompatible with some features and is ignored by
> > others:
> >
> >  * Object filters are not currently integrated with the path-walk API,
> >    such as sparse-checkout or tree depth. A blobless packfile could be
> >    integrated easily, but that is deferred for later.
> >
> >  * Server-focused features such as delta islands, shallow packs, and
> >    using a bitmap index are incompatible with the path-walk API.
> >
> >  * The path walk API is only compatible with the --revs option, not
> >    taking object lists or pack lists over stdin. These alternative ways
> >    to specify the objects currently ignores the --path-walk option
> >    without even a warning.
>
> It might be better to declare --path-walk as "internal use only" and
> only supporting what send-pack.c (used by "git push") and "git repack"
> needs. (From this list, it seems that there is a lot of incompatibility,
> some of which can happen without a warning to the user, so it sounds
> better to be up-front and say that we only support what send-pack.c
> needs. This also makes reviewing easier, as we don't have to think about
> the possible interactions with every other rev-list feature - only what
> is used by send-pack.c.)

Is the thinking there that we care mostly about 'git push' and 'git
repack' on the client-side?

I don't think it's unreasonable necessarily, but I would add that
client-side users definitely do use bitmaps (though not delta islands),
either when working in a bare repository (where bitmaps are the default)
or when using 'git gc' (and/or through 'git maintenance') when
'repack.writeBitmaps' is enabled.

So I think the approach here would be to limit it to some cases of
client side behavior, but we should keep in mind that it will not cover
all cases.

My feeling is that it would be nice to pull on the incompatibility
string a little more and see if we can't make the two work together
without too much effort.

Thanks,
Taylor

Taylor Blau <me@ttaylorr.com> writes:
> Is the thinking there that we care mostly about 'git push' and 'git
> repack' on the client-side?

I would go further - for the initial patch set, we should only care
about "git push" on the client side. Stolee said [1] that the "primary
motivation for this feature is its use to shrink the packfile created
by 'git push' when there are many name-hash collisions", and in thinking
about how to reduce the patch set for easier review, I thought that to
be a good scope.

Subsequent patch set(s) can implement "git repack", useful for both
client and server.

[1] https://lore.kernel.org/git/pull.1813.v2.git.1729431810.gitgitgadget@gmail.com/

> I don't think it's unreasonable necessarily, but I would add that
> client-side users definitely do use bitmaps (though not delta islands),
> either when working in a bare repository (where bitmaps are the default)
> or when using 'git gc' (and/or through 'git maintenance') when
> 'repack.writeBitmaps' is enabled.

I was thinking that a typical use case would be to create the commits
(using the tool Stolee mentioned, "beachball") and then immediately push
them. In this case, I don't think there would be much opportunity for
a bitmap write to be triggered, meaning that the pushed commits are not
covered by bitmaps.

But in any case, this was motivated by a desire to reduce the patch set
- I don't have a fundamental objection to including support for bitmaps
in the first patch set.

> So I think the approach here would be to limit it to some cases of
> client side behavior, but we should keep in mind that it will not cover
> all cases.

Yeah, that was my approach too.

> My feeling is that it would be nice to pull on the incompatibility
> string a little more and see if we can't make the two work together
> without too much effort.
> 
> Thanks,
> Taylor

By incompatibility, do you mean the incompatibility between bitmaps
and the overall --path-walk feature as implemented collectively by the
patches in Stolee's patch set? If so, I suspect that we will need a
parallel code path that takes in the "want" and "uninteresting" commits
and emits the list of objects (possibly before sorting the objects by
path hash), much like in builtin/pack-objects.c, so I think there will
be some effort involved in making the two work together.

On Tue, Oct 29, 2024 at 02:36:57PM -0700, Jonathan Tan wrote:
> By incompatibility, do you mean the incompatibility between bitmaps
> and the overall --path-walk feature as implemented collectively by the
> patches in Stolee's patch set? If so, I suspect that we will need a
> parallel code path that takes in the "want" and "uninteresting" commits
> and emits the list of objects (possibly before sorting the objects by
> path hash), much like in builtin/pack-objects.c, so I think there will
> be some effort involved in making the two work together.

I am not sure yet, in all honesty, because I haven't had enough time to
spend yet reviewing these patches to have anything intelligent to say.

Thanks,
Taylor

On 10/29/24 6:16 PM, Taylor Blau wrote:
> On Tue, Oct 29, 2024 at 02:36:57PM -0700, Jonathan Tan wrote:
>> By incompatibility, do you mean the incompatibility between bitmaps
>> and the overall --path-walk feature as implemented collectively by the
>> patches in Stolee's patch set? If so, I suspect that we will need a
>> parallel code path that takes in the "want" and "uninteresting" commits
>> and emits the list of objects (possibly before sorting the objects by
>> path hash), much like in builtin/pack-objects.c, so I think there will
>> be some effort involved in making the two work together.
> > I am not sure yet, in all honesty, because I haven't had enough time to
> spend yet reviewing these patches to have anything intelligent to say.

I think that the --path-walk option is fundamentally incompatible with
the --use-bitmap-index option (using reachability bitmaps to reduce how
many objects we parse to discover reachability) but is not necessarily
incompatible with writing bitmaps. But it would require testing to be
sure that there are no surprises due to something like an object order
changing or something like that.

The feature is also not currently integrated with delta islands, so
that would need integration and testing to make sure things are
grouped together and delta chains go in the right direction.

These things may be something possible to overcome in the future, but
the lack of current integration points and testing makes me want to
leave this version with guard rails that prevent users from getting
into a bind.

Thanks,
-Stolee

On 10/28/24 3:54 PM, Jonathan Tan wrote:
> "Derrick Stolee via GitGitGadget" <gitgitgadget@gmail.com> writes:
>> This new walk is incompatible with some features and is ignored by
>> others:
>>
>>   * Object filters are not currently integrated with the path-walk API,
>>     such as sparse-checkout or tree depth. A blobless packfile could be
>>     integrated easily, but that is deferred for later.
>>
>>   * Server-focused features such as delta islands, shallow packs, and
>>     using a bitmap index are incompatible with the path-walk API.
>>
>>   * The path walk API is only compatible with the --revs option, not
>>     taking object lists or pack lists over stdin. These alternative ways
>>     to specify the objects currently ignores the --path-walk option
>>     without even a warning.
> > It might be better to declare --path-walk as "internal use only" and
> only supporting what send-pack.c (used by "git push") and "git repack"
> needs. (From this list, it seems that there is a lot of incompatibility,
> some of which can happen without a warning to the user, so it sounds
> better to be up-front and say that we only support what send-pack.c
> needs. This also makes reviewing easier, as we don't have to think about
> the possible interactions with every other rev-list feature - only what
> is used by send-pack.c.)

I do wonder what the value of doing this would be. I consider 'gitpack-objects' to already be a plumbing command, so marking any option
as "internal use only" seems like overkill. It takes effort to combine
the options carefully for the right effect. The tests in p5313 are not
terribly simple, such as needing --no-reuse-delta to guarantee we are
using the desired delta algorithm.

> Also from a reviewer perspective, it might be better to restrict this
> patch set to what send-pack.c needs and leave "git repack" for a future
> patch set. This means that we would not need features such as blob
> and tree exclusions, and possibly not even bitmap use or delta reuse
> (assuming that the user would typically push recently-created objects
> that have not been repacked).

While I can understand that as being a potential place to split the
patch series, the integration to add 'git repack --path-walk' is actually
very simple. Repacking "everything" needs to happen to be able to push a
repo to an empty remote, after all.

There are some subtleties around indexed objects, reflogs, and the like
that add some complexity, but they also are handled in the path-walk API
layer. Some of that complexity was helpful to know about during repack
tests.

Finally, the 'git repack --path-walk' use case is a great one for
demonstrating the benefits to threading the 'git pack-objects
--path-walk' algorithm.

>> +		/* Skip objects that do not exist locally. */
>> +		if (exclude_promisor_objects &&
>> +		    oid_object_info_extended(the_repository, oid, &oi,
>> +					     OBJECT_INFO_FOR_PREFETCH) < 0)
>> +			continue;
> > This functionality is typically triggered by --missing=allow;
> --exclude_promisor_objects means (among other things) that we allow
> a missing link only if that object is known to be a promisor object
> (because another promisor object refers to it) (see Documentation/
> rev-list-options.txt, and also get_reference() and elsewhere in
> revision.c - notice how is_promisor_object() is paired with it)
> > Having said that, we should probably just fail outright on missing
> objects, whether or not we have exclude_promisor_objects. If we have
> computed that we need to push an object, that object needs to exist.
> (Same for repack.)

I think that this is not a reasonable assumption that a hard fail
should be expected. Someone could create a blobless clone with a
sparse-checkout and then add a new file outside their sparse-checkout
without ever having the previous version downloaded.

When pushing, they won't be able to use the previous version as a
delta base, but they would certainly be confused about an object
being downloaded during 'git push'.

While the example I bring up is somewhat contrived, I can easily
imagine cases where missing objects are part of the commit boundary
and could be marked as UNINTERESTING but would still be sent in the
batch to be considered as a delta base.

Thanks,
-Stolee

On 10/29/24 2:07 PM, Taylor Blau wrote:
> On Mon, Oct 28, 2024 at 12:54:04PM -0700, Jonathan Tan wrote:

> Is the thinking there that we care mostly about 'git push' and 'git
> repack' on the client-side?
> > I don't think it's unreasonable necessarily, but I would add that
> client-side users definitely do use bitmaps (though not delta islands),
> either when working in a bare repository (where bitmaps are the default)
> or when using 'git gc' (and/or through 'git maintenance') when
> 'repack.writeBitmaps' is enabled.
I suppose some users do use bitmaps, but in my experience, client-side
pushes are slower with bitmaps because a typical target branch is
faster to compute by doing a commit walk, at least when the bitmaps are
older than the new commits in the topic branch. This may be outdated by
now, as it has been a few years since I did a client-side test of
bitmaps.

Thanks,
-Stolee

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

On Wed, Oct 30, 2024 at 10:14:08PM -0400, Derrick Stolee wrote:
> On 10/29/24 2:07 PM, Taylor Blau wrote:
> > On Mon, Oct 28, 2024 at 12:54:04PM -0700, Jonathan Tan wrote:
>
> > Is the thinking there that we care mostly about 'git push' and 'git
> > repack' on the client-side?
> >
> > I don't think it's unreasonable necessarily, but I would add that
> > client-side users definitely do use bitmaps (though not delta islands),
> > either when working in a bare repository (where bitmaps are the default)
> > or when using 'git gc' (and/or through 'git maintenance') when
> > 'repack.writeBitmaps' is enabled.
> I suppose some users do use bitmaps, but in my experience, client-side
> pushes are slower with bitmaps because a typical target branch is
> faster to compute by doing a commit walk, at least when the bitmaps are
> older than the new commits in the topic branch. This may be outdated by
> now, as it has been a few years since I did a client-side test of
> bitmaps.

All true, though it's hard to estimate the size of "some". I share your
intuition that bitmaps are often a drag on performance for the
client-side because doing a pure commit walk is often faster, especially
if the client has a reasonably up-to-date commit graph.

Thanks,
Taylor

On Wed, Oct 30, 2024 at 10:28:22PM -0400, Derrick Stolee wrote:
> 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.

Sure, I think what I'm trying to understand here is whether this
"incapability" is a fundamental one, or just that we haven't implemented
checking bitmaps in the path-walk API yet.

Thanks,
Taylor