From: Jeff King Date: Fri, 02 Oct 2026 23:02:25 GMT Subject: Re: [PATCH 2/4] pack-objects: ensure tree/tag closure with '--stdin-packs=follow' Message-ID: <20261002230225.GA834759@coredump.intra.peff.net> In-Reply-To: On Thu, Oct 01, 2026 at 07:51:48PM -0500, Taylor Blau wrote: > 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