From: Taylor Blau Date: Wed, 27 May 2026 14:40:31 GMT Subject: Re: [PATCH 3/8] pack-bitmap: reuse stored selected bitmaps Message-ID: In-Reply-To: <20260527092412.GD981444@coredump.intra.peff.net> On Wed, May 27, 2026 at 05:24:12AM -0400, Jeff King wrote: > On Tue, May 19, 2026 at 12:12:41PM -0400, Taylor Blau wrote: > > > Building bitmaps from scratch on the same test repository from the > > previous commits yields a significant speed-up: > > > > +------------------+-------------+-------------+---------------------+ > > | | HEAD^ | HEAD | Delta | > > +------------------+-------------+-------------+---------------------+ > > | elapsed | 562.8 s | 324.8 s | -237.9 s (-42.3%) | > > | cycles | 2,621.3 B | 1,508.6 B | -1,112.7 B (-42.4%) | > > | instructions | 2,348.9 B | 1,436.6 B | -912.3 B (-38.8%) | > > | CPI | 1.116 | 1.050 | -0.066 (-5.9%) | > > +------------------+-------------+-------------+---------------------+ > > Oh my, that's a rather nice speedup. I can reproduce here on linux.git > (~47% improvement). > > > When `fill_bitmap_commit()` reaches an ancestor that was selected for > > its own bitmap and processed earlier, its object closure is already > > stored in `writer->bitmaps` as an EWAH bitmap. As a result, walking > > through that commit's tree and parents again is redundant. > > > > Teach `fill_bitmap_commit()` to notice that case. For non-root commits in > > the walk, look for a stored selected bitmap and OR it into the bitmap > > being built. If one exists, skip the commit, its tree, and its parents. > > I feel like this _shouldn't_ be necessary, because the idea of the > current writing code is to go from the roots up, following inverted > parent pointers, and passing the bitmap up as we go. So whenever we > visit a commit we should in theory have all of the ancestor's bits set > in that bitmap. But I remember that the simple-and-stupid approach ended > up being too memory hungry, so we pick some focal points in the graph > and then fill them independently. It's sharing within the non-first parent history that is killing us here. I think what you said is true in a completely linear repository with no merges. But since we only pass commit masks from commits to their first parents, we don't reuse any already-generated bitmaps for common points in history not shared between commits' first parents. > I wondered about "c != commit" here. "c" is the commit we're traversing, > and "commit" is the one for which we're trying to build the bitmap. So > we would not expect to ever have an entry in writer->bitmaps for "c" > yet, but the conditional is just short-circuiting the hash lookup. Exactly. > The rest of the patch looks obviously correct. The trace2 bits aren't > strictly necessary, of course, but some metrics might help with further > tuning. Yeah, these were for my own curiosity as much as anything. I had written them as a temporary measure in order to write the "[...] there are 1,261 commits selected for bitmap coverage, and 1,382 maximal commits induced [...]" portion of the commit message above. Once I had written it, I found the result useful enough to keep around. Thanks, Taylor