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

[PATCH 0/8] pack-bitmap-write: speed up bitmap generation

From
Taylor Blau <me@ttaylorr.com>
Date
May 19, 2026, 16:12 UTC
Message-ID
<cover.1779207127.git.me@ttaylorr.com>
Note to the maintainer:
 * This series is based on 'tb/pseudo-merge-bugfixes', with
   'ps/clang-w-glibc-2.43-and-_Generic' merged in. I suggest queueing it
   as 'tb/bitmap-build-performance'.
   The latter merge is only to avoid the current Clang/glibc 2.43 CI
   breakage, and is unrelated to the bitmap changes themselves.

This series improves the performance of reachability bitmap generation, focusing on very large repositories and the penalty to generate pseudo-merge reachability bitmaps.

The first few patches address hot paths in the ordinary bitmap build:
 - pass object positions into `fill_bitmap_tree()` so callers can avoid
   redundant lookups,
 - check subtree bits before recursing, which avoids many no-op
   `fill_bitmap_tree()` calls,
 - reuse already-stored selected bitmaps when `fill_bitmap_commit()`
   reaches a selected ancestor, and
 - add a small direct-mapped cache from object IDs to bitmap positions
   to avoid repeated pack/MIDX lookups while filling bitmaps.

On the large repository that I have been using to benchmark these changes (~4.8M commits and ~57M total objects), the no-pseudo-merge bitmap generation case drops **from ~612.5 seconds to ~294.1 seconds**.

The next patch sorts selected bitmaps before choosing XOR offsets. This does not change bitmap selection/coverage, but in the same repository it shrinks the generated bitmap file **from ~635.5 MiB to ~176.4 MiB** by putting related ancestor/descendant bitmaps close enough together for the XOR search window to find them.

The final two patches focus on pseudo-merge bitmaps. The existing code feeds pseudo-merges into the same maximal-commit selection machinery as ordinary selected commits. That machinery works well for real history, but not pseudo-merges.

Instead, this series builds ordinary selected bitmaps first, then builds pseudo-merge bitmaps afterwards. The later pseudo-merge fill can still reuse stored selected ancestor bitmaps, and can also reuse an existing on-disk pseudo-merge bitmap when the parent set matches.

With the coarse pseudo-merge configuration used for testing:
    [bitmapPseudoMerge "all"]
        pattern=refs/
        threshold=now
        stableSize=10000000
        maxMerges=8

, the optimized no-pseudo-merge case takes ~294.1 seconds, while the **pseudo-merge case takes ~328.4 seconds**. Before the final change, the same pseudo-merge configuration took ~575.0 seconds.

On our testing repository, it is faster at the end of this series to generate bitmaps with pseudo-merges (~328 seconds as above) than it is to generate bitmaps without pseudo-merges at the start of this series (~612 seconds).

Thanks in advance for your review!
Taylor Blau (8):
  pack-bitmap: pass object position to `fill_bitmap_tree()`
  pack-bitmap: check subtree bits before recursing
  pack-bitmap: reuse stored selected bitmaps
  pack-bitmap: consolidate `find_object_pos()` success path
  pack-bitmap: cache object positions during fill
  pack-bitmap: sort bitmaps before XORing
  pack-bitmap: remember pseudo-merge parents
  pack-bitmap: build pseudo-merge bitmaps after regular bitmaps
 pack-bitmap-write.c | 431 +++++++++++++++++++++++++++++++++++++-------
 pack-bitmap.h       |   7 +
 2 files changed, 377 insertions(+), 61 deletions(-)
base-commit: c3d7ca7d982efc3a848fd85f34e867cfc0a99479
-- 
2.54.0.rc1.84.g30ce254312c
Next: Taylor Blau
Message 1 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.