From: Taylor Blau Date: Wed, 27 May 2026 14:36:06 GMT Subject: Re: [PATCH 1/8] pack-bitmap: pass object position to `fill_bitmap_tree()` Message-ID: In-Reply-To: <20260527085740.GB981444@coredump.intra.peff.net> 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