Re: [PATCH 2/4] pack-objects: ensure tree/tag closure with '--stdin-packs=follow'

From: Jeff King <peff@peff.net>
Date: Oct 2, 2026, 23:02 UTC
Message-ID: <20261002230225.GA834759@coredump.intra.peff.net>
In-Reply-To: <ar8AJLYZVb6sCIO-@com-79390>

On Thu, Oct 01, 2026 at 07:51:48PM -0500, Taylor Blau wrote:

Show 20 quoted lines

> On Thu, Oct 01, 2026 at 04:22:11PM -0700, Elijah Newren wrote:
> > With the oid_array and parent-first pack order, the blobs are visited
> > as sub/a and sub/b, so sub/* -delta applies. With the oidset, the
> > subtree is visited first and the blobs are seen as a and b, so one is
> > delta-compressed. When the root is processed later, the subtree is
> > already marked SEEN and is not revisited with the sub/ prefix.
> >
> > The oid_array does not manufacture parent-before-child ordering if the
> > input pack itself has the subtree first; this path information is
> > explicitly best-effort. But it preserves a useful order when one
> > exists, whereas an oidset discards it.
> 
> Sure, though as Peff and I discussed elsewhere in the thread, there are
> also situations where you can produce a sub-optimal pack even with
> oid_array. That's because the namehash you get for a given tree object
> depends on the path you took to get there.
> 
> So you can certainly come up with examples where the ordering of tree
> objects in an array of extra roots produces a lesser-quality delta
> selection than the same objects permuted into some different order.

Hmm. Yeah, it is not a 100% solved issue, for sure, but I think Elijah has a point. Even though yes, we may see trees in weird orders between packs, or when visited separate from another commit, the ordering in a single pack _is_ useful, because it puts root trees before subtrees.

So even though these are a few objects we're rescuing out of a cruft pack, we'd expect them to be correlated. E.g., an update to "a/b/c/file" is going to have four trees: the root, a, a/b, and a/b/c. And we'd like to visit them in that order. Which is the order in which we'd typically write them in a pack.

One thing I'm not 100% on is if that "typically" qualifier applies to cruft packs. We might be throwing objects in there with a little less thought, because the point is that they're _not_ reachable, and we didn't get there from a traversal. So I dunno.

> The other thing to keep in mind is that, while there are clearly
> trade-offs as we have discussed here, the oidset ensures that we don't
> allocate memory wastefully when the same object is listed multiple times
> as an extra root.

Yeah, that was my thinking when endorsing the oidset earlier; it is better bounded. It can have worse memory use in practice, though, because it's a hash table rather than a vanilla array. So if we don't expect a lot of duplicates, then the simpler array may be more efficient.

-Peff