From: Taylor Blau Date: Wed, 27 May 2026 19:55:44 GMT Subject: [PATCH v2 0/8] pack-bitmap-write: speed up bitmap generation Message-ID: In-Reply-To: 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 ## 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 ## pack-bitmap-write.c ## base-commit: c3d7ca7d982efc3a848fd85f34e867cfc0a99479 -- 2.54.0.rc1.84.g1cf18622df7