Re: [PATCH 1/8] pack-bitmap: pass object position to `fill_bitmap_tree()`

[Taylor Blau <me@ttaylorr.com>]

On Wed, May 27, 2026 at 04:57:40AM -0400, Jeff King wrote:
> It is indeed surprising. There's a possible candidate for the speedup
> here:
>
> > @@ -482,8 +479,12 @@ static int fill_bitmap_tree(struct bitmap_writer *writer,
> >  	while (tree_entry(&desc, &entry)) {
> >  		switch (object_type(entry.mode)) {
> >  		case OBJ_TREE:
> > +			pos = find_object_pos(writer, &entry.oid, &found);
> > +			if (!found)
> > +				return -1;
> >  			if (fill_bitmap_tree(writer, bitmap,
> > -					     lookup_tree(writer->repo, &entry.oid)) < 0)
> > +					     lookup_tree(writer->repo,
> > +							 &entry.oid), pos) < 0)
> >  				return -1;
> >  			break;
>
> Whenever "found" is false, we cut out early and skip the hash lookup in
> lookup_tree() entirely. But that should almost never happen! It implies
> that a reachable object is not in the pack/midx, and thus the bitmaps is
> not closed (and we'll refuse to generate it).

That's right, and I had actually written something like the following
while developing this patch:

--- 8< ---
diff --git a/pack-bitmap-write.c b/pack-bitmap-write.c
index 2d5ff8fd406..328e1c13df3 100644
--- a/pack-bitmap-write.c
+++ b/pack-bitmap-write.c
@@ -481,7 +481,7 @@ static int fill_bitmap_tree(struct bitmap_writer *writer,
 		case OBJ_TREE:
 			pos = find_object_pos(writer, &entry.oid, &found);
 			if (!found)
-				return -1;
+				BUG("huh??");
 			if (fill_bitmap_tree(writer, bitmap,
 					     lookup_tree(writer->repo,
 							 &entry.oid), pos) < 0)
--- >8 ---

, but couldn't trigger it in either the test suite nor in my sample
repository. I left it in there as a sanity measure.

> So it really is the case that we do the same operations in a different
> order. Weird.

Yeah, I puzzled over this for quite a while myself. I really think that
this is reordering produces more favorable cache behavior or codegen
that results in a meaningful speedup.

> But the patch itself looks correct to me, and I get ~6% speedup on a
> from-scratch bitmap generation of linux.git. I guess it could vary
> between architectures and compilers (I'm using gcc on x86), but since
> the reorg is setting us up for further optimizations in the next patch,
> I suppose there's no need to look a gift horse in the mouth.

Good, I'm glad that it was reproducible on your machine. And I agree
;-).

Thanks,
Taylor