Re: [PATCH v3 26/30] pack-bitmap.c: use pseudo-merges during traversal
- From
Jeff King <peff@peff.net>
- Date
- May 23, 2024, 10:48 UTC
- Message-ID
- <20240523104837.GE1308330@coredump.intra.peff.net>
- In-Reply-To
- <41691824f78818f3c70cad6d02cd7f66d12c68c3.1716318089.git.me@ttaylorr.com>
On Tue, May 21, 2024 at 03:03:03PM -0400, Taylor Blau wrote:
Show 19 quoted lines
> The basic operation is as follows: > > - When enumerating objects on either side of a reachability query, > first see if any subset of the roots satisfies some pseudo-merge > bitmap. If it does, apply that pseudo-merge bitmap. > > - If any pseudo-merge bitmap(s) were applied in the previous step, OR > them into the result[^1]. Then repeat the process over all > pseudo-merge bitmaps (we'll refer to this as "cascading" > pseudo-merges). Once this is done, OR in the resulting bitmap. > > - If there is no fill-in traversal to be done, return the bitmap for > that side of the reachability query. If there is fill-in traversal, > then for each commit we encounter via show_commit(), check to see if > any unsatisfied pseudo-merges containing that commit as one of its > parents has been made satisfied by the presence of that commit. > > If so, OR in the object set from that pseudo-merge bitmap, and then > cascade. If not, continue traversal.
Ah, OK. This is the high-level overview I was looking for in the earlier commit. ;) I think it is fine here. I just hadn't gotten to it yet (and I think it is much better stated than what I wrote in my earlier response).
Show 6 quoted lines
> [^1]: Importantly, we cannot OR in the entire set of roots along with > the objects reachable from whatever pseudo-merge bitmaps were > satisfied. This may leave some dangling bits corresponding to any > unsatisfied root(s) getting OR'd into the resulting bitmap, tricking > other parts of the traversal into thinking we already have a > reachability closure over those commit(s) when we do not.
I think I know how you made this realization. :)
The code itself looks as I'd expect, and the entry points are nice and clean.
-Peff