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

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

From
Taylor Blau <me@ttaylorr.com>
Date
May 27, 2026, 19:55 UTC
Message-ID
<cover.1779911733.git.me@ttaylorr.com>
In-Reply-To
<cover.1779207127.git.me@ttaylorr.com>

Here is a reroll of my series to improve the performance of reachability bitmap generation, focusing on very large repositories and the penalty to generate pseudo-merge reachability bitmaps.

The series is largely unchanged since last time. Notable changes in this round include:

 - minor refactoring in the pair of patches which consolidate the
   `find_object_pos()` success path and introduce the object position
   cache during bitmap fills, and
 - dropping a stale paragraph from the final patch's message, which
   described follow-up commits that are no longer part of this series.
As usual, a range-diff against v1 is included below for convenience.
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(-)
Range-diff against v1:
1:  13191c19b91 = 1:  ad025810ab3 pack-bitmap: pass object position to `fill_bitmap_tree()`
2:  7d6d1cec0dd = 2:  59da63d0330 pack-bitmap: check subtree bits before recursing
3:  6e1f6bef5f6 = 3:  f13d65c0ad9 pack-bitmap: reuse stored selected bitmaps
4:  c9a56066094 ! 4:  856aa3a6ab7 pack-bitmap: consolidate `find_object_pos()` success path
    @@ Commit message
         Signed-off-by: Taylor Blau <me@ttaylorr.com>
     
      ## pack-bitmap-write.c ##
    +@@ pack-bitmap-write.c: static uint32_t find_object_pos(struct bitmap_writer *writer,
    + 				const struct object_id *oid, int *found)
    + {
    + 	struct object_entry *entry;
    ++	uint32_t pos;
    + 
    + 	entry = packlist_find(writer->to_pack, oid);
    + 	if (entry) {
     @@ pack-bitmap-write.c: static uint32_t find_object_pos(struct bitmap_writer *writer,
      		if (writer->midx)
      			base_objects = writer->midx->num_objects +
5:  e43ef6a42d1 ! 5:  70dfa80d543 pack-bitmap: cache object positions during fill
    @@ pack-bitmap-write.c: void bitmap_writer_push_commit(struct bitmap_writer *writer
      				const struct object_id *oid, int *found)
      {
      	struct object_entry *entry;
    -+	uint32_t pos;
    -+
    + 	uint32_t pos;
    + 
     +	bitmap_writer_init_pos_cache(writer);
     +
     +	if (find_cached_object_pos(writer, oid, &pos)) {
    @@ pack-bitmap-write.c: void bitmap_writer_push_commit(struct bitmap_writer *writer
     +			*found = 1;
     +		return pos;
     +	}
    - 
    ++
      	entry = packlist_find(writer->to_pack, oid);
      	if (entry) {
      		uint32_t base_objects = 0;
6:  b0a4f31353a = 6:  b1184792d23 pack-bitmap: sort bitmaps before XORing
7:  0bd88e6a096 = 7:  673b6262911 pack-bitmap: remember pseudo-merge parents
8:  30ce254312c ! 8:  8722242f1bb pack-bitmap: build pseudo-merge bitmaps after regular bitmaps
    @@ Commit message
         portion of history reachable by one or more pseudo-merge(s), but not by
         any non-pseudo-merge commit selected for bitmapping.
     
    -    Now that we have decoupled how we generate pseudo-merges from their
    -    representation, the following commits will improve the API around
    -    specifying pseudo-merge groupings during bitmap generation.
    -
         Signed-off-by: Taylor Blau <me@ttaylorr.com>
     
      ## pack-bitmap-write.c ##
base-commit: c3d7ca7d982efc3a848fd85f34e867cfc0a99479
-- 
2.54.0.rc1.84.g1cf18622df7
Previous: Jeff KingNext: Taylor Blau
Message 29 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.