Re: [PATCH 3/8] pack-bitmap: reuse stored selected bitmaps

[Taylor Blau <me@ttaylorr.com>]

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