git/list[1] front-page[2] threads[3] people[4] search[5] about
 

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

From
Jeff King <peff@peff.net>
Date
May 27, 2026, 08:57 UTC
Message-ID
<20260527085740.GB981444@coredump.intra.peff.net>
In-Reply-To
<13191c19b91bc3f5d671b7016b97f2309f12737d.1779207127.git.me@ttaylorr.com>
On Tue, May 19, 2026 at 12:12:36PM -0400, Taylor Blau wrote:
Show 10 quoted lines
> In the following commit, callers of `fill_bitmap_tree()` will be
> required to check the bit corresponding to their tree before calling
> that function. That change will reduce the overhead of setting up and
> tearing down stack frames for trees whose bits are already set.
> 
> To prepare for that change, have callers pass in the tree's bit position
> in `fill_bitmap_tree()`, which will make the next commit easier to read.
> 
> In the meantime, this change has a surprising and measurable benefit
> during bitmap generation, particularly on very large repositories.

It is indeed surprising. There's a possible candidate for the speedup here:

Show 13 quoted lines
> @@ -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).

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

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.

-Peff
Previous: Taylor BlauNext: Taylor Blau
Message 3 of 38 in “pack-bitmap-write: speed up bitmap generation”
  1. 0/8 pack-bitmap-write: speed up bitmap generationTaylor Blau, May 19, 2026
  2. 1/8 pack-bitmap: pass object position to `fill_bitmap_tree()`Taylor Blau, May 19, 2026
  3. Jeff KingMay 27, 2026
  4. Taylor BlauMay 27, 2026
  5. 2/8 pack-bitmap: check subtree bits before recursingTaylor Blau, May 19, 2026
  6. Jeff KingMay 27, 2026
  7. Taylor BlauMay 27, 2026
  8. 3/8 pack-bitmap: reuse stored selected bitmapsTaylor Blau, May 19, 2026
  9. Jeff KingMay 27, 2026
  10. Taylor BlauMay 27, 2026
  11. Jeff KingMay 29, 2026
  12. 4/8 pack-bitmap: consolidate `find_object_pos()` success pathTaylor Blau, May 19, 2026
  13. SZEDER GáborMay 20, 2026
  14. Taylor BlauMay 20, 2026
  15. Jeff KingMay 27, 2026
  16. 5/8 pack-bitmap: cache object positions during fillTaylor Blau, May 19, 2026
  17. Jeff KingMay 27, 2026
  18. Taylor BlauMay 27, 2026
  19. 6/8 pack-bitmap: sort bitmaps before XORingTaylor Blau, May 19, 2026
  20. Jeff KingMay 27, 2026
  21. Taylor BlauMay 27, 2026
  22. Jeff KingMay 29, 2026
  23. 7/8 pack-bitmap: remember pseudo-merge parentsTaylor Blau, May 19, 2026
  24. 8/8 pack-bitmap: build pseudo-merge bitmaps after regular bitmapsTaylor Blau, May 19, 2026
  25. Jeff KingMay 27, 2026
  26. Taylor BlauMay 27, 2026
  27. Jeff KingMay 29, 2026
  28. Jeff KingMay 27, 2026
  29. 0/8 pack-bitmap-write: speed up bitmap generationTaylor Blau, May 27, 2026
  30. 1/8 pack-bitmap: pass object position to `fill_bitmap_tree()`Taylor Blau, May 27, 2026
  31. 2/8 pack-bitmap: check subtree bits before recursingTaylor Blau, May 27, 2026
  32. 3/8 pack-bitmap: reuse stored selected bitmapsTaylor Blau, May 27, 2026
  33. 4/8 pack-bitmap: consolidate `find_object_pos()` success pathTaylor Blau, May 27, 2026
  34. 5/8 pack-bitmap: cache object positions during fillTaylor Blau, May 27, 2026
  35. 6/8 pack-bitmap: sort bitmaps before XORingTaylor Blau, May 27, 2026
  36. 7/8 pack-bitmap: remember pseudo-merge parentsTaylor Blau, May 27, 2026
  37. 8/8 pack-bitmap: build pseudo-merge bitmaps after regular bitmapsTaylor Blau, May 27, 2026
  38. Jeff KingMay 29, 2026

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.