Re: [PATCH 0/4] pack-objects: create new name-hash algorithm

[Derrick Stolee <stolee@gmail.com>]

On 9/10/24 10:56 AM, Taylor Blau wrote:
> On Mon, Sep 09, 2024 at 10:37:30PM -0400, Derrick Stolee wrote:
>>> I do agree that considering files at the same path from different
>>> (but close-by) revisions as the prime candidates is very important,
>>> but if you spread the "collissions" very thin by using "uniform
>>> distribution", I am afraid that you'd end up discarding anything but
>>> the blobs at the same path, which may go too far.  Having name hash
>>> value that are close by no longer has any meaning in such a system.
>>
>> You are right that some "nearby" paths are lost in this change, and
>> this can be measured by trying to use this option in the pack-objects
>> process underneath a small 'git push'.
>>
>> The thing that surprised me is just how effective this is for the
>> creation of large pack-files that include many versions of most
>> files. The cross-path deltas have less of an effect here, and the
>> benefits of avoiding name-hash collisions can be overwhelming in
>> many cases.
> 
> I think that Junio's suggestion is pretty interesting (though please
> take my comments here with a grain of salt, since I haven't read the
> other series yet, and am not sure how much of this is redundant).
> 
> Imagine computing both the full and existing name-hash values for each
> blob/tree in the pack. Then objects would be sorted in the delta
> selection window by similar full-name hash and similar regular name hash
> values.
> 
> I'm not sure which value you'd actually record in the pack, though.
> Ideally there is a hash function which captures some information about
> the full path as well as the final path component, so we could use a
> single value here, though I suspect the implementation would be more
> complicated than what is presented here.

Is the name hash stored in the pack itself? I know that it is stored
in the 'struct object_entry' data in the packing data. While we could
add another uint32_t into that struct to store both hash values, this
would increase the memory requirements of repacking by four bytes per
object. The struct seemed to be very clear about trying as hard as
possible to avoid doing that.

But maybe an alternative could be replacing that 32-bit number with
an index into an array of paths that have their hash values stored
there.

This would still involve two passes, but might still be possible. I'll
think on this.

>>> I hope you can find a solution that strikes a good balance at the
>>> end of the series (I saw only the first step), but I suspect an easy
>>> way to avoid the downsides you observed is to use both.  Compare
>>> with a handful of blobs taken from nearby commits (the original
>>> object order is roughly in traversal order, and you can take
>>> advantage of that fact) from exactly the same path (using your
>>> "uniform distribution") before comparing with the blobs with close
>>> value (of the current function) like the current implementation
>>> does, may go a long way.
>>
>> Funny you should say that, since the RFC I finally submitted [1]
>> actually does just that. The --path-walk option changes the object
>> walk to consider batches of objects based on their path, computes
>> deltas among that batch, and then does the normal name-hash pass
>> later. This seems to really strike the balance that you are
>> looking for and solves the issues where small pushes need to stay
>> small. It also fixes some problematic cases even when pushing a
>> single commit.
> 
> Interesting.
> 
>> [1] https://lore.kernel.org/git/pull.1786.git.1725935335.gitgitgadget@gmail.com/
> 
>> However, the --path-walk option requires significant implementation
>> of a "path walk API" and my RFC doesn't even do threading right.
>> The --path-walk version (probably) doesn't work with delta islands
>> or other features the same way as the drop-in change to the name-
>> hash heuristic can. For that reason, I think there is likely some
>> long-term value to the --full-name-hash option even though the
>> --path-walk option will be better in many cases.
> 
> I suspect that this is going to be a significant sticking point. Not
> supporting multi-threading is work-able for GitHub (since we set
> pack.threads=1 today), but lacking support for delta-islands makes this
> a non-starter to run at GitHub.
> 
> Do you imagine that the --path-walk option could be made to work with
> delta islands? I'm not all that worried about who does that work, but
> more interested at this point in whether or not it's even possible to
> implement.
This is part of the reason why I think the --full-name-hash option is
an interesting consideration. It doesn't have any obvious reason why
it couldn't work with features like delta islands, so it may provide
some quick wins in "large enough" repositories, or at least "large in
the right way".

I unfortunately don't know enough about how the delta islands feature
works to be confident in the possibility of integrating it with the
--path-walk option. At minimum, it would require two object walks:
the first would mark the objects and the second would do the delta
compression with those markings in mind.

But if there is a way to combine both approaches with a two-pass
delta compression technique, then this may be all avoided. I'll give
it a try.

Thanks,
-Stolee