From: Taylor Blau <me@ttaylorr•com>
To: git@vger•kernel.org
Cc: Junio C Hamano <gitster@pobox•com>, Jeff King <peff@peff•net>,
Elijah Newren <newren@gmail•com>,
Derrick Stolee <stolee@gmail•com>
Subject: [PATCH 1/8] pack-bitmap: pass object position to `fill_bitmap_tree()`
Date: Tue, 19 May 2026 12:12:36 -0400 [thread overview]
Message-ID: <13191c19b91bc3f5d671b7016b97f2309f12737d.1779207127.git.me@ttaylorr.com> (raw)
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
next prev parent reply other threads:[~2026-05-19 16:12 UTC|newest]
Thread overview: 38+ messages / expand[flat|nested] mbox.gz Atom feed top
2026-05-19 16:12 [PATCH 0/8] pack-bitmap-write: speed up bitmap generation Taylor Blau
2026-05-19 16:12 ` Taylor Blau [this message]
2026-05-27 8:57 ` [PATCH 1/8] pack-bitmap: pass object position to `fill_bitmap_tree()` Jeff King
2026-05-27 14:36 ` Taylor Blau
2026-05-19 16:12 ` [PATCH 2/8] pack-bitmap: check subtree bits before recursing Taylor Blau
2026-05-27 9:03 ` Jeff King
2026-05-27 14:36 ` Taylor Blau
2026-05-19 16:12 ` [PATCH 3/8] pack-bitmap: reuse stored selected bitmaps Taylor Blau
2026-05-27 9:24 ` Jeff King
2026-05-27 14:40 ` Taylor Blau
2026-05-29 6:00 ` Jeff King
2026-05-19 16:12 ` [PATCH 4/8] pack-bitmap: consolidate `find_object_pos()` success path Taylor Blau
2026-05-20 14:42 ` SZEDER Gábor
2026-05-20 17:12 ` Taylor Blau
2026-05-27 9:27 ` Jeff King
2026-05-19 16:12 ` [PATCH 5/8] pack-bitmap: cache object positions during fill Taylor Blau
2026-05-27 9:45 ` Jeff King
2026-05-27 14:46 ` Taylor Blau
2026-05-19 16:12 ` [PATCH 6/8] pack-bitmap: sort bitmaps before XORing Taylor Blau
2026-05-27 10:04 ` Jeff King
2026-05-27 16:56 ` Taylor Blau
2026-05-29 8:26 ` Jeff King
2026-05-19 16:12 ` [PATCH 7/8] pack-bitmap: remember pseudo-merge parents Taylor Blau
2026-05-19 16:12 ` [PATCH 8/8] pack-bitmap: build pseudo-merge bitmaps after regular bitmaps Taylor Blau
2026-05-27 10:25 ` Jeff King
2026-05-27 19:24 ` Taylor Blau
2026-05-29 8:33 ` Jeff King
2026-05-27 10:27 ` [PATCH 0/8] pack-bitmap-write: speed up bitmap generation Jeff King
2026-05-27 19:55 ` [PATCH v2 " Taylor Blau
2026-05-27 19:55 ` [PATCH v2 1/8] pack-bitmap: pass object position to `fill_bitmap_tree()` Taylor Blau
2026-05-27 19:55 ` [PATCH v2 2/8] pack-bitmap: check subtree bits before recursing Taylor Blau
2026-05-27 19:55 ` [PATCH v2 3/8] pack-bitmap: reuse stored selected bitmaps Taylor Blau
2026-05-27 19:55 ` [PATCH v2 4/8] pack-bitmap: consolidate `find_object_pos()` success path Taylor Blau
2026-05-27 19:56 ` [PATCH v2 5/8] pack-bitmap: cache object positions during fill Taylor Blau
2026-05-27 19:56 ` [PATCH v2 6/8] pack-bitmap: sort bitmaps before XORing Taylor Blau
2026-05-27 19:56 ` [PATCH v2 7/8] pack-bitmap: remember pseudo-merge parents Taylor Blau
2026-05-27 19:56 ` [PATCH v2 8/8] pack-bitmap: build pseudo-merge bitmaps after regular bitmaps Taylor Blau
2026-05-29 8:34 ` [PATCH v2 0/8] pack-bitmap-write: speed up bitmap generation Jeff King
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=13191c19b91bc3f5d671b7016b97f2309f12737d.1779207127.git.me@ttaylorr.com \
--to=me@ttaylorr$(echo .)com \
--cc=git@vger$(echo .)kernel.org \
--cc=gitster@pobox$(echo .)com \
--cc=newren@gmail$(echo .)com \
--cc=peff@peff$(echo .)net \
--cc=stolee@gmail$(echo .)com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox