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@xxxxxxxxx/
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
