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

[PATCH 6/8] pack-bitmap: sort bitmaps before XORing

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

Reachability bitmaps may be stored as XORs against nearby bitmaps, up to 10 away. However, when callers provide selected commits in an arbitrary order, the writer may miss good ancestor/descendant pairs and produce much larger bitmap files without changing query coverage.

Sort the selected bitmaps in date order (from oldest to newest) before computing XOR offsets, leaving pseudo-merge bitmaps alone (which we will deal with separately in following commits).

On our same testing repository from previous commits, this change shrunk our selection of 1,261 bitmaps from ~635.46 MiB to 176.4 MiB for a ~72.24% reduction in the on-disk size of our *.bitmap file. The time to generate the smaller bitmap file decreased by ~3.69 seconds, though this is likely mostly noise.

Signed-off-by: Taylor Blau <me@ttaylorr.com>
---
 pack-bitmap-write.c | 29 +++++++++++++++++++++++++++++
 1 file changed, 29 insertions(+)
diff --git a/pack-bitmap-write.c b/pack-bitmap-write.c
index 4b6fb07edd7..66282ea14b5 100644
--- a/pack-bitmap-write.c
+++ b/pack-bitmap-write.c
@@ -327,11 +327,40 @@ static uint32_t find_object_pos(struct bitmap_writer *writer,
 	return 0;
 }
 
+static int bitmapped_commit_date_cmp(const void *_a, const void *_b)
+{
+	const struct bitmapped_commit *a = _a;
+	const struct bitmapped_commit *b = _b;
+
+	if (a->commit->date < b->commit->date)
+		return -1;
+	if (a->commit->date > b->commit->date)
+		return 1;
+	return 0;
+}
+
 static void compute_xor_offsets(struct bitmap_writer *writer)
 {
 	static const int MAX_XOR_OFFSET_SEARCH = 10;
 
 	int i, next = 0;
+	int nr = bitmap_writer_nr_selected_commits(writer);
+
+	if (nr > 1) {
+		QSORT(writer->selected, nr, bitmapped_commit_date_cmp);
+
+		for (i = 0; i < nr; i++) {
+			struct bitmapped_commit *stored = &writer->selected[i];
+			khiter_t hash_pos = kh_get_oid_map(writer->bitmaps,
+							   stored->commit->object.oid);
+
+			if (hash_pos == kh_end(writer->bitmaps))
+				BUG("selected commit missing from bitmap map: %s",
+				    oid_to_hex(&stored->commit->object.oid));
+
+			kh_value(writer->bitmaps, hash_pos) = stored;
+		}
+	}
 
 	while (next < writer->selected_nr) {
 		struct bitmapped_commit *stored = &writer->selected[next];
-- 
2.54.0.rc1.84.g30ce254312c
Previous: Taylor BlauNext: Jeff King
Message 19 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.