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

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

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

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.

When processing sub-trees within `fill_bitmap_tree()`, the preimage of this patch did the following:

    while (tree_entry(&desc, entry)) {
        switch (object_type(entry.mode)) {
        case OBJ_TREE:
            if (fill_bitmap_tree(writer, bitmap,
                                 lookup_tree(writer->repo,
                                             &entry.oid)) < 0) {
                /* ... */
            }
            /* ... */
        }
    }

, first performing the object lookup via `lookup_tree()`, and then locating its bit position within the recursive call. This patch effectively reorders those two calls so that we first discover the sub-tree's bit position, *then* load its tree.

By reordering these two operations, we spend fewer CPU cycles per instruction, likely due to improved CPU dependency/cache/pipeline behavior. Comparing the results of: running `perf stat` before and after this commit, we have:

    +--------------+-------------+-------------+-------------------+
    |              | HEAD^       | HEAD        | Delta             |
    +--------------+-------------+-------------+-------------------+
    | elapsed      |   612.5 s   |   582.4 s   |  -30.1 s  (-4.9%) |
    | cycles       | 2,857.3 B   | 2,713.3 B   | -144.0 B  (-5.0%) |
    | instructions | 2,413.2 B   | 2,415.5 B   |   +2.3 B  (+0.1%) |
    | CPI          |     1.184   |     1.123   |  -0.061   (-5.1%) |
    +--------------+-------------+-------------+-------------------+

In a large repository with ~4.8M commit, and ~37.1M tree objects this change improves timing from ~612.5 seconds down to ~582.4 seconds, or a ~4.9% improvement. More importantly, the number of CPU cycles spent dropped off significantly as a result of this commit, lowering our cycles-per-instruction ratio by about ~5.1%.

Signed-off-by: Taylor Blau <me@ttaylorr.com>
---
 pack-bitmap-write.c | 23 +++++++++++++++--------
 1 file changed, 15 insertions(+), 8 deletions(-)
diff --git a/pack-bitmap-write.c b/pack-bitmap-write.c
index 1c8070f99c0..2d5ff8fd406 100644
--- a/pack-bitmap-write.c
+++ b/pack-bitmap-write.c
@@ -456,10 +456,10 @@ static void bitmap_builder_clear(struct bitmap_builder *bb)
 
 static int fill_bitmap_tree(struct bitmap_writer *writer,
 			    struct bitmap *bitmap,
-			    struct tree *tree)
+			    struct tree *tree,
+			    uint32_t pos)
 {
 	int found;
-	uint32_t pos;
 	struct tree_desc desc;
 	struct name_entry entry;
 
@@ -467,9 +467,6 @@ static int fill_bitmap_tree(struct bitmap_writer *writer,
 	 * If our bit is already set, then there is nothing to do. Both this
 	 * tree and all of its children will be set.
 	 */
-	pos = find_object_pos(writer, &tree->object.oid, &found);
-	if (!found)
-		return -1;
 	if (bitmap_get(bitmap, pos))
 		return 0;
 	bitmap_set(bitmap, pos);
@@ -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;
 		case OBJ_BLOB:
@@ -575,8 +576,14 @@ static int fill_bitmap_commit(struct bitmap_writer *writer,
 	}
 
 	while (tree_queue->nr) {
-		if (fill_bitmap_tree(writer, ent->bitmap,
-				     prio_queue_get(tree_queue)) < 0)
+		struct tree *t = prio_queue_get(tree_queue);
+		int found;
+
+		pos = find_object_pos(writer, &t->object.oid, &found);
+		if (!found)
+			return -1;
+
+		if (fill_bitmap_tree(writer, ent->bitmap, t, pos) < 0)
 			return -1;
 	}
 	return 0;
-- 
2.54.0.rc1.84.g30ce254312c
Previous: Taylor BlauNext: Jeff King
Message 2 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.