{"thread":{"id":"65661","subject":"[PATCH 0/8] pack-bitmap-write: speed up bitmap generation","startedAt":"2026-05-19T16:12:35Z","lastAt":"2026-05-29T08:34:40Z","messageCount":38,"participants":["Taylor Blau","SZEDER Gábor","Jeff King"],"isPatch":true,"patchVersion":1,"patchTotal":8},"messages":[{"id":"543671","messageId":"cover.1779207127.git.me@ttaylorr.com","threadId":"65661","inReplyTo":null,"subject":"[PATCH 0/8] pack-bitmap-write: speed up bitmap generation","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2026-05-19T16:12:33Z","receivedAt":"2026-05-19T16:12:35Z","isPatch":true,"body":"Note to the maintainer:\n\n * This series is based on 'tb/pseudo-merge-bugfixes', with\n 'ps/clang-w-glibc-2.43-and-_Generic' merged in. I suggest queueing it\n as 'tb/bitmap-build-performance'.\n\n The latter merge is only to avoid the current Clang/glibc 2.43 CI\n breakage, and is unrelated to the bitmap changes themselves.\n\nThis series improves the performance of reachability bitmap generation,\nfocusing on very large repositories and the penalty to generate\npseudo-merge reachability bitmaps.\n\nThe first few patches address hot paths in the ordinary bitmap build:\n\n - pass object positions into `fill_bitmap_tree()` so callers can avoid\n redundant lookups,\n\n - check subtree bits before recursing, which avoids many no-op\n `fill_bitmap_tree()` calls,\n\n - reuse already-stored selected bitmaps when `fill_bitmap_commit()`\n reaches a selected ancestor, and\n\n - add a small direct-mapped cache from object IDs to bitmap positions\n to avoid repeated pack/MIDX lookups while filling bitmaps.\n\nOn the large repository that I have been using to benchmark these\nchanges (~4.8M commits and ~57M total objects), the no-pseudo-merge\nbitmap generation case drops **from ~612.5 seconds to ~294.1 seconds**.\n\nThe next patch sorts selected bitmaps before choosing XOR offsets. This\ndoes not change bitmap selection/coverage, but in the same repository it\nshrinks the generated bitmap file **from ~635.5 MiB to ~176.4 MiB** by\nputting related ancestor/descendant bitmaps close enough together for\nthe XOR search window to find them.\n\nThe final two patches focus on pseudo-merge bitmaps. The existing code\nfeeds pseudo-merges into the same maximal-commit selection machinery as\nordinary selected commits. That machinery works well for real history,\nbut not pseudo-merges.\n\nInstead, this series builds ordinary selected bitmaps first, then builds\npseudo-merge bitmaps afterwards. The later pseudo-merge fill can still\nreuse stored selected ancestor bitmaps, and can also reuse an existing\non-disk pseudo-merge bitmap when the parent set matches.\n\nWith the coarse pseudo-merge configuration used for testing:\n\n [bitmapPseudoMerge \"all\"]\n pattern=refs/\n threshold=now\n stableSize=10000000\n maxMerges=8\n\n, the optimized no-pseudo-merge case takes ~294.1 seconds, while the\n**pseudo-merge case takes ~328.4 seconds**. Before the final change, the\nsame pseudo-merge configuration took ~575.0 seconds.\n\nOn our testing repository, it is faster at the end of this series to\ngenerate bitmaps with pseudo-merges (~328 seconds as above) than it is\nto generate bitmaps without pseudo-merges at the start of this series\n(~612 seconds).\n\nThanks in advance for your review!\n\nTaylor Blau (8):\n pack-bitmap: pass object position to `fill_bitmap_tree()`\n pack-bitmap: check subtree bits before recursing\n pack-bitmap: reuse stored selected bitmaps\n pack-bitmap: consolidate `find_object_pos()` success path\n pack-bitmap: cache object positions during fill\n pack-bitmap: sort bitmaps before XORing\n pack-bitmap: remember pseudo-merge parents\n pack-bitmap: build pseudo-merge bitmaps after regular bitmaps\n\n pack-bitmap-write.c | 431 +++++++++++++++++++++++++++++++++++++-------\n pack-bitmap.h | 7 +\n 2 files changed, 377 insertions(+), 61 deletions(-)\n\n\nbase-commit: c3d7ca7d982efc3a848fd85f34e867cfc0a99479\n-- \n2.54.0.rc1.84.g30ce254312c\n"},{"id":"543672","messageId":"13191c19b91bc3f5d671b7016b97f2309f12737d.1779207127.git.me@ttaylorr.com","threadId":"65661","inReplyTo":"cover.1779207127.git.me@ttaylorr.com","subject":"[PATCH 1/8] pack-bitmap: pass object position to `fill_bitmap_tree()`","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2026-05-19T16:12:36Z","receivedAt":"2026-05-19T16:12:38Z","isPatch":true,"body":"In the following commit, callers of `fill_bitmap_tree()` will be\nrequired to check the bit corresponding to their tree before calling\nthat function. That change will reduce the overhead of setting up and\ntearing down stack frames for trees whose bits are already set.\n\nTo prepare for that change, have callers pass in the tree's bit position\nin `fill_bitmap_tree()`, which will make the next commit easier to read.\n\nIn the meantime, this change has a surprising and measurable benefit\nduring bitmap generation, particularly on very large repositories.\n\nWhen processing sub-trees within `fill_bitmap_tree()`, the preimage of\nthis patch did the following:\n\n while (tree_entry(&desc, entry)) {\n switch (object_type(entry.mode)) {\n case OBJ_TREE:\n if (fill_bitmap_tree(writer, bitmap,\n lookup_tree(writer->repo,\n &entry.oid)) < 0) {\n /* ... */\n }\n /* ... */\n }\n }\n\n, first performing the object lookup via `lookup_tree()`, and then\nlocating its bit position within the recursive call. This patch\neffectively reorders those two calls so that we first discover the\nsub-tree's bit position, *then* load its tree.\n\nBy reordering these two operations, we spend fewer CPU cycles per\ninstruction, likely due to improved CPU dependency/cache/pipeline\nbehavior. Comparing the results of: running `perf stat` before and after\nthis commit, we have:\n\n +--------------+-------------+-------------+-------------------+\n | | HEAD^ | HEAD | Delta |\n +--------------+-------------+-------------+-------------------+\n | elapsed | 612.5 s | 582.4 s | -30.1 s (-4.9%) |\n | cycles | 2,857.3 B | 2,713.3 B | -144.0 B (-5.0%) |\n | instructions | 2,413.2 B | 2,415.5 B | +2.3 B (+0.1%) |\n | CPI | 1.184 | 1.123 | -0.061 (-5.1%) |\n +--------------+-------------+-------------+-------------------+\n\nIn a large repository with ~4.8M commit, and ~37.1M tree objects this\nchange improves timing from ~612.5 seconds down to ~582.4 seconds, or a\n~4.9% improvement. More importantly, the number of CPU cycles spent\ndropped off significantly as a result of this commit, lowering our\ncycles-per-instruction ratio by about ~5.1%.\n\nSigned-off-by: Taylor Blau \n---\n pack-bitmap-write.c | 23 +++++++++++++++--------\n 1 file changed, 15 insertions(+), 8 deletions(-)\n\ndiff --git a/pack-bitmap-write.c b/pack-bitmap-write.c\nindex 1c8070f99c0..2d5ff8fd406 100644\n--- a/pack-bitmap-write.c\n+++ b/pack-bitmap-write.c\n@@ -456,10 +456,10 @@ static void bitmap_builder_clear(struct bitmap_builder *bb)\n \n static int fill_bitmap_tree(struct bitmap_writer *writer,\n \t\t\t struct bitmap *bitmap,\n-\t\t\t struct tree *tree)\n+\t\t\t struct tree *tree,\n+\t\t\t uint32_t pos)\n {\n \tint found;\n-\tuint32_t pos;\n \tstruct tree_desc desc;\n \tstruct name_entry entry;\n \n@@ -467,9 +467,6 @@ static int fill_bitmap_tree(struct bitmap_writer *writer,\n \t * If our bit is already set, then there is nothing to do. Both this\n \t * tree and all of its children will be set.\n \t */\n-\tpos = find_object_pos(writer, &tree->object.oid, &found);\n-\tif (!found)\n-\t\treturn -1;\n \tif (bitmap_get(bitmap, pos))\n \t\treturn 0;\n \tbitmap_set(bitmap, pos);\n@@ -482,8 +479,12 @@ static int fill_bitmap_tree(struct bitmap_writer *writer,\n \twhile (tree_entry(&desc, &entry)) {\n \t\tswitch (object_type(entry.mode)) {\n \t\tcase OBJ_TREE:\n+\t\t\tpos = find_object_pos(writer, &entry.oid, &found);\n+\t\t\tif (!found)\n+\t\t\t\treturn -1;\n \t\t\tif (fill_bitmap_tree(writer, bitmap,\n-\t\t\t\t\t lookup_tree(writer->repo, &entry.oid)) < 0)\n+\t\t\t\t\t lookup_tree(writer->repo,\n+\t\t\t\t\t\t\t &entry.oid), pos) < 0)\n \t\t\t\treturn -1;\n \t\t\tbreak;\n \t\tcase OBJ_BLOB:\n@@ -575,8 +576,14 @@ static int fill_bitmap_commit(struct bitmap_writer *writer,\n \t}\n \n \twhile (tree_queue->nr) {\n-\t\tif (fill_bitmap_tree(writer, ent->bitmap,\n-\t\t\t\t prio_queue_get(tree_queue)) < 0)\n+\t\tstruct tree *t = prio_queue_get(tree_queue);\n+\t\tint found;\n+\n+\t\tpos = find_object_pos(writer, &t->object.oid, &found);\n+\t\tif (!found)\n+\t\t\treturn -1;\n+\n+\t\tif (fill_bitmap_tree(writer, ent->bitmap, t, pos) < 0)\n \t\t\treturn -1;\n \t}\n \treturn 0;\n-- \n2.54.0.rc1.84.g30ce254312c\n\n"},{"id":"543673","messageId":"7d6d1cec0dd2706ba176c7fa070da46c98155018.1779207127.git.me@ttaylorr.com","threadId":"65661","inReplyTo":"cover.1779207127.git.me@ttaylorr.com","subject":"[PATCH 2/8] pack-bitmap: check subtree bits before recursing","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2026-05-19T16:12:39Z","receivedAt":"2026-05-19T16:12:41Z","isPatch":true,"body":"In the previous commit, we adjusted the callers of `fill_bitmap_tree()`\nto pass in the bit position of the tree they wish to fill.\n\nThis commit makes use of that information at the call site to avoid\nsetting up a stack frame for fill_bitmap_tree() entirely whenever a\ntree's bit position is already set.\n\nSince this is such a hot path, the avoided cost of setting up and\ntearing down stack frames for each noop'd call to `fill_bitmap_tree()`\nis significant:\n\n +--------------+-------------+-------------+-------------------+\n | | HEAD^ | HEAD | Delta |\n +--------------+-------------+-------------+-------------------+\n | elapsed | 582.4 s | 562.8 s | -19.6 s (-3.4%) |\n | cycles | 2,713.3 B | 2,621.3 B | -92.0 B (-3.4%) |\n | instructions | 2,415.5 B | 2,348.9 B | -66.6 B (-2.8%) |\n | CPI | 1.123 | 1.116 | -0.007 (-0.7%) |\n +--------------+-------------+-------------+-------------------+\n\nIn the same repository as in the previous commit, our timings dropped\nfrom ~582.4 seconds down to ~562.77 seconds.\n\nWhile the cycles-per-instruction ratio is basically unchanged, we\nexecute significantly fewer instructions, and correspondingly fewer\ncycles.\n\nSigned-off-by: Taylor Blau \n---\n pack-bitmap-write.c | 23 +++++++++++++++++------\n 1 file changed, 17 insertions(+), 6 deletions(-)\n\ndiff --git a/pack-bitmap-write.c b/pack-bitmap-write.c\nindex 2d5ff8fd406..72610397020 100644\n--- a/pack-bitmap-write.c\n+++ b/pack-bitmap-write.c\n@@ -463,12 +463,6 @@ static int fill_bitmap_tree(struct bitmap_writer *writer,\n \tstruct tree_desc desc;\n \tstruct name_entry entry;\n \n-\t/*\n-\t * If our bit is already set, then there is nothing to do. Both this\n-\t * tree and all of its children will be set.\n-\t */\n-\tif (bitmap_get(bitmap, pos))\n-\t\treturn 0;\n \tbitmap_set(bitmap, pos);\n \n \tif (repo_parse_tree(writer->repo, tree) < 0)\n@@ -482,6 +476,15 @@ static int fill_bitmap_tree(struct bitmap_writer *writer,\n \t\t\tpos = find_object_pos(writer, &entry.oid, &found);\n \t\t\tif (!found)\n \t\t\t\treturn -1;\n+\t\t\tif (bitmap_get(bitmap, pos)) {\n+\t\t\t\t/*\n+\t\t\t\t * If our bit is already set, then there\n+\t\t\t\t * is nothing to do. Both this tree and\n+\t\t\t\t * all of its children will be set.\n+\t\t\t\t */\n+\t\t\t\tbreak;\n+\t\t\t}\n+\n \t\t\tif (fill_bitmap_tree(writer, bitmap,\n \t\t\t\t\t lookup_tree(writer->repo,\n \t\t\t\t\t\t\t &entry.oid), pos) < 0)\n@@ -582,6 +585,14 @@ static int fill_bitmap_commit(struct bitmap_writer *writer,\n \t\tpos = find_object_pos(writer, &t->object.oid, &found);\n \t\tif (!found)\n \t\t\treturn -1;\n+\t\tif (bitmap_get(ent->bitmap, pos)) {\n+\t\t\t/*\n+\t\t\t * If our bit is already set, then there is\n+\t\t\t * nothing to do. Both this tree and all of its\n+\t\t\t * children will be set.\n+\t\t\t */\n+\t\t\tcontinue;\n+\t\t}\n \n \t\tif (fill_bitmap_tree(writer, ent->bitmap, t, pos) < 0)\n \t\t\treturn -1;\n-- \n2.54.0.rc1.84.g30ce254312c\n\n"},{"id":"543674","messageId":"6e1f6bef5f641481a6a875bc215b35fc56cef80c.1779207127.git.me@ttaylorr.com","threadId":"65661","inReplyTo":"cover.1779207127.git.me@ttaylorr.com","subject":"[PATCH 3/8] pack-bitmap: reuse stored selected bitmaps","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2026-05-19T16:12:41Z","receivedAt":"2026-05-19T16:12:44Z","isPatch":true,"body":"When `fill_bitmap_commit()` reaches an ancestor that was selected for\nits own bitmap and processed earlier, its object closure is already\nstored in `writer->bitmaps` as an EWAH bitmap. As a result, walking\nthrough that commit's tree and parents again is redundant.\n\nTeach `fill_bitmap_commit()` to notice that case. For non-root commits in\nthe walk, look for a stored selected bitmap and OR it into the bitmap\nbeing built. If one exists, skip the commit, its tree, and its parents.\n\nBuilding bitmaps from scratch on the same test repository from the\nprevious commits yields a significant speed-up:\n\n +------------------+-------------+-------------+---------------------+\n | | HEAD^ | HEAD | Delta |\n +------------------+-------------+-------------+---------------------+\n | elapsed | 562.8 s | 324.8 s | -237.9 s (-42.3%) |\n | cycles | 2,621.3 B | 1,508.6 B | -1,112.7 B (-42.4%) |\n | instructions | 2,348.9 B | 1,436.6 B | -912.3 B (-38.8%) |\n | CPI | 1.116 | 1.050 | -0.066 (-5.9%) |\n +------------------+-------------+-------------+---------------------+\n\nIn our testing repository, there are 1,261 commits selected for bitmap\ncoverage, and 1,382 maximal commits induced as a result of that. Of the\n1,382 calls made to `fill_bitmap_commit()` (one per maximal commit), 131\nof them can be short-circuited at some point during their traversal as a\nconsequence of this change.\n\nIn large repositories where the cost of filling the bitmap for any\nindividual commit is large, being able to short-circuit even ~9.5% of\nthe calls to `fill_bitmap_commit()` results in a significant savings.\n\nSigned-off-by: Taylor Blau \n---\n pack-bitmap-write.c | 34 ++++++++++++++++++++++++++++++++++\n 1 file changed, 34 insertions(+)\n\ndiff --git a/pack-bitmap-write.c b/pack-bitmap-write.c\nindex 72610397020..651ad467469 100644\n--- a/pack-bitmap-write.c\n+++ b/pack-bitmap-write.c\n@@ -509,6 +509,9 @@ static int fill_bitmap_tree(struct bitmap_writer *writer,\n static int reused_bitmaps_nr;\n static int reused_pseudo_merge_bitmaps_nr;\n \n+static int fill_bitmap_commit_calls_nr;\n+static int fill_bitmap_commit_found_ancestor_nr;\n+\n static int fill_bitmap_commit(struct bitmap_writer *writer,\n \t\t\t struct bb_commit *ent,\n \t\t\t struct commit *commit,\n@@ -519,6 +522,9 @@ static int fill_bitmap_commit(struct bitmap_writer *writer,\n {\n \tint found;\n \tuint32_t pos;\n+\n+\tfill_bitmap_commit_calls_nr++;\n+\n \tif (!ent->bitmap)\n \t\tent->bitmap = bitmap_new();\n \n@@ -553,6 +559,28 @@ static int fill_bitmap_commit(struct bitmap_writer *writer,\n \t\t\tbitmap_free(remapped);\n \t\t}\n \n+\t\t/*\n+\t\t * If we encounter an ancestor for which we have already\n+\t\t * computed a bitmap during this build (i.e. a regular\n+\t\t * selected commit processed earlier in topo order), we can\n+\t\t * short-circuit the walk: its stored bitmap already covers\n+\t\t * the commit itself, its tree, and all of its ancestors.\n+\t\t */\n+\t\tif (c != commit) {\n+\t\t\tkhiter_t hash_pos = kh_get_oid_map(writer->bitmaps,\n+\t\t\t\t\t\t\t c->object.oid);\n+\t\t\tif (hash_pos != kh_end(writer->bitmaps)) {\n+\t\t\t\tstruct bitmapped_commit *stored =\n+\t\t\t\t\tkh_value(writer->bitmaps, hash_pos);\n+\t\t\t\tif (stored && stored->bitmap) {\n+\t\t\t\t\tfill_bitmap_commit_found_ancestor_nr++;\n+\t\t\t\t\tbitmap_or_ewah(ent->bitmap,\n+\t\t\t\t\t\t stored->bitmap);\n+\t\t\t\t\tcontinue;\n+\t\t\t\t}\n+\t\t\t}\n+\t\t}\n+\n \t\t/*\n \t\t * Mark ourselves and queue our tree. The commit\n \t\t * walk ensures we cover all parents.\n@@ -692,6 +720,12 @@ int bitmap_writer_build(struct bitmap_writer *writer)\n \ttrace2_data_intmax(\"pack-bitmap-write\", writer->repo,\n \t\t\t \"building_bitmaps_pseudo_merge_reused\",\n \t\t\t reused_pseudo_merge_bitmaps_nr);\n+\ttrace2_data_intmax(\"pack-bitmap-write\", writer->repo,\n+\t\t\t \"fill_bitmap_commit_calls_nr\",\n+\t\t\t fill_bitmap_commit_calls_nr);\n+\ttrace2_data_intmax(\"pack-bitmap-write\", writer->repo,\n+\t\t\t \"fill_bitmap_commit_found_ancestor_nr\",\n+\t\t\t fill_bitmap_commit_found_ancestor_nr);\n \n \tstop_progress(&writer->progress);\n \n-- \n2.54.0.rc1.84.g30ce254312c\n\n"},{"id":"543675","messageId":"c9a560660949c53575a9b1e81160d25212a1f484.1779207127.git.me@ttaylorr.com","threadId":"65661","inReplyTo":"cover.1779207127.git.me@ttaylorr.com","subject":"[PATCH 4/8] pack-bitmap: consolidate `find_object_pos()` success path","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2026-05-19T16:12:44Z","receivedAt":"2026-05-19T16:12:46Z","isPatch":true,"body":"Both sides of `find_object_pos()` report success in the same way by\nsetting the optional `found` out-parameter and return the resolved\nbitmap position.\n\nPrepare for adding more bookkeeping around object-position lookups by\nstoring the result in a local `pos` variable and sharing the success\nreturn path between the packlist and MIDX cases.\n\nSigned-off-by: Taylor Blau \n---\n pack-bitmap-write.c | 17 ++++++++---------\n 1 file changed, 8 insertions(+), 9 deletions(-)\n\ndiff --git a/pack-bitmap-write.c b/pack-bitmap-write.c\nindex 651ad467469..6483fdc7daf 100644\n--- a/pack-bitmap-write.c\n+++ b/pack-bitmap-write.c\n@@ -224,23 +224,22 @@ static uint32_t find_object_pos(struct bitmap_writer *writer,\n \t\tif (writer->midx)\n \t\t\tbase_objects = writer->midx->num_objects +\n \t\t\t\twriter->midx->num_objects_in_base;\n-\n-\t\tif (found)\n-\t\t\t*found = 1;\n-\t\treturn oe_in_pack_pos(writer->to_pack, entry) + base_objects;\n+\t\tpos = oe_in_pack_pos(writer->to_pack, entry) + base_objects;\n \t} else if (writer->midx) {\n-\t\tuint32_t at, pos;\n+\t\tuint32_t at;\n \n \t\tif (!bsearch_midx(oid, writer->midx, &at))\n \t\t\tgoto missing;\n \t\tif (midx_to_pack_pos(writer->midx, at, &pos) < 0)\n \t\t\tgoto missing;\n-\n-\t\tif (found)\n-\t\t\t*found = 1;\n-\t\treturn pos;\n+\t} else {\n+\t\tgoto missing;\n \t}\n \n+\tif (found)\n+\t\t*found = 1;\n+\treturn pos;\n+\n missing:\n \tif (found)\n \t\t*found = 0;\n-- \n2.54.0.rc1.84.g30ce254312c\n\n"},{"id":"543676","messageId":"e43ef6a42d13578a6b7a4a346f491e51a6edfd14.1779207127.git.me@ttaylorr.com","threadId":"65661","inReplyTo":"cover.1779207127.git.me@ttaylorr.com","subject":"[PATCH 5/8] pack-bitmap: cache object positions during fill","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2026-05-19T16:12:47Z","receivedAt":"2026-05-19T16:12:49Z","isPatch":true,"body":"The previous commits removed some redundant work from bitmap generation\nby avoiding unnecessary tree recursion and by reusing selected bitmaps\nthat have already been computed.\n\nEven with those changes in place, there is still an extremely hot path\nfrom `fill_bitmap_commit()` and `fill_bitmap_tree()` to translate object\nIDs into their corresponding bit positions in order to generate their\nbitmaps.\n\nIn a small repository, this overhead is not significant. However, in a\nvery large repository (e.g., the one that we have been using as a\nbenchmark over the past several commits with ~57M total objects), the\noverhead of locating object bit positions (often repeatedly) adds up\nsignificantly.\n\nCombat this by adding a small, direct-mapped cache to the bitmap writer\nwhich maps object IDs to their corresponding bit positions. Size the\ncache according to the number of objects being written, with fixed lower\nand upper bounds so small repositories do not pay for a large table and\nlarge repositories can avoid most repeated packlist and MIDX lookups.\n\nOn my machine with (a somewhat outdated) GCC 15.2.0, each entry in the\ncache is 40 bytes wide:\n\n $ pahole -C bitmap_pos_cache_entry pack-bitmap-write.o\n struct bitmap_pos_cache_entry {\n struct object_id oid; /* 0 36 */\n uint32_t pos; /* 36 4 */\n\n /* size: 40, cachelines: 1, members: 2 */\n /* last cacheline: 40 bytes */\n };\n\n, and we will allocate up to 2^21 entries for a maximum total of 80 MiB\nof cache overhead.\n\nIn our example repository from above and in earlier commits, this\nresults in a ~9.4% reduction in runtime relative to the previous commit:\n\n +------------------+-------------+-------------+---------------------+\n | | HEAD^ | HEAD | Delta |\n +------------------+-------------+-------------+---------------------+\n | elapsed | 324.8 s | 294.1 s | -30.7 s (-9.4%) |\n | cycles | 1,508.6 B | 1,365.5 B | -143.0 B (-9.5%) |\n | instructions | 1,436.6 B | 1,389.8 B | -46.9 B (-3.3%) |\n | CPI | 1.050 | 0.983 | -0.068 (-6.4%) |\n +------------------+-------------+-------------+---------------------+\n\nWhen generating bitmaps on this repository (to produce the above\ntimings), the cache grew to its maximum size of 80 MiB, and resulted in\n1.024B cache hits and 59.957M cache misses.\n\nSigned-off-by: Taylor Blau \n---\n pack-bitmap-write.c | 89 ++++++++++++++++++++++++++++++++++++++++++++-\n pack-bitmap.h | 7 ++++\n 2 files changed, 95 insertions(+), 1 deletion(-)\n\ndiff --git a/pack-bitmap-write.c b/pack-bitmap-write.c\nindex 6483fdc7daf..4b6fb07edd7 100644\n--- a/pack-bitmap-write.c\n+++ b/pack-bitmap-write.c\n@@ -89,6 +89,7 @@ void bitmap_writer_free(struct bitmap_writer *writer)\n \tewah_free(writer->tags);\n \n \tkh_destroy_oid_map(writer->bitmaps);\n+\tfree(writer->pos_cache);\n \n \tkh_foreach_value(writer->pseudo_merge_commits, idx,\n \t\t\t free_pseudo_merge_commit_idx(idx));\n@@ -213,14 +214,92 @@ void bitmap_writer_push_commit(struct bitmap_writer *writer,\n \twriter->selected_nr++;\n }\n \n+struct bitmap_pos_cache_entry {\n+\tstruct object_id oid;\n+\tuint32_t pos;\n+};\n+\n+#define BITMAP_POS_MIN_CACHE_SIZE (1U << 10)\n+#define BITMAP_POS_MAX_CACHE_SIZE (1U << 21)\n+#define BITMAP_POS_CACHE_VALID (1U << 31)\n+\n+static void bitmap_writer_init_pos_cache(struct bitmap_writer *writer)\n+{\n+\tif (writer->pos_cache)\n+\t\treturn;\n+\n+\twriter->pos_cache_nr = BITMAP_POS_MIN_CACHE_SIZE;\n+\n+\twhile (writer->pos_cache_nr < writer->to_pack->nr_objects &&\n+\t writer->pos_cache_nr < BITMAP_POS_MAX_CACHE_SIZE)\n+\t\twriter->pos_cache_nr <<= 1;\n+\n+\tCALLOC_ARRAY(writer->pos_cache, writer->pos_cache_nr);\n+}\n+\n+static size_t bitmap_writer_pos_cache_slot(struct bitmap_writer *writer,\n+\t\t\t\t\t const struct object_id *oid)\n+{\n+\treturn oidhash(oid) & (writer->pos_cache_nr - 1);\n+}\n+\n+static bool bitmap_writer_pos_cache_valid(struct bitmap_writer *writer,\n+\t\t\t\t\t size_t slot)\n+{\n+\treturn !!(writer->pos_cache[slot].pos & BITMAP_POS_CACHE_VALID);\n+}\n+\n+static int find_cached_object_pos(struct bitmap_writer *writer,\n+\t\t\t\t const struct object_id *oid, uint32_t *pos)\n+{\n+\tsize_t slot = bitmap_writer_pos_cache_slot(writer, oid);\n+\n+\tif (bitmap_writer_pos_cache_valid(writer, slot) &&\n+\t oideq(&writer->pos_cache[slot].oid, oid)) {\n+\t\twriter->pos_cache_hits++;\n+\t\t*pos = writer->pos_cache[slot].pos & ~BITMAP_POS_CACHE_VALID;\n+\t\treturn 1;\n+\t}\n+\n+\twriter->pos_cache_misses++;\n+\treturn 0;\n+}\n+\n+static uint32_t store_cached_object_pos(struct bitmap_writer *writer,\n+\t\t\t\t\tconst struct object_id *oid,\n+\t\t\t\t\tuint32_t pos)\n+{\n+\tsize_t slot;\n+\n+\tif (pos & BITMAP_POS_CACHE_VALID)\n+\t\treturn pos; /* too large to cache */\n+\n+\tslot = bitmap_writer_pos_cache_slot(writer, oid);\n+\n+\toidcpy(&writer->pos_cache[slot].oid, oid);\n+\twriter->pos_cache[slot].pos = pos | BITMAP_POS_CACHE_VALID;\n+\n+\treturn pos;\n+}\n+\n static uint32_t find_object_pos(struct bitmap_writer *writer,\n \t\t\t\tconst struct object_id *oid, int *found)\n {\n \tstruct object_entry *entry;\n+\tuint32_t pos;\n+\n+\tbitmap_writer_init_pos_cache(writer);\n+\n+\tif (find_cached_object_pos(writer, oid, &pos)) {\n+\t\tif (found)\n+\t\t\t*found = 1;\n+\t\treturn pos;\n+\t}\n \n \tentry = packlist_find(writer->to_pack, oid);\n \tif (entry) {\n \t\tuint32_t base_objects = 0;\n+\n \t\tif (writer->midx)\n \t\t\tbase_objects = writer->midx->num_objects +\n \t\t\t\twriter->midx->num_objects_in_base;\n@@ -238,7 +317,7 @@ static uint32_t find_object_pos(struct bitmap_writer *writer,\n \n \tif (found)\n \t\t*found = 1;\n-\treturn pos;\n+\treturn store_cached_object_pos(writer, oid, pos);\n \n missing:\n \tif (found)\n@@ -661,6 +740,10 @@ int bitmap_writer_build(struct bitmap_writer *writer)\n \t\twriter->progress = start_progress(writer->repo,\n \t\t\t\t\t\t \"Building bitmaps\",\n \t\t\t\t\t\t writer->selected_nr);\n+\n+\twriter->pos_cache_hits = 0;\n+\twriter->pos_cache_misses = 0;\n+\n \ttrace2_region_enter(\"pack-bitmap-write\", \"building_bitmaps_total\",\n \t\t\t writer->repo);\n \n@@ -725,6 +808,10 @@ int bitmap_writer_build(struct bitmap_writer *writer)\n \ttrace2_data_intmax(\"pack-bitmap-write\", writer->repo,\n \t\t\t \"fill_bitmap_commit_found_ancestor_nr\",\n \t\t\t fill_bitmap_commit_found_ancestor_nr);\n+\ttrace2_data_intmax(\"pack-bitmap-write\", writer->repo,\n+\t\t\t \"bitmap_pos_cache_hits\", writer->pos_cache_hits);\n+\ttrace2_data_intmax(\"pack-bitmap-write\", writer->repo,\n+\t\t\t \"bitmap_pos_cache_misses\", writer->pos_cache_misses);\n \n \tstop_progress(&writer->progress);\n \ndiff --git a/pack-bitmap.h b/pack-bitmap.h\nindex a95e1c2d115..19a86554579 100644\n--- a/pack-bitmap.h\n+++ b/pack-bitmap.h\n@@ -132,6 +132,8 @@ int bitmap_has_oid_in_uninteresting(struct bitmap_index *, const struct object_i\n \n off_t get_disk_usage_from_bitmap(struct bitmap_index *, struct rev_info *);\n \n+struct bitmap_pos_cache_entry;\n+\n struct bitmap_writer {\n \tstruct repository *repo;\n \tstruct ewah_bitmap *commits;\n@@ -143,6 +145,11 @@ struct bitmap_writer {\n \tstruct packing_data *to_pack;\n \tstruct multi_pack_index *midx; /* if appending to a MIDX chain */\n \n+\tstruct bitmap_pos_cache_entry *pos_cache;\n+\tsize_t pos_cache_nr;\n+\tuint64_t pos_cache_hits;\n+\tuint64_t pos_cache_misses;\n+\n \tstruct bitmapped_commit *selected;\n \tunsigned int selected_nr, selected_alloc;\n \n-- \n2.54.0.rc1.84.g30ce254312c\n\n"},{"id":"543677","messageId":"b0a4f31353a7053ab37b6d8c8f22c69bcfadfe50.1779207127.git.me@ttaylorr.com","threadId":"65661","inReplyTo":"cover.1779207127.git.me@ttaylorr.com","subject":"[PATCH 6/8] pack-bitmap: sort bitmaps before XORing","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2026-05-19T16:12:50Z","receivedAt":"2026-05-19T16:12:53Z","isPatch":true,"body":"Reachability bitmaps may be stored as XORs against nearby bitmaps, up to\n10 away. However, when callers provide selected commits in an arbitrary\norder, the writer may miss good ancestor/descendant pairs and produce\nmuch larger bitmap files without changing query coverage.\n\nSort the selected bitmaps in date order (from oldest to newest) before\ncomputing XOR offsets, leaving pseudo-merge bitmaps alone (which we will\ndeal with separately in following commits).\n\nOn our same testing repository from previous commits, this change shrunk\nour selection of 1,261 bitmaps from ~635.46 MiB to 176.4 MiB for a\n~72.24% reduction in the on-disk size of our *.bitmap file. The time to\ngenerate the smaller bitmap file decreased by ~3.69 seconds, though this\nis likely mostly noise.\n\nSigned-off-by: Taylor Blau \n---\n pack-bitmap-write.c | 29 +++++++++++++++++++++++++++++\n 1 file changed, 29 insertions(+)\n\ndiff --git a/pack-bitmap-write.c b/pack-bitmap-write.c\nindex 4b6fb07edd7..66282ea14b5 100644\n--- a/pack-bitmap-write.c\n+++ b/pack-bitmap-write.c\n@@ -327,11 +327,40 @@ static uint32_t find_object_pos(struct bitmap_writer *writer,\n \treturn 0;\n }\n \n+static int bitmapped_commit_date_cmp(const void *_a, const void *_b)\n+{\n+\tconst struct bitmapped_commit *a = _a;\n+\tconst struct bitmapped_commit *b = _b;\n+\n+\tif (a->commit->date < b->commit->date)\n+\t\treturn -1;\n+\tif (a->commit->date > b->commit->date)\n+\t\treturn 1;\n+\treturn 0;\n+}\n+\n static void compute_xor_offsets(struct bitmap_writer *writer)\n {\n \tstatic const int MAX_XOR_OFFSET_SEARCH = 10;\n \n \tint i, next = 0;\n+\tint nr = bitmap_writer_nr_selected_commits(writer);\n+\n+\tif (nr > 1) {\n+\t\tQSORT(writer->selected, nr, bitmapped_commit_date_cmp);\n+\n+\t\tfor (i = 0; i < nr; i++) {\n+\t\t\tstruct bitmapped_commit *stored = &writer->selected[i];\n+\t\t\tkhiter_t hash_pos = kh_get_oid_map(writer->bitmaps,\n+\t\t\t\t\t\t\t stored->commit->object.oid);\n+\n+\t\t\tif (hash_pos == kh_end(writer->bitmaps))\n+\t\t\t\tBUG(\"selected commit missing from bitmap map: %s\",\n+\t\t\t\t oid_to_hex(&stored->commit->object.oid));\n+\n+\t\t\tkh_value(writer->bitmaps, hash_pos) = stored;\n+\t\t}\n+\t}\n \n \twhile (next < writer->selected_nr) {\n \t\tstruct bitmapped_commit *stored = &writer->selected[next];\n-- \n2.54.0.rc1.84.g30ce254312c\n\n"},{"id":"543678","messageId":"0bd88e6a096223f117d71dc248b61770178b178c.1779207127.git.me@ttaylorr.com","threadId":"65661","inReplyTo":"cover.1779207127.git.me@ttaylorr.com","subject":"[PATCH 7/8] pack-bitmap: remember pseudo-merge parents","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2026-05-19T16:12:53Z","receivedAt":"2026-05-19T16:12:55Z","isPatch":true,"body":"write_pseudo_merges() currently builds an array of temporary bitmaps for\nthe parent set of each pseudo-merge, then serializes those bitmaps later\nwhile writing the extension.\n\nMove those parent bitmaps onto the corresponding bitmapped_commit\nentries instead. This keeps the on-disk output unchanged, but gives the\nparent bitmap the same lifetime and access pattern that later changes\nwill use when pseudo-merge object bitmaps are built before the write\nstep.\n\nSigned-off-by: Taylor Blau \n---\n pack-bitmap-write.c | 30 +++++++++++++++++-------------\n 1 file changed, 17 insertions(+), 13 deletions(-)\n\ndiff --git a/pack-bitmap-write.c b/pack-bitmap-write.c\nindex 66282ea14b5..8200aed6101 100644\n--- a/pack-bitmap-write.c\n+++ b/pack-bitmap-write.c\n@@ -32,6 +32,7 @@ struct bitmapped_commit {\n \tstruct commit *commit;\n \tstruct ewah_bitmap *bitmap;\n \tstruct ewah_bitmap *write_as;\n+\tstruct ewah_bitmap *pseudo_merge_parents;\n \tint flags;\n \tint xor_offset;\n \tuint32_t commit_pos;\n@@ -102,6 +103,7 @@ void bitmap_writer_free(struct bitmap_writer *writer)\n \t\tif (bc->write_as != bc->bitmap)\n \t\t\tewah_free(bc->write_as);\n \t\tewah_free(bc->bitmap);\n+\t\tewah_free(bc->pseudo_merge_parents);\n \t}\n \tfree(writer->selected);\n }\n@@ -210,6 +212,7 @@ void bitmap_writer_push_commit(struct bitmap_writer *writer,\n \twriter->selected[writer->selected_nr].write_as = NULL;\n \twriter->selected[writer->selected_nr].flags = 0;\n \twriter->selected[writer->selected_nr].pseudo_merge = pseudo_merge;\n+\twriter->selected[writer->selected_nr].pseudo_merge_parents = NULL;\n \n \twriter->selected_nr++;\n }\n@@ -1004,42 +1007,47 @@ static void write_pseudo_merges(struct bitmap_writer *writer,\n \t\t\t\tstruct hashfile *f)\n {\n \tstruct oid_array commits = OID_ARRAY_INIT;\n-\tstruct bitmap **commits_bitmap = NULL;\n \toff_t *pseudo_merge_ofs = NULL;\n \toff_t start, table_start, next_ext;\n \n \tuint32_t base = bitmap_writer_nr_selected_commits(writer);\n \tsize_t i, j = 0;\n \n-\tCALLOC_ARRAY(commits_bitmap, writer->pseudo_merges_nr);\n \tCALLOC_ARRAY(pseudo_merge_ofs, writer->pseudo_merges_nr);\n \n \tfor (i = 0; i < writer->pseudo_merges_nr; i++) {\n \t\tstruct bitmapped_commit *merge = &writer->selected[base + i];\n \t\tstruct commit_list *p;\n+\t\tstruct bitmap *parents = bitmap_new();\n \n \t\tif (!merge->pseudo_merge)\n \t\t\tBUG(\"found non-pseudo merge commit at %\"PRIuMAX, (uintmax_t)i);\n \n-\t\tcommits_bitmap[i] = bitmap_new();\n-\n \t\tfor (p = merge->commit->parents; p; p = p->next)\n-\t\t\tbitmap_set(commits_bitmap[i],\n+\t\t\tbitmap_set(parents,\n \t\t\t\t find_object_pos(writer, &p->item->object.oid,\n \t\t\t\t\t\t NULL));\n+\n+\t\tmerge->pseudo_merge_parents = bitmap_to_ewah(parents);\n+\t\tbitmap_free(parents);\n \t}\n \n \tstart = hashfile_total(f);\n \n \tfor (i = 0; i < writer->pseudo_merges_nr; i++) {\n-\t\tstruct ewah_bitmap *commits_ewah = bitmap_to_ewah(commits_bitmap[i]);\n+\t\tstruct bitmapped_commit *merge = &writer->selected[base + i];\n+\n+\t\tif (!merge->pseudo_merge)\n+\t\t\tBUG(\"found non-pseudo merge commit at %\"PRIuMAX, (uintmax_t)i);\n+\n+\t\tif (!merge->pseudo_merge_parents)\n+\t\t\tBUG(\"missing pseudo-merge parents bitmap for commit %s\",\n+\t\t\t oid_to_hex(&merge->commit->object.oid));\n \n \t\tpseudo_merge_ofs[i] = hashfile_total(f);\n \n-\t\tdump_bitmap(f, commits_ewah);\n+\t\tdump_bitmap(f, merge->pseudo_merge_parents);\n \t\tdump_bitmap(f, writer->selected[base+i].write_as);\n-\n-\t\tewah_free(commits_ewah);\n \t}\n \n \tnext_ext = st_add(hashfile_total(f),\n@@ -1122,12 +1130,8 @@ static void write_pseudo_merges(struct bitmap_writer *writer,\n \thashwrite_be64(f, table_start - start);\n \thashwrite_be64(f, hashfile_total(f) - start + sizeof(uint64_t));\n \n-\tfor (i = 0; i < writer->pseudo_merges_nr; i++)\n-\t\tbitmap_free(commits_bitmap[i]);\n-\n \toid_array_clear(&commits);\n \tfree(pseudo_merge_ofs);\n-\tfree(commits_bitmap);\n }\n \n static int table_cmp(const void *_va, const void *_vb, void *_data)\n-- \n2.54.0.rc1.84.g30ce254312c\n\n"},{"id":"543679","messageId":"30ce254312cfee2a2a82f08246c3a2546ae32578.1779207127.git.me@ttaylorr.com","threadId":"65661","inReplyTo":"cover.1779207127.git.me@ttaylorr.com","subject":"[PATCH 8/8] pack-bitmap: build pseudo-merge bitmaps after regular bitmaps","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2026-05-19T16:12:55Z","receivedAt":"2026-05-19T16:12:58Z","isPatch":true,"body":"When generating bitmaps, `bitmap_builder_init()` starts with an initial\nselection of commits to receive bitmap coverage, and then determines a\nset of \"maximal\" commits based on its input.\n\nCommit 089f751360f (pack-bitmap-write: build fewer intermediate bitmaps,\n2020-12-08) has extensive details, but the gist is as follows:\n\nEach selected commit starts with one commit_mask bit in its \"commit\nmask\" bitmap. Then, we walk the first-parent history in topological\norder and OR each commit's mask into its (first) parent. Whenever that\nOR results in the parent having more bits set, the child is deemed to be\nnon-maximal, and the frontier is pushed further back along the first\nparent history.\n\nThat approach works extremely well for ordinary selected commits, whose\nfirst-parent histories often describe real sharing between the bitmaps\nwe are going to write.\n\nIt struggles, however, to efficiently generate pseudo-merge bitmaps.\nUnlike ordinary commits for which the above algorithm is designed,\npseudo-merges don't represent any \"real\" commit in history, just a\ngrouping of non-bitmapped reference tips. In that sense, their first\nparent is just a part of a larger set, and treating them like ordinary\nselected commits imposes a significant slow-down when generating bitmaps\nwith pseudo-merges enabled.\n\nConsider partitioning all non-bitmapped reference tips into eight\nindividual pseudo-merges via the following configuration:\n\n [bitmapPseudoMerge \"all\"]\n pattern=refs/\n threshold=now\n stableSize=10000000\n maxMerges=8\n\n, the cost of generating a bitmap from scratch rises significantly:\n\n +------------------+-----------------+---------------+---------------------+\n | | no pseudo-merge | pseudo-merges | Delta |\n | | | (HEAD^) | |\n +------------------+-----------------+---------------+---------------------+\n | elapsed | 294.1 s | 575.0 s | +280.9 s (+95.5%) |\n | cycles | 1,365.5 B | 2,686.9 B | +1,321.4 B (+96.8%) |\n | instructions | 1,389.8 B | 2,546.6 B | +1,156.8 B (+83.2%) |\n | CPI | 0.983 | 1.055 | +0.073 (+7.4%) |\n +------------------+-----------------+---------------+---------------------+\n\nThis is a particularly poor trade-off, because the time saved by these\npseudo-merges during, e.g.,\n\n $ git rev-list --count --all --objects --use-bitmap-index\n\nis only:\n\n $ hyperfine -L v true,false -n 'pseudo-merges: {v}' '\n GIT_TEST_USE_PSEUDO_MERGES={v} git.compile rev-list --count \\\n --objects --all --use-bitmap-index\n '\n\n Benchmark 1: pseudo-merges: true\n Time (mean ± σ): 2.613 s ± 0.012 s [User: 2.308 s, System: 0.305 s]\n Range (min … max): 2.594 s … 2.633 s 10 runs\n\n Benchmark 2: pseudo-merges: false\n Time (mean ± σ): 52.205 s ± 0.170 s [User: 51.500 s, System: 0.697 s]\n Range (min … max): 51.956 s … 52.458 s 10 runs\n\n Summary\n pseudo-merges: true ran\n 19.98 ± 0.11 times faster than pseudo-merges: false\n\nIn other words, we pay a nearly ~5 minute penalty to generate\npseudo-merge bitmaps, but only save ~50 seconds during traversal.\n\nThe problem stems from injecting pseudo-merges into the bitmap builder\nas if they were normal commits. The maximal commit selection algorithm\nwas simply not designed for that case, and performs predictably poorly.\n\nThe only reason we reused the maximal commit selection routine for\npseudo-merges alongside regular non-pseudo-merge commits is because we\nrepresent them both as commit objects (where the pseudo-merge commits\njust represent a made-up commit as opposed to one that actually exists\nin a repository's object store).\n\nInstead, build the regular selected commit bitmaps first, considering\nonly non-pseudo-merge commits in `bitmap_builder_init()`. Once those\nbitmaps have been stored, build each pseudo-merge bitmap separately and\nattach its parent and object bitmaps to the corresponding pseudo-merge\nentry before writing the extension.\n\nThis keeps the regular bitmap build shaped like the no-pseudo-merge\ncase. The later pseudo-merge fill can still stop at stored selected\nancestor bitmaps, so it does not have to rewalk each pseudo-merge\nclosure from scratch.\n\nWhen an existing bitmap has the same pseudo-merge parent set, reuse and\nremap that whole pseudo-merge bitmap before falling back to\nfill_bitmap_commit(). This preserves the benefit of stable pseudo-merges\nwhile keeping the on-disk format and reader behavior unchanged.\n\nAs a result, the overhead cost for generating pseudo-merges in the above\nconfiguration is much smaller:\n\n +------------------+-----------------+---------------+-------------------+\n | | no pseudo-merge | pseudo-merges | Delta |\n | | | (HEAD) | |\n +------------------+-----------------+---------------+-------------------+\n | elapsed | 294.1 s | 328.4 s | +34.3 s (+11.7%) |\n | cycles | 1,365.5 B | 1,529.3 B | +163.7 B (+12.0%) |\n | instructions | 1,389.8 B | 1,552.8 B | +163.0 B (+11.7%) |\n | CPI | 0.983 | 0.985 | +0.002 (+0.2%) |\n +------------------+-----------------+---------------+-------------------+\n\nRecall that at the start of this series, generating reachability bitmaps\ntook 612.5 seconds *without* pseudo-merges. With this commit, it is\nstill ~46.38% *faster* to generate reachability bitmaps *with*\npseudo-merges than it was to generate bitmaps wihtout them at the\nbeginning of this series.\n\nThe changes to implement this are mostly straightforward. We exclude\npseudo-merge commits from the existing bitmap generation, and walk over\nthem in a separate pass, by either reusing an existing on-disk\npseudo-merge, or passing the pseudo-merge commit itself back to the\nexisting routine in `fill_bitmap_commit()`.\n\n(Note that the routine to build pseudo-merge bitmaps is the same both\nbefore and after this change, the difference is only that we do not let\npsuedo-merges participate in determining the set of maximal commits.)\n\nThe only wrinkle is that `fill_bitmap_commit()` must be taught to not\nexpect that all tree objects have been parsed, which is the case for any\nportion of history reachable by one or more pseudo-merge(s), but not by\nany non-pseudo-merge commit selected for bitmapping.\n\nNow that we have decoupled how we generate pseudo-merges from their\nrepresentation, the following commits will improve the API around\nspecifying pseudo-merge groupings during bitmap generation.\n\nSigned-off-by: Taylor Blau \n---\n pack-bitmap-write.c | 210 ++++++++++++++++++++++++++++++++++++--------\n 1 file changed, 174 insertions(+), 36 deletions(-)\n\ndiff --git a/pack-bitmap-write.c b/pack-bitmap-write.c\nindex 8200aed6101..1bcb3f98a42 100644\n--- a/pack-bitmap-write.c\n+++ b/pack-bitmap-write.c\n@@ -446,13 +446,17 @@ static void bitmap_builder_init(struct bitmap_builder *bb,\n \trevs.topo_order = 1;\n \trevs.first_parent_only = 1;\n \n-\tfor (i = 0; i < writer->selected_nr; i++) {\n+\tfor (i = 0; i < bitmap_writer_nr_selected_commits(writer); i++) {\n \t\tstruct bitmapped_commit *bc = &writer->selected[i];\n \t\tstruct bb_commit *ent = bb_data_at(&bb->data, bc->commit);\n \n+\t\tif (bc->pseudo_merge)\n+\t\t\tBUG(\"unexpected pseudo-merge at %\"PRIuMAX,\n+\t\t\t (uintmax_t)i);\n+\n \t\tent->selected = 1;\n \t\tent->maximal = 1;\n-\t\tent->pseudo_merge = bc->pseudo_merge;\n+\t\tent->pseudo_merge = 0;\n \t\tent->idx = i;\n \n \t\tent->commit_mask = bitmap_new();\n@@ -618,6 +622,8 @@ static int fill_bitmap_tree(struct bitmap_writer *writer,\n \n static int reused_bitmaps_nr;\n static int reused_pseudo_merge_bitmaps_nr;\n+static int pseudo_merge_bitmap_nr;\n+static int pseudo_merge_bitmap_parents;\n \n static int fill_bitmap_commit_calls_nr;\n static int fill_bitmap_commit_found_ancestor_nr;\n@@ -631,8 +637,12 @@ static int fill_bitmap_commit(struct bitmap_writer *writer,\n \t\t\t const uint32_t *mapping)\n {\n \tint found;\n+\tint from_pseudo_merge = commit->object.flags & BITMAP_PSEUDO_MERGE;\n \tuint32_t pos;\n \n+\tif (ent->pseudo_merge)\n+\t\tBUG(\"unexpected pseudo-merge commit in fill_bitmap_commit()\");\n+\n \tfill_bitmap_commit_calls_nr++;\n \n \tif (!ent->bitmap)\n@@ -648,10 +658,7 @@ static int fill_bitmap_commit(struct bitmap_writer *writer,\n \t\t\tstruct ewah_bitmap *old;\n \t\t\tstruct bitmap *remapped = bitmap_new();\n \n-\t\t\tif (commit->object.flags & BITMAP_PSEUDO_MERGE)\n-\t\t\t\told = pseudo_merge_bitmap_for_commit(old_bitmap, c);\n-\t\t\telse\n-\t\t\t\told = bitmap_for_commit(old_bitmap, c);\n+\t\t\told = bitmap_for_commit(old_bitmap, c);\n \t\t\t/*\n \t\t\t * If this commit has an old bitmap, then translate that\n \t\t\t * bitmap and add its bits to this one. No need to walk\n@@ -660,10 +667,7 @@ static int fill_bitmap_commit(struct bitmap_writer *writer,\n \t\t\tif (old && !rebuild_bitmap(mapping, old, remapped)) {\n \t\t\t\tbitmap_or(ent->bitmap, remapped);\n \t\t\t\tbitmap_free(remapped);\n-\t\t\t\tif (commit->object.flags & BITMAP_PSEUDO_MERGE)\n-\t\t\t\t\treused_pseudo_merge_bitmaps_nr++;\n-\t\t\t\telse\n-\t\t\t\t\treused_bitmaps_nr++;\n+\t\t\t\treused_bitmaps_nr++;\n \t\t\t\tcontinue;\n \t\t\t}\n \t\t\tbitmap_free(remapped);\n@@ -696,12 +700,32 @@ static int fill_bitmap_commit(struct bitmap_writer *writer,\n \t\t * walk ensures we cover all parents.\n \t\t */\n \t\tif (!(c->object.flags & BITMAP_PSEUDO_MERGE)) {\n+\t\t\tstruct tree *tree;\n+\n+\t\t\tif (from_pseudo_merge && !c->object.parsed) {\n+\t\t\t\t/*\n+\t\t\t\t * Commits reachable from selected\n+\t\t\t\t * non-pseudo-merges are already parsed\n+\t\t\t\t * by the regular bitmap build.\n+\t\t\t\t *\n+\t\t\t\t * However, pseudo-merge fills can also\n+\t\t\t\t * reach commits that were not covered\n+\t\t\t\t * there, so parse any such leftovers\n+\t\t\t\t * before reading their tree or parents.\n+\t\t\t\t */\n+\t\t\t\tif (repo_parse_commit(writer->repo, c))\n+\t\t\t\t\treturn -1;\n+\t\t\t}\n+\n \t\t\tpos = find_object_pos(writer, &c->object.oid, &found);\n \t\t\tif (!found)\n \t\t\t\treturn -1;\n \t\t\tbitmap_set(ent->bitmap, pos);\n-\t\t\tprio_queue_put(tree_queue,\n-\t\t\t\t repo_get_commit_tree(writer->repo, c));\n+\n+\t\t\ttree = repo_get_commit_tree(writer->repo, c);\n+\t\t\tif (!tree)\n+\t\t\t\treturn -1;\n+\t\t\tprio_queue_put(tree_queue, tree);\n \t\t}\n \n \t\tfor (p = c->parents; p; p = p->next) {\n@@ -738,6 +762,137 @@ static int fill_bitmap_commit(struct bitmap_writer *writer,\n \treturn 0;\n }\n \n+static int reuse_pseudo_merge_bitmap(struct bitmap_index *old_bitmap,\n+\t\t\t\t const uint32_t *mapping,\n+\t\t\t\t struct commit *merge,\n+\t\t\t\t struct ewah_bitmap **out)\n+{\n+\tstruct ewah_bitmap *old;\n+\tstruct bitmap *remapped;\n+\n+\tif (!old_bitmap || !mapping)\n+\t\treturn 0;\n+\n+\told = pseudo_merge_bitmap_for_commit(old_bitmap, merge);\n+\tif (!old)\n+\t\treturn 0;\n+\n+\tremapped = bitmap_new();\n+\tif (rebuild_bitmap(mapping, old, remapped) < 0) {\n+\t\tbitmap_free(remapped);\n+\t\treturn 0;\n+\t}\n+\n+\t*out = bitmap_to_ewah(remapped);\n+\tbitmap_free(remapped);\n+\treused_pseudo_merge_bitmaps_nr++;\n+\treturn 1;\n+}\n+\n+static int build_pseudo_merge_bitmap(struct bitmap_writer *writer,\n+\t\t\t\t struct bitmap_index *old_bitmap,\n+\t\t\t\t const uint32_t *mapping,\n+\t\t\t\t struct commit *merge,\n+\t\t\t\t struct ewah_bitmap **out)\n+{\n+\tstruct bb_commit ent = { 0 };\n+\tstruct prio_queue queue = { NULL };\n+\tstruct prio_queue tree_queue = { NULL };\n+\tunsigned parents = commit_list_count(merge->parents);\n+\tint ret;\n+\n+\tent.bitmap = bitmap_new();\n+\n+\tpseudo_merge_bitmap_nr++;\n+\tpseudo_merge_bitmap_parents += parents;\n+\n+\tif (reuse_pseudo_merge_bitmap(old_bitmap, mapping, merge, out)) {\n+\t\tret = 0;\n+\t\tgoto done;\n+\t}\n+\n+\tret = fill_bitmap_commit(writer, &ent, merge, &queue, &tree_queue,\n+\t\t\t\t old_bitmap, mapping);\n+\n+\tif (!ret)\n+\t\t*out = bitmap_to_ewah(ent.bitmap);\n+\n+done:\n+\tbitmap_free(ent.bitmap);\n+\tclear_prio_queue(&queue);\n+\tclear_prio_queue(&tree_queue);\n+\n+\treturn ret;\n+}\n+\n+static int build_pseudo_merge_bitmaps(struct bitmap_writer *writer,\n+\t\t\t\t struct bitmap_index *old_bitmap,\n+\t\t\t\t const uint32_t *mapping,\n+\t\t\t\t int *nr_stored)\n+{\n+\tsize_t i = bitmap_writer_nr_selected_commits(writer);\n+\tint ret = 0;\n+\n+\tif (!writer->pseudo_merges_nr)\n+\t\treturn 0;\n+\n+\ttrace2_region_enter(\"pack-bitmap-write\", \"building_pseudo_merge_bitmaps\",\n+\t\t\t writer->repo);\n+\n+\tfor (; i < writer->selected_nr; i++) {\n+\t\tstruct bitmapped_commit *merge = &writer->selected[i];\n+\t\tstruct commit_list *p;\n+\t\tstruct bitmap *parents = bitmap_new();\n+\t\tstruct ewah_bitmap *objects = NULL;\n+\n+\t\tif (!merge->pseudo_merge)\n+\t\t\tBUG(\"found non-pseudo merge commit at %\"PRIuMAX,\n+\t\t\t (uintmax_t)i);\n+\n+\t\tfor (p = merge->commit->parents; p; p = p->next) {\n+\t\t\tint found;\n+\t\t\tuint32_t pos = find_object_pos(writer,\n+\t\t\t\t\t\t &p->item->object.oid,\n+\t\t\t\t\t\t &found);\n+\t\t\tif (!found) {\n+\t\t\t\tbitmap_free(parents);\n+\t\t\t\tret = -1;\n+\t\t\t\tgoto done;\n+\t\t\t}\n+\t\t\tbitmap_set(parents, pos);\n+\t\t}\n+\n+\t\tmerge->pseudo_merge_parents = bitmap_to_ewah(parents);\n+\t\tbitmap_free(parents);\n+\n+\t\tif (build_pseudo_merge_bitmap(writer, old_bitmap, mapping,\n+\t\t\t\t\t merge->commit, &objects) < 0) {\n+\t\t\tret = -1;\n+\t\t\tgoto done;\n+\t\t}\n+\t\tmerge->bitmap = objects;\n+\n+\t\t(*nr_stored)++;\n+\t\tdisplay_progress(writer->progress, *nr_stored);\n+\t}\n+\n+done:\n+\ttrace2_region_leave(\"pack-bitmap-write\", \"building_pseudo_merge_bitmaps\",\n+\t\t\t writer->repo);\n+\n+\ttrace2_data_intmax(\"pack-bitmap-write\", writer->repo,\n+\t\t\t \"pseudo_merge_bitmap_nr\",\n+\t\t\t pseudo_merge_bitmap_nr);\n+\ttrace2_data_intmax(\"pack-bitmap-write\", writer->repo,\n+\t\t\t \"building_bitmaps_pseudo_merge_reused\",\n+\t\t\t reused_pseudo_merge_bitmaps_nr);\n+\ttrace2_data_intmax(\"pack-bitmap-write\", writer->repo,\n+\t\t\t \"pseudo_merge_bitmap_parents\",\n+\t\t\t pseudo_merge_bitmap_parents);\n+\n+\treturn ret;\n+}\n+\n static void store_selected(struct bitmap_writer *writer,\n \t\t\t struct bb_commit *ent, struct commit *commit)\n {\n@@ -821,6 +976,10 @@ int bitmap_writer_build(struct bitmap_writer *writer)\n \t\t\tbitmap_free(ent->bitmap);\n \t\tent->bitmap = NULL;\n \t}\n+\tif (closed &&\n+\t build_pseudo_merge_bitmaps(writer, old_bitmap, mapping,\n+\t\t\t\t &nr_stored) < 0)\n+\t\tclosed = 0;\n \tclear_prio_queue(&queue);\n \tclear_prio_queue(&tree_queue);\n \tbitmap_builder_clear(&bb);\n@@ -831,9 +990,6 @@ int bitmap_writer_build(struct bitmap_writer *writer)\n \t\t\t writer->repo);\n \ttrace2_data_intmax(\"pack-bitmap-write\", writer->repo,\n \t\t\t \"building_bitmaps_reused\", reused_bitmaps_nr);\n-\ttrace2_data_intmax(\"pack-bitmap-write\", writer->repo,\n-\t\t\t \"building_bitmaps_pseudo_merge_reused\",\n-\t\t\t reused_pseudo_merge_bitmaps_nr);\n \ttrace2_data_intmax(\"pack-bitmap-write\", writer->repo,\n \t\t\t \"fill_bitmap_commit_calls_nr\",\n \t\t\t fill_bitmap_commit_calls_nr);\n@@ -1015,23 +1171,6 @@ static void write_pseudo_merges(struct bitmap_writer *writer,\n \n \tCALLOC_ARRAY(pseudo_merge_ofs, writer->pseudo_merges_nr);\n \n-\tfor (i = 0; i < writer->pseudo_merges_nr; i++) {\n-\t\tstruct bitmapped_commit *merge = &writer->selected[base + i];\n-\t\tstruct commit_list *p;\n-\t\tstruct bitmap *parents = bitmap_new();\n-\n-\t\tif (!merge->pseudo_merge)\n-\t\t\tBUG(\"found non-pseudo merge commit at %\"PRIuMAX, (uintmax_t)i);\n-\n-\t\tfor (p = merge->commit->parents; p; p = p->next)\n-\t\t\tbitmap_set(parents,\n-\t\t\t\t find_object_pos(writer, &p->item->object.oid,\n-\t\t\t\t\t\t NULL));\n-\n-\t\tmerge->pseudo_merge_parents = bitmap_to_ewah(parents);\n-\t\tbitmap_free(parents);\n-\t}\n-\n \tstart = hashfile_total(f);\n \n \tfor (i = 0; i < writer->pseudo_merges_nr; i++) {\n@@ -1040,14 +1179,13 @@ static void write_pseudo_merges(struct bitmap_writer *writer,\n \t\tif (!merge->pseudo_merge)\n \t\t\tBUG(\"found non-pseudo merge commit at %\"PRIuMAX, (uintmax_t)i);\n \n-\t\tif (!merge->pseudo_merge_parents)\n-\t\t\tBUG(\"missing pseudo-merge parents bitmap for commit %s\",\n+\t\tif (!merge->pseudo_merge_parents || !merge->bitmap)\n+\t\t\tBUG(\"missing pseudo-merge bitmap for commit %s\",\n \t\t\t oid_to_hex(&merge->commit->object.oid));\n \n \t\tpseudo_merge_ofs[i] = hashfile_total(f);\n-\n \t\tdump_bitmap(f, merge->pseudo_merge_parents);\n-\t\tdump_bitmap(f, writer->selected[base+i].write_as);\n+\t\tdump_bitmap(f, merge->bitmap);\n \t}\n \n \tnext_ext = st_add(hashfile_total(f),\n-- \n2.54.0.rc1.84.g30ce254312c\n"},{"id":"543743","messageId":"ag3IXa3lKLmQC1tD@szeder.dev","threadId":"65661","inReplyTo":"c9a560660949c53575a9b1e81160d25212a1f484.1779207127.git.me@ttaylorr.com","subject":"Re: [PATCH 4/8] pack-bitmap: consolidate `find_object_pos()` success path","fromName":"SZEDER Gábor","fromEmail":"szeder.dev@gmail.com","sentAt":"2026-05-20T14:42:37Z","receivedAt":"2026-05-20T14:42:51Z","isPatch":true,"body":"On Tue, May 19, 2026 at 12:12:44PM -0400, Taylor Blau wrote:\n> Both sides of `find_object_pos()` report success in the same way by\n> setting the optional `found` out-parameter and return the resolved\n> bitmap position.\n> \n> Prepare for adding more bookkeeping around object-position lookups by\n> storing the result in a local `pos` variable and sharing the success\n\nThis 'pos' variable will only be declared in the next commit,\nresulting in an error building this commit:\n\n pack-bitmap-write.c: In function ‘find_object_pos’:\n pack-bitmap-write.c:227:17: error: ‘pos’ undeclared (first use in this function)\n 227 | pos = oe_in_pack_pos(writer->to_pack, entry) + base_objects;\n | ^~~\n pack-bitmap-write.c:227:17: note: each undeclared identifier is reported only once for each function it appears in\n make: *** [Makefile:2917: pack-bitmap-write.o] Error 1\n\n> return path between the packlist and MIDX cases.\n> \n> Signed-off-by: Taylor Blau \n> ---\n> pack-bitmap-write.c | 17 ++++++++---------\n> 1 file changed, 8 insertions(+), 9 deletions(-)\n> \n> diff --git a/pack-bitmap-write.c b/pack-bitmap-write.c\n> index 651ad467469..6483fdc7daf 100644\n> --- a/pack-bitmap-write.c\n> +++ b/pack-bitmap-write.c\n> @@ -224,23 +224,22 @@ static uint32_t find_object_pos(struct bitmap_writer *writer,\n> \t\tif (writer->midx)\n> \t\t\tbase_objects = writer->midx->num_objects +\n> \t\t\t\twriter->midx->num_objects_in_base;\n> -\n> -\t\tif (found)\n> -\t\t\t*found = 1;\n> -\t\treturn oe_in_pack_pos(writer->to_pack, entry) + base_objects;\n> +\t\tpos = oe_in_pack_pos(writer->to_pack, entry) + base_objects;\n> \t} else if (writer->midx) {\n> -\t\tuint32_t at, pos;\n> +\t\tuint32_t at;\n> \n> \t\tif (!bsearch_midx(oid, writer->midx, &at))\n> \t\t\tgoto missing;\n> \t\tif (midx_to_pack_pos(writer->midx, at, &pos) < 0)\n> \t\t\tgoto missing;\n> -\n> -\t\tif (found)\n> -\t\t\t*found = 1;\n> -\t\treturn pos;\n> +\t} else {\n> +\t\tgoto missing;\n> \t}\n> \n> +\tif (found)\n> +\t\t*found = 1;\n> +\treturn pos;\n> +\n> missing:\n> \tif (found)\n> \t\t*found = 0;\n> -- \n> 2.54.0.rc1.84.g30ce254312c\n> \n"},{"id":"543747","messageId":"ag3reiso1XFh/Jvs@nand.local","threadId":"65661","inReplyTo":"ag3IXa3lKLmQC1tD@szeder.dev","subject":"Re: [PATCH 4/8] pack-bitmap: consolidate `find_object_pos()` success path","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2026-05-20T17:12:26Z","receivedAt":"2026-05-20T17:12:31Z","isPatch":true,"body":"On Wed, May 20, 2026 at 04:42:37PM +0200, SZEDER Gábor wrote:\n> On Tue, May 19, 2026 at 12:12:44PM -0400, Taylor Blau wrote:\n> > Both sides of `find_object_pos()` report success in the same way by\n> > setting the optional `found` out-parameter and return the resolved\n> > bitmap position.\n> >\n> > Prepare for adding more bookkeeping around object-position lookups by\n> > storing the result in a local `pos` variable and sharing the success\n>\n> This 'pos' variable will only be declared in the next commit,\n> resulting in an error building this commit:\n>\n> pack-bitmap-write.c: In function ‘find_object_pos’:\n> pack-bitmap-write.c:227:17: error: ‘pos’ undeclared (first use in this function)\n> 227 | pos = oe_in_pack_pos(writer->to_pack, entry) + base_objects;\n> | ^~~\n> pack-bitmap-write.c:227:17: note: each undeclared identifier is reported only once for each function it appears in\n> make: *** [Makefile:2917: pack-bitmap-write.o] Error 1\n\nThanks for spotting. I had split the patch that immediately follows this\none into two to make the latter easier to read, but have no idea how\nthis snuck through.\n\nIt's fixed by declaring `pos` in this commit:\n\n--- 8< ---\ndiff --git a/pack-bitmap-write.c b/pack-bitmap-write.c\nindex 6483fdc7daf..42ed22feacc 100644\n--- a/pack-bitmap-write.c\n+++ b/pack-bitmap-write.c\n@@ -217,6 +217,7 @@ static uint32_t find_object_pos(struct bitmap_writer *writer,\n \t\t\t\tconst struct object_id *oid, int *found)\n {\n \tstruct object_entry *entry;\n+\tuint32_t pos;\n\n \tentry = packlist_find(writer->to_pack, oid);\n \tif (entry) {\n--- >8 ---\n\n, but I'll send a re-roll after the rest of the series has been\nreviewed.\n\nThanks,\nTaylor\n"},{"id":"544142","messageId":"20260527085740.GB981444@coredump.intra.peff.net","threadId":"65661","inReplyTo":"13191c19b91bc3f5d671b7016b97f2309f12737d.1779207127.git.me@ttaylorr.com","subject":"Re: [PATCH 1/8] pack-bitmap: pass object position to `fill_bitmap_tree()`","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2026-05-27T08:57:40Z","receivedAt":"2026-05-27T08:57:41Z","isPatch":true,"body":"On Tue, May 19, 2026 at 12:12:36PM -0400, Taylor Blau wrote:\n\n> In the following commit, callers of `fill_bitmap_tree()` will be\n> required to check the bit corresponding to their tree before calling\n> that function. That change will reduce the overhead of setting up and\n> tearing down stack frames for trees whose bits are already set.\n> \n> To prepare for that change, have callers pass in the tree's bit position\n> in `fill_bitmap_tree()`, which will make the next commit easier to read.\n> \n> In the meantime, this change has a surprising and measurable benefit\n> during bitmap generation, particularly on very large repositories.\n\nIt is indeed surprising. There's a possible candidate for the speedup\nhere:\n\n> @@ -482,8 +479,12 @@ static int fill_bitmap_tree(struct bitmap_writer *writer,\n> \twhile (tree_entry(&desc, &entry)) {\n> \t\tswitch (object_type(entry.mode)) {\n> \t\tcase OBJ_TREE:\n> +\t\t\tpos = find_object_pos(writer, &entry.oid, &found);\n> +\t\t\tif (!found)\n> +\t\t\t\treturn -1;\n> \t\t\tif (fill_bitmap_tree(writer, bitmap,\n> -\t\t\t\t\t lookup_tree(writer->repo, &entry.oid)) < 0)\n> +\t\t\t\t\t lookup_tree(writer->repo,\n> +\t\t\t\t\t\t\t &entry.oid), pos) < 0)\n> \t\t\t\treturn -1;\n> \t\t\tbreak;\n\nWhenever \"found\" is false, we cut out early and skip the hash lookup in\nlookup_tree() entirely. But that should almost never happen! It implies\nthat a reachable object is not in the pack/midx, and thus the bitmaps is\nnot closed (and we'll refuse to generate it).\n\nSo it really is the case that we do the same operations in a different\norder. Weird.\n\nBut the patch itself looks correct to me, and I get ~6% speedup on a\nfrom-scratch bitmap generation of linux.git. I guess it could vary\nbetween architectures and compilers (I'm using gcc on x86), but since\nthe reorg is setting us up for further optimizations in the next patch,\nI suppose there's no need to look a gift horse in the mouth.\n\n-Peff\n"},{"id":"544143","messageId":"20260527090348.GC981444@coredump.intra.peff.net","threadId":"65661","inReplyTo":"7d6d1cec0dd2706ba176c7fa070da46c98155018.1779207127.git.me@ttaylorr.com","subject":"Re: [PATCH 2/8] pack-bitmap: check subtree bits before recursing","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2026-05-27T09:03:48Z","receivedAt":"2026-05-27T09:03:49Z","isPatch":true,"body":"On Tue, May 19, 2026 at 12:12:39PM -0400, Taylor Blau wrote:\n\n> In the previous commit, we adjusted the callers of `fill_bitmap_tree()`\n> to pass in the bit position of the tree they wish to fill.\n> \n> This commit makes use of that information at the call site to avoid\n> setting up a stack frame for fill_bitmap_tree() entirely whenever a\n> tree's bit position is already set.\n\nOK, this one at least has a plausible explanation. ;)\n\nI can reproduce your speedup on linux.git (~5% again). I don't love that\nwe have to duplicate the logic in each of the callers, but there are\nonly two sites (and unlikely to ever be more). And it is only one line,\nthe comment notwithstanding. That seems like a good tradeoff for a\nmultiple-second speedup.\n\nThe patch itself looks obviously correct.\n\n-Peff\n"},{"id":"544144","messageId":"20260527092412.GD981444@coredump.intra.peff.net","threadId":"65661","inReplyTo":"6e1f6bef5f641481a6a875bc215b35fc56cef80c.1779207127.git.me@ttaylorr.com","subject":"Re: [PATCH 3/8] pack-bitmap: reuse stored selected bitmaps","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2026-05-27T09:24:12Z","receivedAt":"2026-05-27T09:24:15Z","isPatch":true,"body":"On Tue, May 19, 2026 at 12:12:41PM -0400, Taylor Blau wrote:\n\n> Building bitmaps from scratch on the same test repository from the\n> previous commits yields a significant speed-up:\n> \n> +------------------+-------------+-------------+---------------------+\n> | | HEAD^ | HEAD | Delta |\n> +------------------+-------------+-------------+---------------------+\n> | elapsed | 562.8 s | 324.8 s | -237.9 s (-42.3%) |\n> | cycles | 2,621.3 B | 1,508.6 B | -1,112.7 B (-42.4%) |\n> | instructions | 2,348.9 B | 1,436.6 B | -912.3 B (-38.8%) |\n> | CPI | 1.116 | 1.050 | -0.066 (-5.9%) |\n> +------------------+-------------+-------------+---------------------+\n\nOh my, that's a rather nice speedup. I can reproduce here on linux.git\n(~47% improvement).\n\n> When `fill_bitmap_commit()` reaches an ancestor that was selected for\n> its own bitmap and processed earlier, its object closure is already\n> stored in `writer->bitmaps` as an EWAH bitmap. As a result, walking\n> through that commit's tree and parents again is redundant.\n> \n> Teach `fill_bitmap_commit()` to notice that case. For non-root commits in\n> the walk, look for a stored selected bitmap and OR it into the bitmap\n> being built. If one exists, skip the commit, its tree, and its parents.\n\nI feel like this _shouldn't_ be necessary, because the idea of the\ncurrent writing code is to go from the roots up, following inverted\nparent pointers, and passing the bitmap up as we go. So whenever we\nvisit a commit we should in theory have all of the ancestor's bits set\nin that bitmap. But I remember that the simple-and-stupid approach ended\nup being too memory hungry, so we pick some focal points in the graph\nand then fill them independently.\n\nAnd I guess that's what you're showing here:\n\n> In our testing repository, there are 1,261 commits selected for bitmap\n> coverage, and 1,382 maximal commits induced as a result of that. Of the\n> 1,382 calls made to `fill_bitmap_commit()` (one per maximal commit), 131\n> of them can be short-circuited at some point during their traversal as a\n> consequence of this change.\n\nWe'll end up seeing some of the same parts of history for various\nmaximal commits, and this lets us sometimes reuse the earlier efforts.\n\nAnyway, it is hard to argue with the numbers.\n\n> @@ -553,6 +559,28 @@ static int fill_bitmap_commit(struct bitmap_writer *writer,\n> \t\t\tbitmap_free(remapped);\n> \t\t}\n> \n> +\t\t/*\n> +\t\t * If we encounter an ancestor for which we have already\n> +\t\t * computed a bitmap during this build (i.e. a regular\n> +\t\t * selected commit processed earlier in topo order), we can\n> +\t\t * short-circuit the walk: its stored bitmap already covers\n> +\t\t * the commit itself, its tree, and all of its ancestors.\n> +\t\t */\n> +\t\tif (c != commit) {\n> +\t\t\tkhiter_t hash_pos = kh_get_oid_map(writer->bitmaps,\n> +\t\t\t\t\t\t\t c->object.oid);\n> +\t\t\tif (hash_pos != kh_end(writer->bitmaps)) {\n> +\t\t\t\tstruct bitmapped_commit *stored =\n> +\t\t\t\t\tkh_value(writer->bitmaps, hash_pos);\n> +\t\t\t\tif (stored && stored->bitmap) {\n> +\t\t\t\t\tfill_bitmap_commit_found_ancestor_nr++;\n> +\t\t\t\t\tbitmap_or_ewah(ent->bitmap,\n> +\t\t\t\t\t\t stored->bitmap);\n> +\t\t\t\t\tcontinue;\n> +\t\t\t\t}\n> +\t\t\t}\n> +\t\t}\n\nOK, so we incur one hash lookup per commit as we walk, which seems like\na good tradeoff.\n\nI wondered about \"c != commit\" here. \"c\" is the commit we're traversing,\nand \"commit\" is the one for which we're trying to build the bitmap. So\nwe would not expect to ever have an entry in writer->bitmaps for \"c\"\nyet, but the conditional is just short-circuiting the hash lookup.\n\nThe rest of the patch looks obviously correct. The trace2 bits aren't\nstrictly necessary, of course, but some metrics might help with further\ntuning.\n\n-Peff\n"},{"id":"544145","messageId":"20260527092707.GE981444@coredump.intra.peff.net","threadId":"65661","inReplyTo":"c9a560660949c53575a9b1e81160d25212a1f484.1779207127.git.me@ttaylorr.com","subject":"Re: [PATCH 4/8] pack-bitmap: consolidate `find_object_pos()` success path","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2026-05-27T09:27:07Z","receivedAt":"2026-05-27T09:27:10Z","isPatch":true,"body":"On Tue, May 19, 2026 at 12:12:44PM -0400, Taylor Blau wrote:\n\n> Both sides of `find_object_pos()` report success in the same way by\n> setting the optional `found` out-parameter and return the resolved\n> bitmap position.\n> \n> Prepare for adding more bookkeeping around object-position lookups by\n> storing the result in a local `pos` variable and sharing the success\n> return path between the packlist and MIDX cases.\n\nOK. Modulo the missing \"pos\" fixup, this seems like an obviously correct\nrefactor. On its own its hard to judge if it makes things better, so\nlet's read on.\n\n-Peff\n"},{"id":"544146","messageId":"20260527094535.GF981444@coredump.intra.peff.net","threadId":"65661","inReplyTo":"e43ef6a42d13578a6b7a4a346f491e51a6edfd14.1779207127.git.me@ttaylorr.com","subject":"Re: [PATCH 5/8] pack-bitmap: cache object positions during fill","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2026-05-27T09:45:35Z","receivedAt":"2026-05-27T09:45:37Z","isPatch":true,"body":"On Tue, May 19, 2026 at 12:12:47PM -0400, Taylor Blau wrote:\n\n> The previous commits removed some redundant work from bitmap generation\n> by avoiding unnecessary tree recursion and by reusing selected bitmaps\n> that have already been computed.\n> \n> Even with those changes in place, there is still an extremely hot path\n> from `fill_bitmap_commit()` and `fill_bitmap_tree()` to translate object\n> IDs into their corresponding bit positions in order to generate their\n> bitmaps.\n> \n> In a small repository, this overhead is not significant. However, in a\n> very large repository (e.g., the one that we have been using as a\n> benchmark over the past several commits with ~57M total objects), the\n> overhead of locating object bit positions (often repeatedly) adds up\n> significantly.\n> \n> Combat this by adding a small, direct-mapped cache to the bitmap writer\n> which maps object IDs to their corresponding bit positions. Size the\n> cache according to the number of objects being written, with fixed lower\n> and upper bounds so small repositories do not pay for a large table and\n> large repositories can avoid most repeated packlist and MIDX lookups.\n\nIntroducing another layer of data structure feels so dirty, but it's\nhard to argue with the numbers. We are looking up oids in the packlist,\nso it's already O(lg n). Your cache here is essentially a hash lookup,\nwhich is O(1)-ish (with collisions causing eviction rather than growth).\nAnd it presumably works because there's a lot of locality in lookups\n(between commits X and X^1, their top-level trees will be almost\nidentical but we have to resolve the bits to find out which entries are\nnew).\n\nIt does make me wonder if we'd see similar improvements if we just\nturned the packlist into a regular hash table. Or maybe not, because\nthen we'd have to do actual probing.\n\nIt also makes me wonder if we could use this trick elsewhere, but I\nguess we usually are using \"struct object\" itself to find repeats in\nmost graph traversals. And there we're using a hash table already. So\nthis might save us a tiny bit of probing, but not much else.\n\nLikewise when comparing two trees directly, we can just walk them in\nparallel to find the changed parts (which doesn't work here, because\nwe're comparing one tree to the bitmap of all ancestors, not just X^1).\n\nSo this really is a somewhat unique situation. It _might_ be applicable\nfor the reading side of bitmaps, though. When we do fill-in traversal we\nend up with this same \"read a tree, find the bit for each entry, and 99%\nof the time find that it is already in the bitmap\".\n\n> On my machine with (a somewhat outdated) GCC 15.2.0, each entry in the\n> cache is 40 bytes wide:\n> \n> $ pahole -C bitmap_pos_cache_entry pack-bitmap-write.o\n> struct bitmap_pos_cache_entry {\n> struct object_id oid; /* 0 36 */\n> uint32_t pos; /* 36 4 */\n> \n> /* size: 40, cachelines: 1, members: 2 */\n> /* last cacheline: 40 bytes */\n> };\n\nI wondered about storing a pointer to an oid here, which would be\nsmaller but require an extra level of pointer chasing. The ones from\nobject structs are stable, but I guess the ones from trees are not (they\npoint to an entry field which will be reused). So we have to store the\noid whole.\n\n> In our example repository from above and in earlier commits, this\n> results in a ~9.4% reduction in runtime relative to the previous commit:\n> \n> +------------------+-------------+-------------+---------------------+\n> | | HEAD^ | HEAD | Delta |\n> +------------------+-------------+-------------+---------------------+\n> | elapsed | 324.8 s | 294.1 s | -30.7 s (-9.4%) |\n> | cycles | 1,508.6 B | 1,365.5 B | -143.0 B (-9.5%) |\n> | instructions | 1,436.6 B | 1,389.8 B | -46.9 B (-3.3%) |\n> | CPI | 1.050 | 0.983 | -0.068 (-6.4%) |\n> +------------------+-------------+-------------+---------------------+\n\nI show a 26% speed up on linux.git (1m37 down to 1m12). Very cool.\n\n> +static uint32_t store_cached_object_pos(struct bitmap_writer *writer,\n> +\t\t\t\t\tconst struct object_id *oid,\n> +\t\t\t\t\tuint32_t pos)\n> +{\n> +\tsize_t slot;\n> +\n> +\tif (pos & BITMAP_POS_CACHE_VALID)\n> +\t\treturn pos; /* too large to cache */\n\nCute, I wondered what would happen if we went past 2^31. I suspect there\nare other parts of the code that do not behave that well around that\nsize, but it is good that we are not introducing any new surprises.\n\nThe whole patch looked pretty cleanly done.\n\n-Peff\n"},{"id":"544147","messageId":"20260527100406.GG981444@coredump.intra.peff.net","threadId":"65661","inReplyTo":"b0a4f31353a7053ab37b6d8c8f22c69bcfadfe50.1779207127.git.me@ttaylorr.com","subject":"Re: [PATCH 6/8] pack-bitmap: sort bitmaps before XORing","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2026-05-27T10:04:06Z","receivedAt":"2026-05-27T10:04:08Z","isPatch":true,"body":"On Tue, May 19, 2026 at 12:12:50PM -0400, Taylor Blau wrote:\n\n> Reachability bitmaps may be stored as XORs against nearby bitmaps, up to\n> 10 away. However, when callers provide selected commits in an arbitrary\n> order, the writer may miss good ancestor/descendant pairs and produce\n> much larger bitmap files without changing query coverage.\n> \n> Sort the selected bitmaps in date order (from oldest to newest) before\n> computing XOR offsets, leaving pseudo-merge bitmaps alone (which we will\n> deal with separately in following commits).\n\nThat order certainly makes the most sense. I'd have thought we ended up\nthere incidentally because of the order in which we consider the\ncommits, but perhaps not. I wonder if this got much worse when we\nre-wrote the bitmap generation code a few years ago.\n\nThat was in v2.31.0, I think. Repacking linux.git with bitmaps, though,\nI couldn't find any difference in size between v2.30 and v2.31. They're\nboth ~67M. But that also didn't shrink with this patch, either.\n\nIf you have some spare CPU cycles to burn, I would be interested in a\ncomparison of the bitmap size of your test repo using v2.30.0, v2.31.1,\nand this patch.\n\n> On our same testing repository from previous commits, this change shrunk\n> our selection of 1,261 bitmaps from ~635.46 MiB to 176.4 MiB for a\n> ~72.24% reduction in the on-disk size of our *.bitmap file. The time to\n> generate the smaller bitmap file decreased by ~3.69 seconds, though this\n> is likely mostly noise.\n\nCertainly good numbers. The obvious follow-up question is: how does the\nreading side fare? I'd expect it to be a little better, if only because\nthere are fewer bytes to consider when XOR-ing. But if there's some\nhidden assumption we're missing, then it could get wildly worse. It\nwould be good to confirm that that didn't happen. ;)\n\n> static void compute_xor_offsets(struct bitmap_writer *writer)\n> {\n> \tstatic const int MAX_XOR_OFFSET_SEARCH = 10;\n> \n> \tint i, next = 0;\n> +\tint nr = bitmap_writer_nr_selected_commits(writer);\n> +\n> +\tif (nr > 1) {\n> +\t\tQSORT(writer->selected, nr, bitmapped_commit_date_cmp);\n> +\n> +\t\tfor (i = 0; i < nr; i++) {\n> +\t\t\tstruct bitmapped_commit *stored = &writer->selected[i];\n> +\t\t\tkhiter_t hash_pos = kh_get_oid_map(writer->bitmaps,\n> +\t\t\t\t\t\t\t stored->commit->object.oid);\n> +\n> +\t\t\tif (hash_pos == kh_end(writer->bitmaps))\n> +\t\t\t\tBUG(\"selected commit missing from bitmap map: %s\",\n> +\t\t\t\t oid_to_hex(&stored->commit->object.oid));\n> +\n> +\t\t\tkh_value(writer->bitmaps, hash_pos) = stored;\n> +\t\t}\n> +\t}\n\nOK. It took me a minute to wrap my head around this. The real work is\ndone by QSORT(). But because we maintain a hash pointing into that\narray, we have to go through each hash entry and fix up its pointer.\n\nLooks correct.\n\n-Peff\n"},{"id":"544149","messageId":"20260527102534.GH981444@coredump.intra.peff.net","threadId":"65661","inReplyTo":"30ce254312cfee2a2a82f08246c3a2546ae32578.1779207127.git.me@ttaylorr.com","subject":"Re: [PATCH 8/8] pack-bitmap: build pseudo-merge bitmaps after regular bitmaps","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2026-05-27T10:25:34Z","receivedAt":"2026-05-27T10:25:36Z","isPatch":true,"body":"On Tue, May 19, 2026 at 12:12:55PM -0400, Taylor Blau wrote:\n\n> Each selected commit starts with one commit_mask bit in its \"commit\n> mask\" bitmap. Then, we walk the first-parent history in topological\n> order and OR each commit's mask into its (first) parent. Whenever that\n> OR results in the parent having more bits set, the child is deemed to be\n> non-maximal, and the frontier is pushed further back along the first\n> parent history.\n> \n> That approach works extremely well for ordinary selected commits, whose\n> first-parent histories often describe real sharing between the bitmaps\n> we are going to write.\n> \n> It struggles, however, to efficiently generate pseudo-merge bitmaps.\n> Unlike ordinary commits for which the above algorithm is designed,\n> pseudo-merges don't represent any \"real\" commit in history, just a\n> grouping of non-bitmapped reference tips. In that sense, their first\n> parent is just a part of a larger set, and treating them like ordinary\n> selected commits imposes a significant slow-down when generating bitmaps\n> with pseudo-merges enabled.\n\nThis is a great explanation of the problem, and especially this:\n\n> In other words, we pay a nearly ~5 minute penalty to generate\n> pseudo-merge bitmaps, but only save ~50 seconds during traversal.\n\nmakes it clear that we're doing something sub-optimal. And it points us\nin the right direction, since that traversal should be able to generate\nthe pseudo-merge bitmap we need in the first place! So that should be\nour goal to work towards.\n\n> Instead, build the regular selected commit bitmaps first, considering\n> only non-pseudo-merge commits in `bitmap_builder_init()`. Once those\n> bitmaps have been stored, build each pseudo-merge bitmap separately and\n> attach its parent and object bitmaps to the corresponding pseudo-merge\n> entry before writing the extension.\n\nAnd then this solution follows naturally from the earlier explanations.\nGood.\n\nIn some ways this goes back to the pre-v2.31 way of generating bitmaps,\nwhich is to just traverse for each bitmap independently. But as you\nnote, the whole idea of pseudo-merge bitmaps is that they aren't\noverlapping in any meaningful way. So doing one fill-in traversal per\npseudo-merge makes sense, and hopefully we hit enough real bitmaps that\nit's not too costly.\n\n> As a result, the overhead cost for generating pseudo-merges in the above\n> configuration is much smaller:\n> \n> +------------------+-----------------+---------------+-------------------+\n> | | no pseudo-merge | pseudo-merges | Delta |\n> | | | (HEAD) | |\n> +------------------+-----------------+---------------+-------------------+\n> | elapsed | 294.1 s | 328.4 s | +34.3 s (+11.7%) |\n> | cycles | 1,365.5 B | 1,529.3 B | +163.7 B (+12.0%) |\n> | instructions | 1,389.8 B | 1,552.8 B | +163.0 B (+11.7%) |\n> | CPI | 0.983 | 0.985 | +0.002 (+0.2%) |\n> +------------------+-----------------+---------------+-------------------+\n\nNice. The time savings are going to depend on how many pseudo-merges we\ngenerate, I think. And I'd guess that the numbers above come from making\none big pseudo-merge bitmap, per the config you showed earlier. But you\nprobably only want a handful of them in any repo, so hopefully it\ndoesn't scale _too_ badly.\n\n> Recall that at the start of this series, generating reachability bitmaps\n> took 612.5 seconds *without* pseudo-merges. With this commit, it is\n> still ~46.38% *faster* to generate reachability bitmaps *with*\n> pseudo-merges than it was to generate bitmaps wihtout them at the\n> beginning of this series.\n\nSure, though 612.5 seconds is all in the distant past. We only care\nabout 294.1 seconds now. ;)\n\nMore seriously, I do think the interesting question here is how the time\nscales for various pseudo-merge configurations. I don't know if we have\nany real operational experience with them yet. The original idea is that\nyou might slice up the ref space into a few chunks. I'd guess that the\nold code performed badly-ish overall, but the time did not grow all that\nmuch as you increased the number of chunks. But with the new code, I\nsuspect that the cost grows more linearly with number of chunks. That's\njust a guess, though.\n\nThe other thing we hope for with pseudo-merges is that the chunks are\nselected such that most of the chunks don't change (because they are\ncomposed of old, stable refs). So in subsequent bitmap generations, we\ncan either reuse them either verbatim or as a starting point (if there\nwere only additions). But all of that is going to be heuristic and\ndepend on your config, the changes the repo sees over time, and so on.\n\nSo I don't know if we'd really have good numbers on that.\n\n> Now that we have decoupled how we generate pseudo-merges from their\n> representation, the following commits will improve the API around\n> specifying pseudo-merge groupings during bitmap generation.\n\nI think we're at patch 8/8 here. I guess you have more to come\neventually, but for now this part is just misleading. ;)\n\n> pack-bitmap-write.c | 210 ++++++++++++++++++++++++++++++++++++--------\n> 1 file changed, 174 insertions(+), 36 deletions(-)\n\nThe patch looks reasonable, though I'm not all that familiar with the\nins and outs of the pseudo-merge code. I'd trust the tests here more\nthan my review.\n\n> @@ -696,12 +700,32 @@ static int fill_bitmap_commit(struct bitmap_writer *writer,\n> \t\t * walk ensures we cover all parents.\n> \t\t */\n> \t\tif (!(c->object.flags & BITMAP_PSEUDO_MERGE)) {\n> +\t\t\tstruct tree *tree;\n> +\n> +\t\t\tif (from_pseudo_merge && !c->object.parsed) {\n> +\t\t\t\t/*\n> +\t\t\t\t * Commits reachable from selected\n> +\t\t\t\t * non-pseudo-merges are already parsed\n> +\t\t\t\t * by the regular bitmap build.\n> +\t\t\t\t *\n> +\t\t\t\t * However, pseudo-merge fills can also\n> +\t\t\t\t * reach commits that were not covered\n> +\t\t\t\t * there, so parse any such leftovers\n> +\t\t\t\t * before reading their tree or parents.\n> +\t\t\t\t */\n> +\t\t\t\tif (repo_parse_commit(writer->repo, c))\n> +\t\t\t\t\treturn -1;\n> +\t\t\t}\n\nMakes sense. This should be a quick noop for the regular bitmap build,\nsince we'll have the parsed flag set. And it should even allow use of\nthe commit-graph if it's available.\n\n-Peff\n"},{"id":"544150","messageId":"20260527102716.GI981444@coredump.intra.peff.net","threadId":"65661","inReplyTo":"cover.1779207127.git.me@ttaylorr.com","subject":"Re: [PATCH 0/8] pack-bitmap-write: speed up bitmap generation","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2026-05-27T10:27:16Z","receivedAt":"2026-05-27T10:27:18Z","isPatch":true,"body":"On Tue, May 19, 2026 at 12:12:33PM -0400, Taylor Blau wrote:\n\n> This series improves the performance of reachability bitmap generation,\n> focusing on very large repositories and the penalty to generate\n> pseudo-merge reachability bitmaps.\n\nVery nice numbers. I'm especially excited about patches 1-6, which are\nreally just speeding up bitmap generation in general, pseudo-merges\naside. I think you could even have split those off into their own\nseries, and then built the final two as a separate topic, but I am happy\neither way.\n\nI looked through the patches and had nothing to complain about.\n\n-Peff\n"},{"id":"544165","messageId":"ahcBVlwysYlKsjUs@nand.local","threadId":"65661","inReplyTo":"20260527085740.GB981444@coredump.intra.peff.net","subject":"Re: [PATCH 1/8] pack-bitmap: pass object position to `fill_bitmap_tree()`","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2026-05-27T14:36:06Z","receivedAt":"2026-05-27T14:36:11Z","isPatch":true,"body":"On Wed, May 27, 2026 at 04:57:40AM -0400, Jeff King wrote:\n> It is indeed surprising. There's a possible candidate for the speedup\n> here:\n>\n> > @@ -482,8 +479,12 @@ static int fill_bitmap_tree(struct bitmap_writer *writer,\n> > \twhile (tree_entry(&desc, &entry)) {\n> > \t\tswitch (object_type(entry.mode)) {\n> > \t\tcase OBJ_TREE:\n> > +\t\t\tpos = find_object_pos(writer, &entry.oid, &found);\n> > +\t\t\tif (!found)\n> > +\t\t\t\treturn -1;\n> > \t\t\tif (fill_bitmap_tree(writer, bitmap,\n> > -\t\t\t\t\t lookup_tree(writer->repo, &entry.oid)) < 0)\n> > +\t\t\t\t\t lookup_tree(writer->repo,\n> > +\t\t\t\t\t\t\t &entry.oid), pos) < 0)\n> > \t\t\t\treturn -1;\n> > \t\t\tbreak;\n>\n> Whenever \"found\" is false, we cut out early and skip the hash lookup in\n> lookup_tree() entirely. But that should almost never happen! It implies\n> that a reachable object is not in the pack/midx, and thus the bitmaps is\n> not closed (and we'll refuse to generate it).\n\nThat's right, and I had actually written something like the following\nwhile developing this patch:\n\n--- 8< ---\ndiff --git a/pack-bitmap-write.c b/pack-bitmap-write.c\nindex 2d5ff8fd406..328e1c13df3 100644\n--- a/pack-bitmap-write.c\n+++ b/pack-bitmap-write.c\n@@ -481,7 +481,7 @@ static int fill_bitmap_tree(struct bitmap_writer *writer,\n \t\tcase OBJ_TREE:\n \t\t\tpos = find_object_pos(writer, &entry.oid, &found);\n \t\t\tif (!found)\n-\t\t\t\treturn -1;\n+\t\t\t\tBUG(\"huh??\");\n \t\t\tif (fill_bitmap_tree(writer, bitmap,\n \t\t\t\t\t lookup_tree(writer->repo,\n \t\t\t\t\t\t\t &entry.oid), pos) < 0)\n--- >8 ---\n\n, but couldn't trigger it in either the test suite nor in my sample\nrepository. I left it in there as a sanity measure.\n\n> So it really is the case that we do the same operations in a different\n> order. Weird.\n\nYeah, I puzzled over this for quite a while myself. I really think that\nthis is reordering produces more favorable cache behavior or codegen\nthat results in a meaningful speedup.\n\n> But the patch itself looks correct to me, and I get ~6% speedup on a\n> from-scratch bitmap generation of linux.git. I guess it could vary\n> between architectures and compilers (I'm using gcc on x86), but since\n> the reorg is setting us up for further optimizations in the next patch,\n> I suppose there's no need to look a gift horse in the mouth.\n\nGood, I'm glad that it was reproducible on your machine. And I agree\n;-).\n\nThanks,\nTaylor\n"},{"id":"544166","messageId":"ahcBf8jQ2iqP+Lme@nand.local","threadId":"65661","inReplyTo":"20260527090348.GC981444@coredump.intra.peff.net","subject":"Re: [PATCH 2/8] pack-bitmap: check subtree bits before recursing","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2026-05-27T14:36:47Z","receivedAt":"2026-05-27T14:36:49Z","isPatch":true,"body":"On Wed, May 27, 2026 at 05:03:48AM -0400, Jeff King wrote:\n> On Tue, May 19, 2026 at 12:12:39PM -0400, Taylor Blau wrote:\n>\n> > In the previous commit, we adjusted the callers of `fill_bitmap_tree()`\n> > to pass in the bit position of the tree they wish to fill.\n> >\n> > This commit makes use of that information at the call site to avoid\n> > setting up a stack frame for fill_bitmap_tree() entirely whenever a\n> > tree's bit position is already set.\n>\n> OK, this one at least has a plausible explanation. ;)\n>\n> I can reproduce your speedup on linux.git (~5% again). I don't love that\n> we have to duplicate the logic in each of the callers, but there are\n> only two sites (and unlikely to ever be more). And it is only one line,\n> the comment notwithstanding. That seems like a good tradeoff for a\n> multiple-second speedup.\n\nYup, exactly. There are naturally only two callers: one to handle a\ncommit's root tree, and another for recursive calls to handle subtrees.\nAs a result, I'm OK with the duplication here.\n\nThanks,\nTaylor\n"},{"id":"544167","messageId":"ahcCX+xAKFOL8HcW@nand.local","threadId":"65661","inReplyTo":"20260527092412.GD981444@coredump.intra.peff.net","subject":"Re: [PATCH 3/8] pack-bitmap: reuse stored selected bitmaps","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2026-05-27T14:40:31Z","receivedAt":"2026-05-27T14:40:34Z","isPatch":true,"body":"On Wed, May 27, 2026 at 05:24:12AM -0400, Jeff King wrote:\n> On Tue, May 19, 2026 at 12:12:41PM -0400, Taylor Blau wrote:\n>\n> > Building bitmaps from scratch on the same test repository from the\n> > previous commits yields a significant speed-up:\n> >\n> > +------------------+-------------+-------------+---------------------+\n> > | | HEAD^ | HEAD | Delta |\n> > +------------------+-------------+-------------+---------------------+\n> > | elapsed | 562.8 s | 324.8 s | -237.9 s (-42.3%) |\n> > | cycles | 2,621.3 B | 1,508.6 B | -1,112.7 B (-42.4%) |\n> > | instructions | 2,348.9 B | 1,436.6 B | -912.3 B (-38.8%) |\n> > | CPI | 1.116 | 1.050 | -0.066 (-5.9%) |\n> > +------------------+-------------+-------------+---------------------+\n>\n> Oh my, that's a rather nice speedup. I can reproduce here on linux.git\n> (~47% improvement).\n>\n> > When `fill_bitmap_commit()` reaches an ancestor that was selected for\n> > its own bitmap and processed earlier, its object closure is already\n> > stored in `writer->bitmaps` as an EWAH bitmap. As a result, walking\n> > through that commit's tree and parents again is redundant.\n> >\n> > Teach `fill_bitmap_commit()` to notice that case. For non-root commits in\n> > the walk, look for a stored selected bitmap and OR it into the bitmap\n> > being built. If one exists, skip the commit, its tree, and its parents.\n>\n> I feel like this _shouldn't_ be necessary, because the idea of the\n> current writing code is to go from the roots up, following inverted\n> parent pointers, and passing the bitmap up as we go. So whenever we\n> visit a commit we should in theory have all of the ancestor's bits set\n> in that bitmap. But I remember that the simple-and-stupid approach ended\n> up being too memory hungry, so we pick some focal points in the graph\n> and then fill them independently.\n\nIt's sharing within the non-first parent history that is killing us\nhere. I think what you said is true in a completely linear repository\nwith no merges. But since we only pass commit masks from commits to\ntheir first parents, we don't reuse any already-generated bitmaps for\ncommon points in history not shared between commits' first parents.\n\n> I wondered about \"c != commit\" here. \"c\" is the commit we're traversing,\n> and \"commit\" is the one for which we're trying to build the bitmap. So\n> we would not expect to ever have an entry in writer->bitmaps for \"c\"\n> yet, but the conditional is just short-circuiting the hash lookup.\n\nExactly.\n\n> The rest of the patch looks obviously correct. The trace2 bits aren't\n> strictly necessary, of course, but some metrics might help with further\n> tuning.\n\nYeah, these were for my own curiosity as much as anything. I had written\nthem as a temporary measure in order to write the \"[...] there are 1,261\ncommits selected for bitmap coverage, and 1,382 maximal commits induced\n[...]\" portion of the commit message above.\n\nOnce I had written it, I found the result useful enough to keep around.\n\nThanks,\nTaylor\n"},{"id":"544168","messageId":"ahcDsgYTJurWO7X3@nand.local","threadId":"65661","inReplyTo":"20260527094535.GF981444@coredump.intra.peff.net","subject":"Re: [PATCH 5/8] pack-bitmap: cache object positions during fill","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2026-05-27T14:46:10Z","receivedAt":"2026-05-27T14:46:12Z","isPatch":true,"body":"On Wed, May 27, 2026 at 05:45:35AM -0400, Jeff King wrote:\n> > Combat this by adding a small, direct-mapped cache to the bitmap writer\n> > which maps object IDs to their corresponding bit positions. Size the\n> > cache according to the number of objects being written, with fixed lower\n> > and upper bounds so small repositories do not pay for a large table and\n> > large repositories can avoid most repeated packlist and MIDX lookups.\n>\n> Introducing another layer of data structure feels so dirty, but it's\n> hard to argue with the numbers. We are looking up oids in the packlist,\n> so it's already O(lg n). Your cache here is essentially a hash lookup,\n> which is O(1)-ish (with collisions causing eviction rather than growth).\n> And it presumably works because there's a lot of locality in lookups\n> (between commits X and X^1, their top-level trees will be almost\n> identical but we have to resolve the bits to find out which entries are\n> new).\n>\n> It does make me wonder if we'd see similar improvements if we just\n> turned the packlist into a regular hash table. Or maybe not, because\n> then we'd have to do actual probing.\n\nI haven't run that experiment directly, but I share your suspicion. I\nwrote a 2- and 4-way associative cache implementation as alternatives\nbefore settling on the direct-mapped approach in this patch. I found\nthat associative caches regardless of cache lines nearly nuked any of\nthe performance gains that we got as a result of this patch.\n\n> So this really is a somewhat unique situation. It _might_ be applicable\n> for the reading side of bitmaps, though. When we do fill-in traversal we\n> end up with this same \"read a tree, find the bit for each entry, and 99%\n> of the time find that it is already in the bitmap\".\n\nI think it's certainly likely. In my experience, many object to\nbit-position queries are extremely cache-friendly. And in practice, many\nlarge repositories have MIDXs with many tens of millions of objects. So\neven on a O(log n) lookup, caching seems to help a lot.\n\n> > In our example repository from above and in earlier commits, this\n> > results in a ~9.4% reduction in runtime relative to the previous commit:\n> >\n> > +------------------+-------------+-------------+---------------------+\n> > | | HEAD^ | HEAD | Delta |\n> > +------------------+-------------+-------------+---------------------+\n> > | elapsed | 324.8 s | 294.1 s | -30.7 s (-9.4%) |\n> > | cycles | 1,508.6 B | 1,365.5 B | -143.0 B (-9.5%) |\n> > | instructions | 1,436.6 B | 1,389.8 B | -46.9 B (-3.3%) |\n> > | CPI | 1.050 | 0.983 | -0.068 (-6.4%) |\n> > +------------------+-------------+-------------+---------------------+\n>\n> I show a 26% speed up on linux.git (1m37 down to 1m12). Very cool.\n\nGlad it reproduces ;-).\n\n> > +static uint32_t store_cached_object_pos(struct bitmap_writer *writer,\n> > +\t\t\t\t\tconst struct object_id *oid,\n> > +\t\t\t\t\tuint32_t pos)\n> > +{\n> > +\tsize_t slot;\n> > +\n> > +\tif (pos & BITMAP_POS_CACHE_VALID)\n> > +\t\treturn pos; /* too large to cache */\n>\n> Cute, I wondered what would happen if we went past 2^31. I suspect there\n> are other parts of the code that do not behave that well around that\n> size, but it is good that we are not introducing any new surprises.\n\nYeah, I suspect that there are many breakages past the 32-bit unsigned\nmaximum number of objects. I figure the easiest thing to do in this\npatch is to avoid making that situation worse by simply not caching\nobjects that are near that limit.\n\nThanks,\nTaylor\n"},{"id":"544177","messageId":"ahciIDuESxNa9Fzn@nand.local","threadId":"65661","inReplyTo":"20260527100406.GG981444@coredump.intra.peff.net","subject":"Re: [PATCH 6/8] pack-bitmap: sort bitmaps before XORing","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2026-05-27T16:56:00Z","receivedAt":"2026-05-27T16:56:02Z","isPatch":true,"body":"On Wed, May 27, 2026 at 06:04:06AM -0400, Jeff King wrote:\n> On Tue, May 19, 2026 at 12:12:50PM -0400, Taylor Blau wrote:\n>\n> > Reachability bitmaps may be stored as XORs against nearby bitmaps, up to\n> > 10 away. However, when callers provide selected commits in an arbitrary\n> > order, the writer may miss good ancestor/descendant pairs and produce\n> > much larger bitmap files without changing query coverage.\n> >\n> > Sort the selected bitmaps in date order (from oldest to newest) before\n> > computing XOR offsets, leaving pseudo-merge bitmaps alone (which we will\n> > deal with separately in following commits).\n>\n> That order certainly makes the most sense. I'd have thought we ended up\n> there incidentally because of the order in which we consider the\n> commits, but perhaps not. I wonder if this got much worse when we\n> re-wrote the bitmap generation code a few years ago.\n>\n> That was in v2.31.0, I think. Repacking linux.git with bitmaps, though,\n> I couldn't find any difference in size between v2.30 and v2.31. They're\n> both ~67M. But that also didn't shrink with this patch, either.\n>\n> If you have some spare CPU cycles to burn, I would be interested in a\n> comparison of the bitmap size of your test repo using v2.30.0, v2.31.1,\n> and this patch.\n\nI started running this experiment, but I don't think I actually have\nenough CPU cycles to let it finish ;-). Pre-v2.31 bitmap generation is\n*really* slow[^1], and after multiple hours (forcing the same selection\nof bitmaps by back-porting and adjusting 'test-tool bitmap') I couldn't\nseem to make any meaningful progress.\n\nI'm sure that you could get some plausible numbers out of benchmarking\nthis on a smaller repository. In case you're interested, here's the\npatch I wrote on top of v2.30.0:\n\n--- 8< ---\ndiff --git a/Makefile b/Makefile\nindex 7b64106930a..9ce9f2b483c 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -690,6 +690,7 @@ X =\n PROGRAMS += $(patsubst %.o,git-%$X,$(PROGRAM_OBJS))\n\n TEST_BUILTINS_OBJS += test-advise.o\n+TEST_BUILTINS_OBJS += test-bitmap.o\n TEST_BUILTINS_OBJS += test-bloom.o\n TEST_BUILTINS_OBJS += test-chmtime.o\n TEST_BUILTINS_OBJS += test-config.o\ndiff --git a/pack-bitmap-write.c b/pack-bitmap-write.c\nindex 5e998bdaa79..55dbb475120 100644\n--- a/pack-bitmap-write.c\n+++ b/pack-bitmap-write.c\n@@ -113,7 +113,7 @@ void bitmap_writer_build_type_index(struct packing_data *to_pack,\n static struct object **seen_objects;\n static unsigned int seen_objects_nr, seen_objects_alloc;\n\n-static inline void push_bitmapped_commit(struct commit *commit, struct ewah_bitmap *reused)\n+void bitmap_writer_push_commit(struct commit *commit, struct ewah_bitmap *reused)\n {\n \tif (writer.selected_nr >= writer.selected_alloc) {\n \t\twriter.selected_alloc = (writer.selected_alloc + 32) * 2;\n@@ -402,7 +402,7 @@ void bitmap_writer_select_commits(struct commit **indexed_commits,\n\n \tif (indexed_commits_nr < 100) {\n \t\tfor (i = 0; i < indexed_commits_nr; ++i)\n-\t\t\tpush_bitmapped_commit(indexed_commits[i], NULL);\n+\t\t\tbitmap_writer_push_commit(indexed_commits[i], NULL);\n \t\treturn;\n \t}\n\n@@ -440,7 +440,7 @@ void bitmap_writer_select_commits(struct commit **indexed_commits,\n \t\t\t}\n \t\t}\n\n-\t\tpush_bitmapped_commit(chosen, reused_bitmap);\n+\t\tbitmap_writer_push_commit(chosen, reused_bitmap);\n\n \t\ti += next + 1;\n \t\tdisplay_progress(writer.progress, i);\ndiff --git a/pack-bitmap.h b/pack-bitmap.h\nindex 1203120c432..a882efdb16a 100644\n--- a/pack-bitmap.h\n+++ b/pack-bitmap.h\n@@ -74,6 +74,8 @@ void bitmap_writer_build_type_index(struct packing_data *to_pack,\n \t\t\t\t struct pack_idx_entry **index,\n \t\t\t\t uint32_t index_nr);\n void bitmap_writer_reuse_bitmaps(struct packing_data *to_pack);\n+void bitmap_writer_push_commit(struct commit *commit,\n+\t\t\t struct ewah_bitmap *reused);\n void bitmap_writer_select_commits(struct commit **indexed_commits,\n \t\tunsigned int indexed_commits_nr, int max_bitmaps);\n void bitmap_writer_build(struct packing_data *to_pack);\ndiff --git a/t/helper/test-bitmap.c b/t/helper/test-bitmap.c\nnew file mode 100644\nindex 00000000000..9be03377c06\n--- /dev/null\n+++ b/t/helper/test-bitmap.c\n@@ -0,0 +1,119 @@\n+#define USE_THE_REPOSITORY_VARIABLE\n+\n+#include \"test-tool.h\"\n+#include \"git-compat-util.h\"\n+#include \"commit.h\"\n+#include \"packfile.h\"\n+#include \"pack-bitmap.h\"\n+\n+static int add_packed_object(const struct object_id *oid,\n+\t\t\t struct packed_git *pack,\n+\t\t\t uint32_t pos,\n+\t\t\t void *_data)\n+{\n+\tstruct packing_data *packed = _data;\n+\tstruct object_entry *entry;\n+\tstruct object_info oi = OBJECT_INFO_INIT;\n+\tenum object_type type;\n+\n+\toi.typep = &type;\n+\n+\tentry = packlist_alloc(packed, oid);\n+\tentry->in_pack_offset = nth_packed_object_offset(pack, pos);\n+\tentry->idx.offset = entry->in_pack_offset;\n+\tif (packed_object_info(the_repository, pack, entry->in_pack_offset, &oi) < 0)\n+\t\tdie(\"could not get type of object %s\",\n+\t\t oid_to_hex(oid));\n+\toe_set_type(entry, type);\n+\toe_set_in_pack(packed, entry, pack);\n+\n+\treturn 0;\n+}\n+\n+static int idx_oid_cmp(const void *va, const void *vb)\n+{\n+\tconst struct pack_idx_entry *a = *(const struct pack_idx_entry **)va;\n+\tconst struct pack_idx_entry *b = *(const struct pack_idx_entry **)vb;\n+\n+\treturn oidcmp(&a->oid, &b->oid);\n+}\n+\n+static int bitmap_write(const char *basename)\n+{\n+\tstruct packed_git *p = NULL;\n+\tstruct packing_data packed = { 0 };\n+\tstruct pack_idx_entry **index;\n+\tstruct strbuf buf = STRBUF_INIT;\n+\tuint32_t i;\n+\n+\tprepare_repo_settings(the_repository);\n+\tfor (p = get_all_packs(the_repository); p; p = p->next) {\n+\t\tif (!strcmp(pack_basename(p), basename))\n+\t\t\tbreak;\n+\t}\n+\n+\tif (!p)\n+\t\tdie(\"could not find pack '%s'\", basename);\n+\n+\tif (open_pack_index(p))\n+\t\tdie(\"cannot open pack index for '%s'\", p->pack_name);\n+\n+\tprepare_packing_data(the_repository, &packed);\n+\n+\tfor_each_object_in_pack(p, add_packed_object, &packed,\n+\t\t\t\tFOR_EACH_OBJECT_PACK_ORDER);\n+\n+\t/*\n+\t * Build the index array now that data.packed.objects[] is\n+\t * fully allocated (packlist_alloc() may have reallocated it\n+\t * during the loop above).\n+\t */\n+\tALLOC_ARRAY(index, p->num_objects);\n+\tfor (i = 0; i < p->num_objects; i++)\n+\t\tindex[i] = &packed.objects[i].idx;\n+\n+\tbitmap_writer_build_type_index(&packed, index, p->num_objects);\n+\n+\twhile (strbuf_getline_lf(&buf, stdin) != EOF) {\n+\t\tstruct object_id oid;\n+\t\tstruct commit *c;\n+\n+\t\tif (get_oid_hex(buf.buf, &oid))\n+\t\t\tdie(\"invalid OID: %s\", buf.buf);\n+\n+\t\tc = lookup_commit(the_repository, &oid);\n+\t\tif (!c || repo_parse_commit(the_repository, c))\n+\t\t\tdie(\"could not parse commit %s\", buf.buf);\n+\n+\t\tbitmap_writer_push_commit(c, NULL);\n+\t}\n+\n+\tbitmap_writer_build(&packed);\n+\n+\tbitmap_writer_set_checksum(p->hash);\n+\n+\tQSORT(index, p->num_objects, idx_oid_cmp);\n+\n+\tstrbuf_reset(&buf);\n+\tstrbuf_addstr(&buf, p->pack_name);\n+\tstrbuf_strip_suffix(&buf, \".pack\");\n+\tstrbuf_addstr(&buf, \".bitmap\");\n+\tbitmap_writer_finish(index, p->num_objects, buf.buf, 0);\n+\n+\tstrbuf_release(&buf);\n+\tfree(index);\n+\n+\treturn 0;\n+}\n+\n+int cmd__bitmap(int argc, const char **argv)\n+{\n+\tsetup_git_directory();\n+\n+\tif (argc == 3 && !strcmp(argv[1], \"write\"))\n+\t\treturn bitmap_write(argv[2]);\n+\n+\tusage(\"\\ttest-tool bitmap write < \");\n+\n+\treturn -1;\n+}\ndiff --git a/t/helper/test-tool.c b/t/helper/test-tool.c\nindex 9d6d14d9293..c43d8c0977b 100644\n--- a/t/helper/test-tool.c\n+++ b/t/helper/test-tool.c\n@@ -15,6 +15,7 @@ struct test_cmd {\n\n static struct test_cmd cmds[] = {\n \t{ \"advise\", cmd__advise_if_enabled },\n+\t{ \"bitmap\", cmd__bitmap },\n \t{ \"bloom\", cmd__bloom },\n \t{ \"chmtime\", cmd__chmtime },\n \t{ \"config\", cmd__config },\ndiff --git a/t/helper/test-tool.h b/t/helper/test-tool.h\nindex a6470ff62c4..27e6e40ffcb 100644\n--- a/t/helper/test-tool.h\n+++ b/t/helper/test-tool.h\n@@ -5,6 +5,7 @@\n #include \"git-compat-util.h\"\n\n int cmd__advise_if_enabled(int argc, const char **argv);\n+int cmd__bitmap(int argc, const char **argv);\n int cmd__bloom(int argc, const char **argv);\n int cmd__chmtime(int argc, const char **argv);\n int cmd__config(int argc, const char **argv);\n--- >8 ---\n\n> > On our same testing repository from previous commits, this change shrunk\n> > our selection of 1,261 bitmaps from ~635.46 MiB to 176.4 MiB for a\n> > ~72.24% reduction in the on-disk size of our *.bitmap file. The time to\n> > generate the smaller bitmap file decreased by ~3.69 seconds, though this\n> > is likely mostly noise.\n>\n> Certainly good numbers. The obvious follow-up question is: how does the\n> reading side fare? I'd expect it to be a little better, if only because\n> there are fewer bytes to consider when XOR-ing. But if there's some\n> hidden assumption we're missing, then it could get wildly worse. It\n> would be good to confirm that that didn't happen. ;)\n\nIt doesn't make a huge difference. Prior to this patch, the timings on\nmy test repository for 'git rev-list --count --all --objects\n--use-bitmap-index' go from:\n\n - 2.180 ± 0.019 seconds (with pseudo-merges)\n - 52.149 ± 0.224 seconds (without pseudo-merges)\n\n, and after applying this patch, it changes to:\n\n - 2.611 ± 0.023 seconds (with pseudo-merges)\n - 51.963 ± 0.131 seconds (without pseudo-merges)\n\nIt looks like there is a minor slow-down on pseudo-merges, and a minor\nspeed-up without them. The difference is small enough that I'm willing\nto treat it as run-to-run noise.\n\n> > static void compute_xor_offsets(struct bitmap_writer *writer)\n> > {\n> > \tstatic const int MAX_XOR_OFFSET_SEARCH = 10;\n> >\n> > \tint i, next = 0;\n> > +\tint nr = bitmap_writer_nr_selected_commits(writer);\n> > +\n> > +\tif (nr > 1) {\n> > +\t\tQSORT(writer->selected, nr, bitmapped_commit_date_cmp);\n> > +\n> > +\t\tfor (i = 0; i < nr; i++) {\n> > +\t\t\tstruct bitmapped_commit *stored = &writer->selected[i];\n> > +\t\t\tkhiter_t hash_pos = kh_get_oid_map(writer->bitmaps,\n> > +\t\t\t\t\t\t\t stored->commit->object.oid);\n> > +\n> > +\t\t\tif (hash_pos == kh_end(writer->bitmaps))\n> > +\t\t\t\tBUG(\"selected commit missing from bitmap map: %s\",\n> > +\t\t\t\t oid_to_hex(&stored->commit->object.oid));\n> > +\n> > +\t\t\tkh_value(writer->bitmaps, hash_pos) = stored;\n> > +\t\t}\n> > +\t}\n>\n> OK. It took me a minute to wrap my head around this. The real work is\n> done by QSORT(). But because we maintain a hash pointing into that\n> array, we have to go through each hash entry and fix up its pointer.\n\nYup.\n\n> Looks correct.\n\nThanks,\nTaylor\n\n[^1]: ...and I have great empathy for Stolee's suffering here when\n benchmarking his performance improvements to the bitmap generation\n code from back in the day! ;-).\n"},{"id":"544183","messageId":"ahdE+Je5YK9JoE7B@nand.local","threadId":"65661","inReplyTo":"20260527102534.GH981444@coredump.intra.peff.net","subject":"Re: [PATCH 8/8] pack-bitmap: build pseudo-merge bitmaps after regular bitmaps","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2026-05-27T19:24:40Z","receivedAt":"2026-05-27T19:24:46Z","isPatch":true,"body":"On Wed, May 27, 2026 at 06:25:34AM -0400, Jeff King wrote:\n> > It struggles, however, to efficiently generate pseudo-merge bitmaps.\n> > Unlike ordinary commits for which the above algorithm is designed,\n> > pseudo-merges don't represent any \"real\" commit in history, just a\n> > grouping of non-bitmapped reference tips. In that sense, their first\n> > parent is just a part of a larger set, and treating them like ordinary\n> > selected commits imposes a significant slow-down when generating bitmaps\n> > with pseudo-merges enabled.\n>\n> This is a great explanation of the problem, and especially this:\n>\n> > In other words, we pay a nearly ~5 minute penalty to generate\n> > pseudo-merge bitmaps, but only save ~50 seconds during traversal.\n>\n> makes it clear that we're doing something sub-optimal. And it points us\n> in the right direction, since that traversal should be able to generate\n> the pseudo-merge bitmap we need in the first place! So that should be\n> our goal to work towards.\n>\n> > Instead, build the regular selected commit bitmaps first, considering\n> > only non-pseudo-merge commits in `bitmap_builder_init()`. Once those\n> > bitmaps have been stored, build each pseudo-merge bitmap separately and\n> > attach its parent and object bitmaps to the corresponding pseudo-merge\n> > entry before writing the extension.\n>\n> And then this solution follows naturally from the earlier explanations.\n> Good.\n\nThanks. For as clear as this sounds now, finding this approach took me\nlonger than I'd like to admit. I'm satisfied, however, with the result.\n\n> In some ways this goes back to the pre-v2.31 way of generating bitmaps,\n> which is to just traverse for each bitmap independently. But as you\n> note, the whole idea of pseudo-merge bitmaps is that they aren't\n> overlapping in any meaningful way. So doing one fill-in traversal per\n> pseudo-merge makes sense, and hopefully we hit enough real bitmaps that\n> it's not too costly.\n\nExactly!\n\n> > As a result, the overhead cost for generating pseudo-merges in the above\n> > configuration is much smaller:\n> >\n> > +------------------+-----------------+---------------+-------------------+\n> > | | no pseudo-merge | pseudo-merges | Delta |\n> > | | | (HEAD) | |\n> > +------------------+-----------------+---------------+-------------------+\n> > | elapsed | 294.1 s | 328.4 s | +34.3 s (+11.7%) |\n> > | cycles | 1,365.5 B | 1,529.3 B | +163.7 B (+12.0%) |\n> > | instructions | 1,389.8 B | 1,552.8 B | +163.0 B (+11.7%) |\n> > | CPI | 0.983 | 0.985 | +0.002 (+0.2%) |\n> > +------------------+-----------------+---------------+-------------------+\n>\n> Nice. The time savings are going to depend on how many pseudo-merges we\n> generate, I think. And I'd guess that the numbers above come from making\n> one big pseudo-merge bitmap, per the config you showed earlier. But you\n> probably only want a handful of them in any repo, so hopefully it\n> doesn't scale _too_ badly.\n\nThat's right, though see below for more thoughts on scaling...\n\n> > Recall that at the start of this series, generating reachability bitmaps\n> > took 612.5 seconds *without* pseudo-merges. With this commit, it is\n> > still ~46.38% *faster* to generate reachability bitmaps *with*\n> > pseudo-merges than it was to generate bitmaps wihtout them at the\n> > beginning of this series.\n>\n> Sure, though 612.5 seconds is all in the distant past. We only care\n> about 294.1 seconds now. ;)\n\nHeh ;-). Naturally, I agree here, but wanted to include it for context.\nI wanted to point out that the accumulated changes in this series make\nit cheaper to generate bitmaps with pseudo-merges now than it was to\ngenerate bitmaps without them before.\n\n> More seriously, I do think the interesting question here is how the time\n> scales for various pseudo-merge configurations. I don't know if we have\n> any real operational experience with them yet. The original idea is that\n> you might slice up the ref space into a few chunks. I'd guess that the\n> old code performed badly-ish overall, but the time did not grow all that\n> much as you increased the number of chunks. But with the new code, I\n> suspect that the cost grows more linearly with number of chunks. That's\n> just a guess, though.\n\nI'm not aware of any large-scale deployments of pseudo-merge bitmaps.\nThis series is written (in part) of the hopes of making one ;-). I think\nyour intuition on the old code matches my own.\n\nBelow are some numbers that give you a sense of how the runtime scales\nwith the number of pseudo-merges. I'm relying exclusively on \"stable\"\npseudo-merges here since they have more predictable bucketing behavior,\nthough note that there isn't an exact way to dial in the number of these\nso-called \"stable\" pseudo-merge groups. We can only control their *size*\n(in terms of number of parents), so I ran the harness which produced the\nabove code with powers of 10 between [10^3, 10^6].\n\nResults are as follows:\n\n +------------+-------+----------+\n | stableSize | count | time (s) |\n +------------+-------+----------+\n | 1000000 | 1 | 34.963 |\n | 100000 | 3 | 36.954 |\n | 10000 | 26 | 221.963 |\n | 1000 | 252 | 2779.373 |\n +------------+-------+----------+\n\nWhich scales roughly like O(x^1.165) (the best fit function I could find\nwas t(n) = 25.18 + 4.386 * n^1.165, where 'n' is the number of\npseudo-merges, and t(n) is the time it took to generate them).\n\nSo it does grow faster than linearly, but it's not too bad. The jump\nfrom 26 to 252 pseudo-merges is pretty significant, though, but having\nthat many pseudo-merges is probably not something that we would want to\ndo in practice.\n\n> The other thing we hope for with pseudo-merges is that the chunks are\n> selected such that most of the chunks don't change (because they are\n> composed of old, stable refs). So in subsequent bitmap generations, we\n> can either reuse them either verbatim or as a starting point (if there\n> were only additions). But all of that is going to be heuristic and\n> depend on your config, the changes the repo sees over time, and so on.\n>\n> So I don't know if we'd really have good numbers on that.\n\nWe don't, and it is somewhat of a pain to simulate. I think the proof\nwill be in the pudding, so to speak.\n\n> > Now that we have decoupled how we generate pseudo-merges from their\n> > representation, the following commits will improve the API around\n> > specifying pseudo-merge groupings during bitmap generation.\n>\n> I think we're at patch 8/8 here. I guess you have more to come\n> eventually, but for now this part is just misleading. ;)\n\nYeah, I cleaved this off of a larger series to make the pseudo-merge API\na little easier to reason about and less clunky to use. But I ended up\nhoarding some of those patches, and apparently forgot to adjust the\nmessage here. Thanks for spotting.\n\nThanks,\nTaylor\n"},{"id":"544184","messageId":"cover.1779911733.git.me@ttaylorr.com","threadId":"65661","inReplyTo":"cover.1779207127.git.me@ttaylorr.com","subject":"[PATCH v2 0/8] pack-bitmap-write: speed up bitmap generation","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2026-05-27T19:55:44Z","receivedAt":"2026-05-27T19:55:46Z","isPatch":true,"body":"Here is a reroll of my series to improve the performance of reachability\nbitmap generation, focusing on very large repositories and the penalty\nto generate pseudo-merge reachability bitmaps.\n\nThe series is largely unchanged since last time. Notable changes in this\nround include:\n\n - minor refactoring in the pair of patches which consolidate the\n `find_object_pos()` success path and introduce the object position\n cache during bitmap fills, and\n\n - dropping a stale paragraph from the final patch's message, which\n described follow-up commits that are no longer part of this series.\n\nAs usual, a range-diff against v1 is included below for convenience.\n\nThanks in advance for your review!\n\nTaylor Blau (8):\n pack-bitmap: pass object position to `fill_bitmap_tree()`\n pack-bitmap: check subtree bits before recursing\n pack-bitmap: reuse stored selected bitmaps\n pack-bitmap: consolidate `find_object_pos()` success path\n pack-bitmap: cache object positions during fill\n pack-bitmap: sort bitmaps before XORing\n pack-bitmap: remember pseudo-merge parents\n pack-bitmap: build pseudo-merge bitmaps after regular bitmaps\n\n pack-bitmap-write.c | 431 +++++++++++++++++++++++++++++++++++++-------\n pack-bitmap.h | 7 +\n 2 files changed, 377 insertions(+), 61 deletions(-)\n\nRange-diff against v1:\n1: 13191c19b91 = 1: ad025810ab3 pack-bitmap: pass object position to `fill_bitmap_tree()`\n2: 7d6d1cec0dd = 2: 59da63d0330 pack-bitmap: check subtree bits before recursing\n3: 6e1f6bef5f6 = 3: f13d65c0ad9 pack-bitmap: reuse stored selected bitmaps\n4: c9a56066094 ! 4: 856aa3a6ab7 pack-bitmap: consolidate `find_object_pos()` success path\n @@ Commit message\n Signed-off-by: Taylor Blau \n \n ## pack-bitmap-write.c ##\n +@@ pack-bitmap-write.c: static uint32_t find_object_pos(struct bitmap_writer *writer,\n + \t\t\t\tconst struct object_id *oid, int *found)\n + {\n + \tstruct object_entry *entry;\n ++\tuint32_t pos;\n + \n + \tentry = packlist_find(writer->to_pack, oid);\n + \tif (entry) {\n @@ pack-bitmap-write.c: static uint32_t find_object_pos(struct bitmap_writer *writer,\n \t\tif (writer->midx)\n \t\t\tbase_objects = writer->midx->num_objects +\n5: e43ef6a42d1 ! 5: 70dfa80d543 pack-bitmap: cache object positions during fill\n @@ pack-bitmap-write.c: void bitmap_writer_push_commit(struct bitmap_writer *writer\n \t\t\t\tconst struct object_id *oid, int *found)\n {\n \tstruct object_entry *entry;\n -+\tuint32_t pos;\n -+\n + \tuint32_t pos;\n + \n +\tbitmap_writer_init_pos_cache(writer);\n +\n +\tif (find_cached_object_pos(writer, oid, &pos)) {\n @@ pack-bitmap-write.c: void bitmap_writer_push_commit(struct bitmap_writer *writer\n +\t\t\t*found = 1;\n +\t\treturn pos;\n +\t}\n - \n ++\n \tentry = packlist_find(writer->to_pack, oid);\n \tif (entry) {\n \t\tuint32_t base_objects = 0;\n6: b0a4f31353a = 6: b1184792d23 pack-bitmap: sort bitmaps before XORing\n7: 0bd88e6a096 = 7: 673b6262911 pack-bitmap: remember pseudo-merge parents\n8: 30ce254312c ! 8: 8722242f1bb pack-bitmap: build pseudo-merge bitmaps after regular bitmaps\n @@ Commit message\n portion of history reachable by one or more pseudo-merge(s), but not by\n any non-pseudo-merge commit selected for bitmapping.\n \n - Now that we have decoupled how we generate pseudo-merges from their\n - representation, the following commits will improve the API around\n - specifying pseudo-merge groupings during bitmap generation.\n -\n Signed-off-by: Taylor Blau \n \n ## pack-bitmap-write.c ##\n\nbase-commit: c3d7ca7d982efc3a848fd85f34e867cfc0a99479\n-- \n2.54.0.rc1.84.g1cf18622df7\n"},{"id":"544185","messageId":"ad025810ab3c14152998755f6ea74cffc2438f92.1779911733.git.me@ttaylorr.com","threadId":"65661","inReplyTo":"cover.1779911733.git.me@ttaylorr.com","subject":"[PATCH v2 1/8] pack-bitmap: pass object position to `fill_bitmap_tree()`","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2026-05-27T19:55:50Z","receivedAt":"2026-05-27T19:55:52Z","isPatch":true,"body":"In the following commit, callers of `fill_bitmap_tree()` will be\nrequired to check the bit corresponding to their tree before calling\nthat function. That change will reduce the overhead of setting up and\ntearing down stack frames for trees whose bits are already set.\n\nTo prepare for that change, have callers pass in the tree's bit position\nin `fill_bitmap_tree()`, which will make the next commit easier to read.\n\nIn the meantime, this change has a surprising and measurable benefit\nduring bitmap generation, particularly on very large repositories.\n\nWhen processing sub-trees within `fill_bitmap_tree()`, the preimage of\nthis patch did the following:\n\n while (tree_entry(&desc, entry)) {\n switch (object_type(entry.mode)) {\n case OBJ_TREE:\n if (fill_bitmap_tree(writer, bitmap,\n lookup_tree(writer->repo,\n &entry.oid)) < 0) {\n /* ... */\n }\n /* ... */\n }\n }\n\n, first performing the object lookup via `lookup_tree()`, and then\nlocating its bit position within the recursive call. This patch\neffectively reorders those two calls so that we first discover the\nsub-tree's bit position, *then* load its tree.\n\nBy reordering these two operations, we spend fewer CPU cycles per\ninstruction, likely due to improved CPU dependency/cache/pipeline\nbehavior. Comparing the results of: running `perf stat` before and after\nthis commit, we have:\n\n +--------------+-------------+-------------+-------------------+\n | | HEAD^ | HEAD | Delta |\n +--------------+-------------+-------------+-------------------+\n | elapsed | 612.5 s | 582.4 s | -30.1 s (-4.9%) |\n | cycles | 2,857.3 B | 2,713.3 B | -144.0 B (-5.0%) |\n | instructions | 2,413.2 B | 2,415.5 B | +2.3 B (+0.1%) |\n | CPI | 1.184 | 1.123 | -0.061 (-5.1%) |\n +--------------+-------------+-------------+-------------------+\n\nIn a large repository with ~4.8M commit, and ~37.1M tree objects this\nchange improves timing from ~612.5 seconds down to ~582.4 seconds, or a\n~4.9% improvement. More importantly, the number of CPU cycles spent\ndropped off significantly as a result of this commit, lowering our\ncycles-per-instruction ratio by about ~5.1%.\n\nSigned-off-by: Taylor Blau \n---\n pack-bitmap-write.c | 23 +++++++++++++++--------\n 1 file changed, 15 insertions(+), 8 deletions(-)\n\ndiff --git a/pack-bitmap-write.c b/pack-bitmap-write.c\nindex 1c8070f99c0..2d5ff8fd406 100644\n--- a/pack-bitmap-write.c\n+++ b/pack-bitmap-write.c\n@@ -456,10 +456,10 @@ static void bitmap_builder_clear(struct bitmap_builder *bb)\n \n static int fill_bitmap_tree(struct bitmap_writer *writer,\n \t\t\t struct bitmap *bitmap,\n-\t\t\t struct tree *tree)\n+\t\t\t struct tree *tree,\n+\t\t\t uint32_t pos)\n {\n \tint found;\n-\tuint32_t pos;\n \tstruct tree_desc desc;\n \tstruct name_entry entry;\n \n@@ -467,9 +467,6 @@ static int fill_bitmap_tree(struct bitmap_writer *writer,\n \t * If our bit is already set, then there is nothing to do. Both this\n \t * tree and all of its children will be set.\n \t */\n-\tpos = find_object_pos(writer, &tree->object.oid, &found);\n-\tif (!found)\n-\t\treturn -1;\n \tif (bitmap_get(bitmap, pos))\n \t\treturn 0;\n \tbitmap_set(bitmap, pos);\n@@ -482,8 +479,12 @@ static int fill_bitmap_tree(struct bitmap_writer *writer,\n \twhile (tree_entry(&desc, &entry)) {\n \t\tswitch (object_type(entry.mode)) {\n \t\tcase OBJ_TREE:\n+\t\t\tpos = find_object_pos(writer, &entry.oid, &found);\n+\t\t\tif (!found)\n+\t\t\t\treturn -1;\n \t\t\tif (fill_bitmap_tree(writer, bitmap,\n-\t\t\t\t\t lookup_tree(writer->repo, &entry.oid)) < 0)\n+\t\t\t\t\t lookup_tree(writer->repo,\n+\t\t\t\t\t\t\t &entry.oid), pos) < 0)\n \t\t\t\treturn -1;\n \t\t\tbreak;\n \t\tcase OBJ_BLOB:\n@@ -575,8 +576,14 @@ static int fill_bitmap_commit(struct bitmap_writer *writer,\n \t}\n \n \twhile (tree_queue->nr) {\n-\t\tif (fill_bitmap_tree(writer, ent->bitmap,\n-\t\t\t\t prio_queue_get(tree_queue)) < 0)\n+\t\tstruct tree *t = prio_queue_get(tree_queue);\n+\t\tint found;\n+\n+\t\tpos = find_object_pos(writer, &t->object.oid, &found);\n+\t\tif (!found)\n+\t\t\treturn -1;\n+\n+\t\tif (fill_bitmap_tree(writer, ent->bitmap, t, pos) < 0)\n \t\t\treturn -1;\n \t}\n \treturn 0;\n-- \n2.54.0.rc1.84.g1cf18622df7\n\n"},{"id":"544186","messageId":"59da63d0330de760a4c144d210e70c44e1e142c0.1779911733.git.me@ttaylorr.com","threadId":"65661","inReplyTo":"cover.1779911733.git.me@ttaylorr.com","subject":"[PATCH v2 2/8] pack-bitmap: check subtree bits before recursing","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2026-05-27T19:55:53Z","receivedAt":"2026-05-27T19:55:55Z","isPatch":true,"body":"In the previous commit, we adjusted the callers of `fill_bitmap_tree()`\nto pass in the bit position of the tree they wish to fill.\n\nThis commit makes use of that information at the call site to avoid\nsetting up a stack frame for fill_bitmap_tree() entirely whenever a\ntree's bit position is already set.\n\nSince this is such a hot path, the avoided cost of setting up and\ntearing down stack frames for each noop'd call to `fill_bitmap_tree()`\nis significant:\n\n +--------------+-------------+-------------+-------------------+\n | | HEAD^ | HEAD | Delta |\n +--------------+-------------+-------------+-------------------+\n | elapsed | 582.4 s | 562.8 s | -19.6 s (-3.4%) |\n | cycles | 2,713.3 B | 2,621.3 B | -92.0 B (-3.4%) |\n | instructions | 2,415.5 B | 2,348.9 B | -66.6 B (-2.8%) |\n | CPI | 1.123 | 1.116 | -0.007 (-0.7%) |\n +--------------+-------------+-------------+-------------------+\n\nIn the same repository as in the previous commit, our timings dropped\nfrom ~582.4 seconds down to ~562.77 seconds.\n\nWhile the cycles-per-instruction ratio is basically unchanged, we\nexecute significantly fewer instructions, and correspondingly fewer\ncycles.\n\nSigned-off-by: Taylor Blau \n---\n pack-bitmap-write.c | 23 +++++++++++++++++------\n 1 file changed, 17 insertions(+), 6 deletions(-)\n\ndiff --git a/pack-bitmap-write.c b/pack-bitmap-write.c\nindex 2d5ff8fd406..72610397020 100644\n--- a/pack-bitmap-write.c\n+++ b/pack-bitmap-write.c\n@@ -463,12 +463,6 @@ static int fill_bitmap_tree(struct bitmap_writer *writer,\n \tstruct tree_desc desc;\n \tstruct name_entry entry;\n \n-\t/*\n-\t * If our bit is already set, then there is nothing to do. Both this\n-\t * tree and all of its children will be set.\n-\t */\n-\tif (bitmap_get(bitmap, pos))\n-\t\treturn 0;\n \tbitmap_set(bitmap, pos);\n \n \tif (repo_parse_tree(writer->repo, tree) < 0)\n@@ -482,6 +476,15 @@ static int fill_bitmap_tree(struct bitmap_writer *writer,\n \t\t\tpos = find_object_pos(writer, &entry.oid, &found);\n \t\t\tif (!found)\n \t\t\t\treturn -1;\n+\t\t\tif (bitmap_get(bitmap, pos)) {\n+\t\t\t\t/*\n+\t\t\t\t * If our bit is already set, then there\n+\t\t\t\t * is nothing to do. Both this tree and\n+\t\t\t\t * all of its children will be set.\n+\t\t\t\t */\n+\t\t\t\tbreak;\n+\t\t\t}\n+\n \t\t\tif (fill_bitmap_tree(writer, bitmap,\n \t\t\t\t\t lookup_tree(writer->repo,\n \t\t\t\t\t\t\t &entry.oid), pos) < 0)\n@@ -582,6 +585,14 @@ static int fill_bitmap_commit(struct bitmap_writer *writer,\n \t\tpos = find_object_pos(writer, &t->object.oid, &found);\n \t\tif (!found)\n \t\t\treturn -1;\n+\t\tif (bitmap_get(ent->bitmap, pos)) {\n+\t\t\t/*\n+\t\t\t * If our bit is already set, then there is\n+\t\t\t * nothing to do. Both this tree and all of its\n+\t\t\t * children will be set.\n+\t\t\t */\n+\t\t\tcontinue;\n+\t\t}\n \n \t\tif (fill_bitmap_tree(writer, ent->bitmap, t, pos) < 0)\n \t\t\treturn -1;\n-- \n2.54.0.rc1.84.g1cf18622df7\n\n"},{"id":"544187","messageId":"f13d65c0ad9d57bea2eb81a58d7e9f25c25b9e68.1779911733.git.me@ttaylorr.com","threadId":"65661","inReplyTo":"cover.1779911733.git.me@ttaylorr.com","subject":"[PATCH v2 3/8] pack-bitmap: reuse stored selected bitmaps","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2026-05-27T19:55:56Z","receivedAt":"2026-05-27T19:55:58Z","isPatch":true,"body":"When `fill_bitmap_commit()` reaches an ancestor that was selected for\nits own bitmap and processed earlier, its object closure is already\nstored in `writer->bitmaps` as an EWAH bitmap. As a result, walking\nthrough that commit's tree and parents again is redundant.\n\nTeach `fill_bitmap_commit()` to notice that case. For non-root commits in\nthe walk, look for a stored selected bitmap and OR it into the bitmap\nbeing built. If one exists, skip the commit, its tree, and its parents.\n\nBuilding bitmaps from scratch on the same test repository from the\nprevious commits yields a significant speed-up:\n\n +------------------+-------------+-------------+---------------------+\n | | HEAD^ | HEAD | Delta |\n +------------------+-------------+-------------+---------------------+\n | elapsed | 562.8 s | 324.8 s | -237.9 s (-42.3%) |\n | cycles | 2,621.3 B | 1,508.6 B | -1,112.7 B (-42.4%) |\n | instructions | 2,348.9 B | 1,436.6 B | -912.3 B (-38.8%) |\n | CPI | 1.116 | 1.050 | -0.066 (-5.9%) |\n +------------------+-------------+-------------+---------------------+\n\nIn our testing repository, there are 1,261 commits selected for bitmap\ncoverage, and 1,382 maximal commits induced as a result of that. Of the\n1,382 calls made to `fill_bitmap_commit()` (one per maximal commit), 131\nof them can be short-circuited at some point during their traversal as a\nconsequence of this change.\n\nIn large repositories where the cost of filling the bitmap for any\nindividual commit is large, being able to short-circuit even ~9.5% of\nthe calls to `fill_bitmap_commit()` results in a significant savings.\n\nSigned-off-by: Taylor Blau \n---\n pack-bitmap-write.c | 34 ++++++++++++++++++++++++++++++++++\n 1 file changed, 34 insertions(+)\n\ndiff --git a/pack-bitmap-write.c b/pack-bitmap-write.c\nindex 72610397020..651ad467469 100644\n--- a/pack-bitmap-write.c\n+++ b/pack-bitmap-write.c\n@@ -509,6 +509,9 @@ static int fill_bitmap_tree(struct bitmap_writer *writer,\n static int reused_bitmaps_nr;\n static int reused_pseudo_merge_bitmaps_nr;\n \n+static int fill_bitmap_commit_calls_nr;\n+static int fill_bitmap_commit_found_ancestor_nr;\n+\n static int fill_bitmap_commit(struct bitmap_writer *writer,\n \t\t\t struct bb_commit *ent,\n \t\t\t struct commit *commit,\n@@ -519,6 +522,9 @@ static int fill_bitmap_commit(struct bitmap_writer *writer,\n {\n \tint found;\n \tuint32_t pos;\n+\n+\tfill_bitmap_commit_calls_nr++;\n+\n \tif (!ent->bitmap)\n \t\tent->bitmap = bitmap_new();\n \n@@ -553,6 +559,28 @@ static int fill_bitmap_commit(struct bitmap_writer *writer,\n \t\t\tbitmap_free(remapped);\n \t\t}\n \n+\t\t/*\n+\t\t * If we encounter an ancestor for which we have already\n+\t\t * computed a bitmap during this build (i.e. a regular\n+\t\t * selected commit processed earlier in topo order), we can\n+\t\t * short-circuit the walk: its stored bitmap already covers\n+\t\t * the commit itself, its tree, and all of its ancestors.\n+\t\t */\n+\t\tif (c != commit) {\n+\t\t\tkhiter_t hash_pos = kh_get_oid_map(writer->bitmaps,\n+\t\t\t\t\t\t\t c->object.oid);\n+\t\t\tif (hash_pos != kh_end(writer->bitmaps)) {\n+\t\t\t\tstruct bitmapped_commit *stored =\n+\t\t\t\t\tkh_value(writer->bitmaps, hash_pos);\n+\t\t\t\tif (stored && stored->bitmap) {\n+\t\t\t\t\tfill_bitmap_commit_found_ancestor_nr++;\n+\t\t\t\t\tbitmap_or_ewah(ent->bitmap,\n+\t\t\t\t\t\t stored->bitmap);\n+\t\t\t\t\tcontinue;\n+\t\t\t\t}\n+\t\t\t}\n+\t\t}\n+\n \t\t/*\n \t\t * Mark ourselves and queue our tree. The commit\n \t\t * walk ensures we cover all parents.\n@@ -692,6 +720,12 @@ int bitmap_writer_build(struct bitmap_writer *writer)\n \ttrace2_data_intmax(\"pack-bitmap-write\", writer->repo,\n \t\t\t \"building_bitmaps_pseudo_merge_reused\",\n \t\t\t reused_pseudo_merge_bitmaps_nr);\n+\ttrace2_data_intmax(\"pack-bitmap-write\", writer->repo,\n+\t\t\t \"fill_bitmap_commit_calls_nr\",\n+\t\t\t fill_bitmap_commit_calls_nr);\n+\ttrace2_data_intmax(\"pack-bitmap-write\", writer->repo,\n+\t\t\t \"fill_bitmap_commit_found_ancestor_nr\",\n+\t\t\t fill_bitmap_commit_found_ancestor_nr);\n \n \tstop_progress(&writer->progress);\n \n-- \n2.54.0.rc1.84.g1cf18622df7\n\n"},{"id":"544188","messageId":"856aa3a6ab7e814490386fb0719072c4fad8be8d.1779911733.git.me@ttaylorr.com","threadId":"65661","inReplyTo":"cover.1779911733.git.me@ttaylorr.com","subject":"[PATCH v2 4/8] pack-bitmap: consolidate `find_object_pos()` success path","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2026-05-27T19:55:59Z","receivedAt":"2026-05-27T19:56:01Z","isPatch":true,"body":"Both sides of `find_object_pos()` report success in the same way by\nsetting the optional `found` out-parameter and return the resolved\nbitmap position.\n\nPrepare for adding more bookkeeping around object-position lookups by\nstoring the result in a local `pos` variable and sharing the success\nreturn path between the packlist and MIDX cases.\n\nSigned-off-by: Taylor Blau \n---\n pack-bitmap-write.c | 18 +++++++++---------\n 1 file changed, 9 insertions(+), 9 deletions(-)\n\ndiff --git a/pack-bitmap-write.c b/pack-bitmap-write.c\nindex 651ad467469..42ed22feacc 100644\n--- a/pack-bitmap-write.c\n+++ b/pack-bitmap-write.c\n@@ -217,6 +217,7 @@ static uint32_t find_object_pos(struct bitmap_writer *writer,\n \t\t\t\tconst struct object_id *oid, int *found)\n {\n \tstruct object_entry *entry;\n+\tuint32_t pos;\n \n \tentry = packlist_find(writer->to_pack, oid);\n \tif (entry) {\n@@ -224,23 +225,22 @@ static uint32_t find_object_pos(struct bitmap_writer *writer,\n \t\tif (writer->midx)\n \t\t\tbase_objects = writer->midx->num_objects +\n \t\t\t\twriter->midx->num_objects_in_base;\n-\n-\t\tif (found)\n-\t\t\t*found = 1;\n-\t\treturn oe_in_pack_pos(writer->to_pack, entry) + base_objects;\n+\t\tpos = oe_in_pack_pos(writer->to_pack, entry) + base_objects;\n \t} else if (writer->midx) {\n-\t\tuint32_t at, pos;\n+\t\tuint32_t at;\n \n \t\tif (!bsearch_midx(oid, writer->midx, &at))\n \t\t\tgoto missing;\n \t\tif (midx_to_pack_pos(writer->midx, at, &pos) < 0)\n \t\t\tgoto missing;\n-\n-\t\tif (found)\n-\t\t\t*found = 1;\n-\t\treturn pos;\n+\t} else {\n+\t\tgoto missing;\n \t}\n \n+\tif (found)\n+\t\t*found = 1;\n+\treturn pos;\n+\n missing:\n \tif (found)\n \t\t*found = 0;\n-- \n2.54.0.rc1.84.g1cf18622df7\n\n"},{"id":"544189","messageId":"70dfa80d5436007aed0f9c27e7bab8c6c1d6742c.1779911733.git.me@ttaylorr.com","threadId":"65661","inReplyTo":"cover.1779911733.git.me@ttaylorr.com","subject":"[PATCH v2 5/8] pack-bitmap: cache object positions during fill","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2026-05-27T19:56:02Z","receivedAt":"2026-05-27T19:56:04Z","isPatch":true,"body":"The previous commits removed some redundant work from bitmap generation\nby avoiding unnecessary tree recursion and by reusing selected bitmaps\nthat have already been computed.\n\nEven with those changes in place, there is still an extremely hot path\nfrom `fill_bitmap_commit()` and `fill_bitmap_tree()` to translate object\nIDs into their corresponding bit positions in order to generate their\nbitmaps.\n\nIn a small repository, this overhead is not significant. However, in a\nvery large repository (e.g., the one that we have been using as a\nbenchmark over the past several commits with ~57M total objects), the\noverhead of locating object bit positions (often repeatedly) adds up\nsignificantly.\n\nCombat this by adding a small, direct-mapped cache to the bitmap writer\nwhich maps object IDs to their corresponding bit positions. Size the\ncache according to the number of objects being written, with fixed lower\nand upper bounds so small repositories do not pay for a large table and\nlarge repositories can avoid most repeated packlist and MIDX lookups.\n\nOn my machine with (a somewhat outdated) GCC 15.2.0, each entry in the\ncache is 40 bytes wide:\n\n $ pahole -C bitmap_pos_cache_entry pack-bitmap-write.o\n struct bitmap_pos_cache_entry {\n struct object_id oid; /* 0 36 */\n uint32_t pos; /* 36 4 */\n\n /* size: 40, cachelines: 1, members: 2 */\n /* last cacheline: 40 bytes */\n };\n\n, and we will allocate up to 2^21 entries for a maximum total of 80 MiB\nof cache overhead.\n\nIn our example repository from above and in earlier commits, this\nresults in a ~9.4% reduction in runtime relative to the previous commit:\n\n +------------------+-------------+-------------+---------------------+\n | | HEAD^ | HEAD | Delta |\n +------------------+-------------+-------------+---------------------+\n | elapsed | 324.8 s | 294.1 s | -30.7 s (-9.4%) |\n | cycles | 1,508.6 B | 1,365.5 B | -143.0 B (-9.5%) |\n | instructions | 1,436.6 B | 1,389.8 B | -46.9 B (-3.3%) |\n | CPI | 1.050 | 0.983 | -0.068 (-6.4%) |\n +------------------+-------------+-------------+---------------------+\n\nWhen generating bitmaps on this repository (to produce the above\ntimings), the cache grew to its maximum size of 80 MiB, and resulted in\n1.024B cache hits and 59.957M cache misses.\n\nSigned-off-by: Taylor Blau \n---\n pack-bitmap-write.c | 88 ++++++++++++++++++++++++++++++++++++++++++++-\n pack-bitmap.h | 7 ++++\n 2 files changed, 94 insertions(+), 1 deletion(-)\n\ndiff --git a/pack-bitmap-write.c b/pack-bitmap-write.c\nindex 42ed22feacc..4b6fb07edd7 100644\n--- a/pack-bitmap-write.c\n+++ b/pack-bitmap-write.c\n@@ -89,6 +89,7 @@ void bitmap_writer_free(struct bitmap_writer *writer)\n \tewah_free(writer->tags);\n \n \tkh_destroy_oid_map(writer->bitmaps);\n+\tfree(writer->pos_cache);\n \n \tkh_foreach_value(writer->pseudo_merge_commits, idx,\n \t\t\t free_pseudo_merge_commit_idx(idx));\n@@ -213,15 +214,92 @@ void bitmap_writer_push_commit(struct bitmap_writer *writer,\n \twriter->selected_nr++;\n }\n \n+struct bitmap_pos_cache_entry {\n+\tstruct object_id oid;\n+\tuint32_t pos;\n+};\n+\n+#define BITMAP_POS_MIN_CACHE_SIZE (1U << 10)\n+#define BITMAP_POS_MAX_CACHE_SIZE (1U << 21)\n+#define BITMAP_POS_CACHE_VALID (1U << 31)\n+\n+static void bitmap_writer_init_pos_cache(struct bitmap_writer *writer)\n+{\n+\tif (writer->pos_cache)\n+\t\treturn;\n+\n+\twriter->pos_cache_nr = BITMAP_POS_MIN_CACHE_SIZE;\n+\n+\twhile (writer->pos_cache_nr < writer->to_pack->nr_objects &&\n+\t writer->pos_cache_nr < BITMAP_POS_MAX_CACHE_SIZE)\n+\t\twriter->pos_cache_nr <<= 1;\n+\n+\tCALLOC_ARRAY(writer->pos_cache, writer->pos_cache_nr);\n+}\n+\n+static size_t bitmap_writer_pos_cache_slot(struct bitmap_writer *writer,\n+\t\t\t\t\t const struct object_id *oid)\n+{\n+\treturn oidhash(oid) & (writer->pos_cache_nr - 1);\n+}\n+\n+static bool bitmap_writer_pos_cache_valid(struct bitmap_writer *writer,\n+\t\t\t\t\t size_t slot)\n+{\n+\treturn !!(writer->pos_cache[slot].pos & BITMAP_POS_CACHE_VALID);\n+}\n+\n+static int find_cached_object_pos(struct bitmap_writer *writer,\n+\t\t\t\t const struct object_id *oid, uint32_t *pos)\n+{\n+\tsize_t slot = bitmap_writer_pos_cache_slot(writer, oid);\n+\n+\tif (bitmap_writer_pos_cache_valid(writer, slot) &&\n+\t oideq(&writer->pos_cache[slot].oid, oid)) {\n+\t\twriter->pos_cache_hits++;\n+\t\t*pos = writer->pos_cache[slot].pos & ~BITMAP_POS_CACHE_VALID;\n+\t\treturn 1;\n+\t}\n+\n+\twriter->pos_cache_misses++;\n+\treturn 0;\n+}\n+\n+static uint32_t store_cached_object_pos(struct bitmap_writer *writer,\n+\t\t\t\t\tconst struct object_id *oid,\n+\t\t\t\t\tuint32_t pos)\n+{\n+\tsize_t slot;\n+\n+\tif (pos & BITMAP_POS_CACHE_VALID)\n+\t\treturn pos; /* too large to cache */\n+\n+\tslot = bitmap_writer_pos_cache_slot(writer, oid);\n+\n+\toidcpy(&writer->pos_cache[slot].oid, oid);\n+\twriter->pos_cache[slot].pos = pos | BITMAP_POS_CACHE_VALID;\n+\n+\treturn pos;\n+}\n+\n static uint32_t find_object_pos(struct bitmap_writer *writer,\n \t\t\t\tconst struct object_id *oid, int *found)\n {\n \tstruct object_entry *entry;\n \tuint32_t pos;\n \n+\tbitmap_writer_init_pos_cache(writer);\n+\n+\tif (find_cached_object_pos(writer, oid, &pos)) {\n+\t\tif (found)\n+\t\t\t*found = 1;\n+\t\treturn pos;\n+\t}\n+\n \tentry = packlist_find(writer->to_pack, oid);\n \tif (entry) {\n \t\tuint32_t base_objects = 0;\n+\n \t\tif (writer->midx)\n \t\t\tbase_objects = writer->midx->num_objects +\n \t\t\t\twriter->midx->num_objects_in_base;\n@@ -239,7 +317,7 @@ static uint32_t find_object_pos(struct bitmap_writer *writer,\n \n \tif (found)\n \t\t*found = 1;\n-\treturn pos;\n+\treturn store_cached_object_pos(writer, oid, pos);\n \n missing:\n \tif (found)\n@@ -662,6 +740,10 @@ int bitmap_writer_build(struct bitmap_writer *writer)\n \t\twriter->progress = start_progress(writer->repo,\n \t\t\t\t\t\t \"Building bitmaps\",\n \t\t\t\t\t\t writer->selected_nr);\n+\n+\twriter->pos_cache_hits = 0;\n+\twriter->pos_cache_misses = 0;\n+\n \ttrace2_region_enter(\"pack-bitmap-write\", \"building_bitmaps_total\",\n \t\t\t writer->repo);\n \n@@ -726,6 +808,10 @@ int bitmap_writer_build(struct bitmap_writer *writer)\n \ttrace2_data_intmax(\"pack-bitmap-write\", writer->repo,\n \t\t\t \"fill_bitmap_commit_found_ancestor_nr\",\n \t\t\t fill_bitmap_commit_found_ancestor_nr);\n+\ttrace2_data_intmax(\"pack-bitmap-write\", writer->repo,\n+\t\t\t \"bitmap_pos_cache_hits\", writer->pos_cache_hits);\n+\ttrace2_data_intmax(\"pack-bitmap-write\", writer->repo,\n+\t\t\t \"bitmap_pos_cache_misses\", writer->pos_cache_misses);\n \n \tstop_progress(&writer->progress);\n \ndiff --git a/pack-bitmap.h b/pack-bitmap.h\nindex a95e1c2d115..19a86554579 100644\n--- a/pack-bitmap.h\n+++ b/pack-bitmap.h\n@@ -132,6 +132,8 @@ int bitmap_has_oid_in_uninteresting(struct bitmap_index *, const struct object_i\n \n off_t get_disk_usage_from_bitmap(struct bitmap_index *, struct rev_info *);\n \n+struct bitmap_pos_cache_entry;\n+\n struct bitmap_writer {\n \tstruct repository *repo;\n \tstruct ewah_bitmap *commits;\n@@ -143,6 +145,11 @@ struct bitmap_writer {\n \tstruct packing_data *to_pack;\n \tstruct multi_pack_index *midx; /* if appending to a MIDX chain */\n \n+\tstruct bitmap_pos_cache_entry *pos_cache;\n+\tsize_t pos_cache_nr;\n+\tuint64_t pos_cache_hits;\n+\tuint64_t pos_cache_misses;\n+\n \tstruct bitmapped_commit *selected;\n \tunsigned int selected_nr, selected_alloc;\n \n-- \n2.54.0.rc1.84.g1cf18622df7\n\n"},{"id":"544190","messageId":"b1184792d23b2d24309d09f476cb0d93f8e81536.1779911733.git.me@ttaylorr.com","threadId":"65661","inReplyTo":"cover.1779911733.git.me@ttaylorr.com","subject":"[PATCH v2 6/8] pack-bitmap: sort bitmaps before XORing","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2026-05-27T19:56:05Z","receivedAt":"2026-05-27T19:56:07Z","isPatch":true,"body":"Reachability bitmaps may be stored as XORs against nearby bitmaps, up to\n10 away. However, when callers provide selected commits in an arbitrary\norder, the writer may miss good ancestor/descendant pairs and produce\nmuch larger bitmap files without changing query coverage.\n\nSort the selected bitmaps in date order (from oldest to newest) before\ncomputing XOR offsets, leaving pseudo-merge bitmaps alone (which we will\ndeal with separately in following commits).\n\nOn our same testing repository from previous commits, this change shrunk\nour selection of 1,261 bitmaps from ~635.46 MiB to 176.4 MiB for a\n~72.24% reduction in the on-disk size of our *.bitmap file. The time to\ngenerate the smaller bitmap file decreased by ~3.69 seconds, though this\nis likely mostly noise.\n\nSigned-off-by: Taylor Blau \n---\n pack-bitmap-write.c | 29 +++++++++++++++++++++++++++++\n 1 file changed, 29 insertions(+)\n\ndiff --git a/pack-bitmap-write.c b/pack-bitmap-write.c\nindex 4b6fb07edd7..66282ea14b5 100644\n--- a/pack-bitmap-write.c\n+++ b/pack-bitmap-write.c\n@@ -327,11 +327,40 @@ static uint32_t find_object_pos(struct bitmap_writer *writer,\n \treturn 0;\n }\n \n+static int bitmapped_commit_date_cmp(const void *_a, const void *_b)\n+{\n+\tconst struct bitmapped_commit *a = _a;\n+\tconst struct bitmapped_commit *b = _b;\n+\n+\tif (a->commit->date < b->commit->date)\n+\t\treturn -1;\n+\tif (a->commit->date > b->commit->date)\n+\t\treturn 1;\n+\treturn 0;\n+}\n+\n static void compute_xor_offsets(struct bitmap_writer *writer)\n {\n \tstatic const int MAX_XOR_OFFSET_SEARCH = 10;\n \n \tint i, next = 0;\n+\tint nr = bitmap_writer_nr_selected_commits(writer);\n+\n+\tif (nr > 1) {\n+\t\tQSORT(writer->selected, nr, bitmapped_commit_date_cmp);\n+\n+\t\tfor (i = 0; i < nr; i++) {\n+\t\t\tstruct bitmapped_commit *stored = &writer->selected[i];\n+\t\t\tkhiter_t hash_pos = kh_get_oid_map(writer->bitmaps,\n+\t\t\t\t\t\t\t stored->commit->object.oid);\n+\n+\t\t\tif (hash_pos == kh_end(writer->bitmaps))\n+\t\t\t\tBUG(\"selected commit missing from bitmap map: %s\",\n+\t\t\t\t oid_to_hex(&stored->commit->object.oid));\n+\n+\t\t\tkh_value(writer->bitmaps, hash_pos) = stored;\n+\t\t}\n+\t}\n \n \twhile (next < writer->selected_nr) {\n \t\tstruct bitmapped_commit *stored = &writer->selected[next];\n-- \n2.54.0.rc1.84.g1cf18622df7\n\n"},{"id":"544191","messageId":"673b6262911dbcc8a8fdb11995f7c112f5330906.1779911733.git.me@ttaylorr.com","threadId":"65661","inReplyTo":"cover.1779911733.git.me@ttaylorr.com","subject":"[PATCH v2 7/8] pack-bitmap: remember pseudo-merge parents","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2026-05-27T19:56:08Z","receivedAt":"2026-05-27T19:56:10Z","isPatch":true,"body":"write_pseudo_merges() currently builds an array of temporary bitmaps for\nthe parent set of each pseudo-merge, then serializes those bitmaps later\nwhile writing the extension.\n\nMove those parent bitmaps onto the corresponding bitmapped_commit\nentries instead. This keeps the on-disk output unchanged, but gives the\nparent bitmap the same lifetime and access pattern that later changes\nwill use when pseudo-merge object bitmaps are built before the write\nstep.\n\nSigned-off-by: Taylor Blau \n---\n pack-bitmap-write.c | 30 +++++++++++++++++-------------\n 1 file changed, 17 insertions(+), 13 deletions(-)\n\ndiff --git a/pack-bitmap-write.c b/pack-bitmap-write.c\nindex 66282ea14b5..8200aed6101 100644\n--- a/pack-bitmap-write.c\n+++ b/pack-bitmap-write.c\n@@ -32,6 +32,7 @@ struct bitmapped_commit {\n \tstruct commit *commit;\n \tstruct ewah_bitmap *bitmap;\n \tstruct ewah_bitmap *write_as;\n+\tstruct ewah_bitmap *pseudo_merge_parents;\n \tint flags;\n \tint xor_offset;\n \tuint32_t commit_pos;\n@@ -102,6 +103,7 @@ void bitmap_writer_free(struct bitmap_writer *writer)\n \t\tif (bc->write_as != bc->bitmap)\n \t\t\tewah_free(bc->write_as);\n \t\tewah_free(bc->bitmap);\n+\t\tewah_free(bc->pseudo_merge_parents);\n \t}\n \tfree(writer->selected);\n }\n@@ -210,6 +212,7 @@ void bitmap_writer_push_commit(struct bitmap_writer *writer,\n \twriter->selected[writer->selected_nr].write_as = NULL;\n \twriter->selected[writer->selected_nr].flags = 0;\n \twriter->selected[writer->selected_nr].pseudo_merge = pseudo_merge;\n+\twriter->selected[writer->selected_nr].pseudo_merge_parents = NULL;\n \n \twriter->selected_nr++;\n }\n@@ -1004,42 +1007,47 @@ static void write_pseudo_merges(struct bitmap_writer *writer,\n \t\t\t\tstruct hashfile *f)\n {\n \tstruct oid_array commits = OID_ARRAY_INIT;\n-\tstruct bitmap **commits_bitmap = NULL;\n \toff_t *pseudo_merge_ofs = NULL;\n \toff_t start, table_start, next_ext;\n \n \tuint32_t base = bitmap_writer_nr_selected_commits(writer);\n \tsize_t i, j = 0;\n \n-\tCALLOC_ARRAY(commits_bitmap, writer->pseudo_merges_nr);\n \tCALLOC_ARRAY(pseudo_merge_ofs, writer->pseudo_merges_nr);\n \n \tfor (i = 0; i < writer->pseudo_merges_nr; i++) {\n \t\tstruct bitmapped_commit *merge = &writer->selected[base + i];\n \t\tstruct commit_list *p;\n+\t\tstruct bitmap *parents = bitmap_new();\n \n \t\tif (!merge->pseudo_merge)\n \t\t\tBUG(\"found non-pseudo merge commit at %\"PRIuMAX, (uintmax_t)i);\n \n-\t\tcommits_bitmap[i] = bitmap_new();\n-\n \t\tfor (p = merge->commit->parents; p; p = p->next)\n-\t\t\tbitmap_set(commits_bitmap[i],\n+\t\t\tbitmap_set(parents,\n \t\t\t\t find_object_pos(writer, &p->item->object.oid,\n \t\t\t\t\t\t NULL));\n+\n+\t\tmerge->pseudo_merge_parents = bitmap_to_ewah(parents);\n+\t\tbitmap_free(parents);\n \t}\n \n \tstart = hashfile_total(f);\n \n \tfor (i = 0; i < writer->pseudo_merges_nr; i++) {\n-\t\tstruct ewah_bitmap *commits_ewah = bitmap_to_ewah(commits_bitmap[i]);\n+\t\tstruct bitmapped_commit *merge = &writer->selected[base + i];\n+\n+\t\tif (!merge->pseudo_merge)\n+\t\t\tBUG(\"found non-pseudo merge commit at %\"PRIuMAX, (uintmax_t)i);\n+\n+\t\tif (!merge->pseudo_merge_parents)\n+\t\t\tBUG(\"missing pseudo-merge parents bitmap for commit %s\",\n+\t\t\t oid_to_hex(&merge->commit->object.oid));\n \n \t\tpseudo_merge_ofs[i] = hashfile_total(f);\n \n-\t\tdump_bitmap(f, commits_ewah);\n+\t\tdump_bitmap(f, merge->pseudo_merge_parents);\n \t\tdump_bitmap(f, writer->selected[base+i].write_as);\n-\n-\t\tewah_free(commits_ewah);\n \t}\n \n \tnext_ext = st_add(hashfile_total(f),\n@@ -1122,12 +1130,8 @@ static void write_pseudo_merges(struct bitmap_writer *writer,\n \thashwrite_be64(f, table_start - start);\n \thashwrite_be64(f, hashfile_total(f) - start + sizeof(uint64_t));\n \n-\tfor (i = 0; i < writer->pseudo_merges_nr; i++)\n-\t\tbitmap_free(commits_bitmap[i]);\n-\n \toid_array_clear(&commits);\n \tfree(pseudo_merge_ofs);\n-\tfree(commits_bitmap);\n }\n \n static int table_cmp(const void *_va, const void *_vb, void *_data)\n-- \n2.54.0.rc1.84.g1cf18622df7\n\n"},{"id":"544192","messageId":"8722242f1bb93a5ae9de4edb30b97806108227f2.1779911733.git.me@ttaylorr.com","threadId":"65661","inReplyTo":"cover.1779911733.git.me@ttaylorr.com","subject":"[PATCH v2 8/8] pack-bitmap: build pseudo-merge bitmaps after regular bitmaps","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2026-05-27T19:56:11Z","receivedAt":"2026-05-27T19:56:13Z","isPatch":true,"body":"When generating bitmaps, `bitmap_builder_init()` starts with an initial\nselection of commits to receive bitmap coverage, and then determines a\nset of \"maximal\" commits based on its input.\n\nCommit 089f751360f (pack-bitmap-write: build fewer intermediate bitmaps,\n2020-12-08) has extensive details, but the gist is as follows:\n\nEach selected commit starts with one commit_mask bit in its \"commit\nmask\" bitmap. Then, we walk the first-parent history in topological\norder and OR each commit's mask into its (first) parent. Whenever that\nOR results in the parent having more bits set, the child is deemed to be\nnon-maximal, and the frontier is pushed further back along the first\nparent history.\n\nThat approach works extremely well for ordinary selected commits, whose\nfirst-parent histories often describe real sharing between the bitmaps\nwe are going to write.\n\nIt struggles, however, to efficiently generate pseudo-merge bitmaps.\nUnlike ordinary commits for which the above algorithm is designed,\npseudo-merges don't represent any \"real\" commit in history, just a\ngrouping of non-bitmapped reference tips. In that sense, their first\nparent is just a part of a larger set, and treating them like ordinary\nselected commits imposes a significant slow-down when generating bitmaps\nwith pseudo-merges enabled.\n\nConsider partitioning all non-bitmapped reference tips into eight\nindividual pseudo-merges via the following configuration:\n\n [bitmapPseudoMerge \"all\"]\n pattern=refs/\n threshold=now\n stableSize=10000000\n maxMerges=8\n\n, the cost of generating a bitmap from scratch rises significantly:\n\n +------------------+-----------------+---------------+---------------------+\n | | no pseudo-merge | pseudo-merges | Delta |\n | | | (HEAD^) | |\n +------------------+-----------------+---------------+---------------------+\n | elapsed | 294.1 s | 575.0 s | +280.9 s (+95.5%) |\n | cycles | 1,365.5 B | 2,686.9 B | +1,321.4 B (+96.8%) |\n | instructions | 1,389.8 B | 2,546.6 B | +1,156.8 B (+83.2%) |\n | CPI | 0.983 | 1.055 | +0.073 (+7.4%) |\n +------------------+-----------------+---------------+---------------------+\n\nThis is a particularly poor trade-off, because the time saved by these\npseudo-merges during, e.g.,\n\n $ git rev-list --count --all --objects --use-bitmap-index\n\nis only:\n\n $ hyperfine -L v true,false -n 'pseudo-merges: {v}' '\n GIT_TEST_USE_PSEUDO_MERGES={v} git.compile rev-list --count \\\n --objects --all --use-bitmap-index\n '\n\n Benchmark 1: pseudo-merges: true\n Time (mean ± σ): 2.613 s ± 0.012 s [User: 2.308 s, System: 0.305 s]\n Range (min … max): 2.594 s … 2.633 s 10 runs\n\n Benchmark 2: pseudo-merges: false\n Time (mean ± σ): 52.205 s ± 0.170 s [User: 51.500 s, System: 0.697 s]\n Range (min … max): 51.956 s … 52.458 s 10 runs\n\n Summary\n pseudo-merges: true ran\n 19.98 ± 0.11 times faster than pseudo-merges: false\n\nIn other words, we pay a nearly ~5 minute penalty to generate\npseudo-merge bitmaps, but only save ~50 seconds during traversal.\n\nThe problem stems from injecting pseudo-merges into the bitmap builder\nas if they were normal commits. The maximal commit selection algorithm\nwas simply not designed for that case, and performs predictably poorly.\n\nThe only reason we reused the maximal commit selection routine for\npseudo-merges alongside regular non-pseudo-merge commits is because we\nrepresent them both as commit objects (where the pseudo-merge commits\njust represent a made-up commit as opposed to one that actually exists\nin a repository's object store).\n\nInstead, build the regular selected commit bitmaps first, considering\nonly non-pseudo-merge commits in `bitmap_builder_init()`. Once those\nbitmaps have been stored, build each pseudo-merge bitmap separately and\nattach its parent and object bitmaps to the corresponding pseudo-merge\nentry before writing the extension.\n\nThis keeps the regular bitmap build shaped like the no-pseudo-merge\ncase. The later pseudo-merge fill can still stop at stored selected\nancestor bitmaps, so it does not have to rewalk each pseudo-merge\nclosure from scratch.\n\nWhen an existing bitmap has the same pseudo-merge parent set, reuse and\nremap that whole pseudo-merge bitmap before falling back to\nfill_bitmap_commit(). This preserves the benefit of stable pseudo-merges\nwhile keeping the on-disk format and reader behavior unchanged.\n\nAs a result, the overhead cost for generating pseudo-merges in the above\nconfiguration is much smaller:\n\n +------------------+-----------------+---------------+-------------------+\n | | no pseudo-merge | pseudo-merges | Delta |\n | | | (HEAD) | |\n +------------------+-----------------+---------------+-------------------+\n | elapsed | 294.1 s | 328.4 s | +34.3 s (+11.7%) |\n | cycles | 1,365.5 B | 1,529.3 B | +163.7 B (+12.0%) |\n | instructions | 1,389.8 B | 1,552.8 B | +163.0 B (+11.7%) |\n | CPI | 0.983 | 0.985 | +0.002 (+0.2%) |\n +------------------+-----------------+---------------+-------------------+\n\nRecall that at the start of this series, generating reachability bitmaps\ntook 612.5 seconds *without* pseudo-merges. With this commit, it is\nstill ~46.38% *faster* to generate reachability bitmaps *with*\npseudo-merges than it was to generate bitmaps wihtout them at the\nbeginning of this series.\n\nThe changes to implement this are mostly straightforward. We exclude\npseudo-merge commits from the existing bitmap generation, and walk over\nthem in a separate pass, by either reusing an existing on-disk\npseudo-merge, or passing the pseudo-merge commit itself back to the\nexisting routine in `fill_bitmap_commit()`.\n\n(Note that the routine to build pseudo-merge bitmaps is the same both\nbefore and after this change, the difference is only that we do not let\npsuedo-merges participate in determining the set of maximal commits.)\n\nThe only wrinkle is that `fill_bitmap_commit()` must be taught to not\nexpect that all tree objects have been parsed, which is the case for any\nportion of history reachable by one or more pseudo-merge(s), but not by\nany non-pseudo-merge commit selected for bitmapping.\n\nSigned-off-by: Taylor Blau \n---\n pack-bitmap-write.c | 210 ++++++++++++++++++++++++++++++++++++--------\n 1 file changed, 174 insertions(+), 36 deletions(-)\n\ndiff --git a/pack-bitmap-write.c b/pack-bitmap-write.c\nindex 8200aed6101..1bcb3f98a42 100644\n--- a/pack-bitmap-write.c\n+++ b/pack-bitmap-write.c\n@@ -446,13 +446,17 @@ static void bitmap_builder_init(struct bitmap_builder *bb,\n \trevs.topo_order = 1;\n \trevs.first_parent_only = 1;\n \n-\tfor (i = 0; i < writer->selected_nr; i++) {\n+\tfor (i = 0; i < bitmap_writer_nr_selected_commits(writer); i++) {\n \t\tstruct bitmapped_commit *bc = &writer->selected[i];\n \t\tstruct bb_commit *ent = bb_data_at(&bb->data, bc->commit);\n \n+\t\tif (bc->pseudo_merge)\n+\t\t\tBUG(\"unexpected pseudo-merge at %\"PRIuMAX,\n+\t\t\t (uintmax_t)i);\n+\n \t\tent->selected = 1;\n \t\tent->maximal = 1;\n-\t\tent->pseudo_merge = bc->pseudo_merge;\n+\t\tent->pseudo_merge = 0;\n \t\tent->idx = i;\n \n \t\tent->commit_mask = bitmap_new();\n@@ -618,6 +622,8 @@ static int fill_bitmap_tree(struct bitmap_writer *writer,\n \n static int reused_bitmaps_nr;\n static int reused_pseudo_merge_bitmaps_nr;\n+static int pseudo_merge_bitmap_nr;\n+static int pseudo_merge_bitmap_parents;\n \n static int fill_bitmap_commit_calls_nr;\n static int fill_bitmap_commit_found_ancestor_nr;\n@@ -631,8 +637,12 @@ static int fill_bitmap_commit(struct bitmap_writer *writer,\n \t\t\t const uint32_t *mapping)\n {\n \tint found;\n+\tint from_pseudo_merge = commit->object.flags & BITMAP_PSEUDO_MERGE;\n \tuint32_t pos;\n \n+\tif (ent->pseudo_merge)\n+\t\tBUG(\"unexpected pseudo-merge commit in fill_bitmap_commit()\");\n+\n \tfill_bitmap_commit_calls_nr++;\n \n \tif (!ent->bitmap)\n@@ -648,10 +658,7 @@ static int fill_bitmap_commit(struct bitmap_writer *writer,\n \t\t\tstruct ewah_bitmap *old;\n \t\t\tstruct bitmap *remapped = bitmap_new();\n \n-\t\t\tif (commit->object.flags & BITMAP_PSEUDO_MERGE)\n-\t\t\t\told = pseudo_merge_bitmap_for_commit(old_bitmap, c);\n-\t\t\telse\n-\t\t\t\told = bitmap_for_commit(old_bitmap, c);\n+\t\t\told = bitmap_for_commit(old_bitmap, c);\n \t\t\t/*\n \t\t\t * If this commit has an old bitmap, then translate that\n \t\t\t * bitmap and add its bits to this one. No need to walk\n@@ -660,10 +667,7 @@ static int fill_bitmap_commit(struct bitmap_writer *writer,\n \t\t\tif (old && !rebuild_bitmap(mapping, old, remapped)) {\n \t\t\t\tbitmap_or(ent->bitmap, remapped);\n \t\t\t\tbitmap_free(remapped);\n-\t\t\t\tif (commit->object.flags & BITMAP_PSEUDO_MERGE)\n-\t\t\t\t\treused_pseudo_merge_bitmaps_nr++;\n-\t\t\t\telse\n-\t\t\t\t\treused_bitmaps_nr++;\n+\t\t\t\treused_bitmaps_nr++;\n \t\t\t\tcontinue;\n \t\t\t}\n \t\t\tbitmap_free(remapped);\n@@ -696,12 +700,32 @@ static int fill_bitmap_commit(struct bitmap_writer *writer,\n \t\t * walk ensures we cover all parents.\n \t\t */\n \t\tif (!(c->object.flags & BITMAP_PSEUDO_MERGE)) {\n+\t\t\tstruct tree *tree;\n+\n+\t\t\tif (from_pseudo_merge && !c->object.parsed) {\n+\t\t\t\t/*\n+\t\t\t\t * Commits reachable from selected\n+\t\t\t\t * non-pseudo-merges are already parsed\n+\t\t\t\t * by the regular bitmap build.\n+\t\t\t\t *\n+\t\t\t\t * However, pseudo-merge fills can also\n+\t\t\t\t * reach commits that were not covered\n+\t\t\t\t * there, so parse any such leftovers\n+\t\t\t\t * before reading their tree or parents.\n+\t\t\t\t */\n+\t\t\t\tif (repo_parse_commit(writer->repo, c))\n+\t\t\t\t\treturn -1;\n+\t\t\t}\n+\n \t\t\tpos = find_object_pos(writer, &c->object.oid, &found);\n \t\t\tif (!found)\n \t\t\t\treturn -1;\n \t\t\tbitmap_set(ent->bitmap, pos);\n-\t\t\tprio_queue_put(tree_queue,\n-\t\t\t\t repo_get_commit_tree(writer->repo, c));\n+\n+\t\t\ttree = repo_get_commit_tree(writer->repo, c);\n+\t\t\tif (!tree)\n+\t\t\t\treturn -1;\n+\t\t\tprio_queue_put(tree_queue, tree);\n \t\t}\n \n \t\tfor (p = c->parents; p; p = p->next) {\n@@ -738,6 +762,137 @@ static int fill_bitmap_commit(struct bitmap_writer *writer,\n \treturn 0;\n }\n \n+static int reuse_pseudo_merge_bitmap(struct bitmap_index *old_bitmap,\n+\t\t\t\t const uint32_t *mapping,\n+\t\t\t\t struct commit *merge,\n+\t\t\t\t struct ewah_bitmap **out)\n+{\n+\tstruct ewah_bitmap *old;\n+\tstruct bitmap *remapped;\n+\n+\tif (!old_bitmap || !mapping)\n+\t\treturn 0;\n+\n+\told = pseudo_merge_bitmap_for_commit(old_bitmap, merge);\n+\tif (!old)\n+\t\treturn 0;\n+\n+\tremapped = bitmap_new();\n+\tif (rebuild_bitmap(mapping, old, remapped) < 0) {\n+\t\tbitmap_free(remapped);\n+\t\treturn 0;\n+\t}\n+\n+\t*out = bitmap_to_ewah(remapped);\n+\tbitmap_free(remapped);\n+\treused_pseudo_merge_bitmaps_nr++;\n+\treturn 1;\n+}\n+\n+static int build_pseudo_merge_bitmap(struct bitmap_writer *writer,\n+\t\t\t\t struct bitmap_index *old_bitmap,\n+\t\t\t\t const uint32_t *mapping,\n+\t\t\t\t struct commit *merge,\n+\t\t\t\t struct ewah_bitmap **out)\n+{\n+\tstruct bb_commit ent = { 0 };\n+\tstruct prio_queue queue = { NULL };\n+\tstruct prio_queue tree_queue = { NULL };\n+\tunsigned parents = commit_list_count(merge->parents);\n+\tint ret;\n+\n+\tent.bitmap = bitmap_new();\n+\n+\tpseudo_merge_bitmap_nr++;\n+\tpseudo_merge_bitmap_parents += parents;\n+\n+\tif (reuse_pseudo_merge_bitmap(old_bitmap, mapping, merge, out)) {\n+\t\tret = 0;\n+\t\tgoto done;\n+\t}\n+\n+\tret = fill_bitmap_commit(writer, &ent, merge, &queue, &tree_queue,\n+\t\t\t\t old_bitmap, mapping);\n+\n+\tif (!ret)\n+\t\t*out = bitmap_to_ewah(ent.bitmap);\n+\n+done:\n+\tbitmap_free(ent.bitmap);\n+\tclear_prio_queue(&queue);\n+\tclear_prio_queue(&tree_queue);\n+\n+\treturn ret;\n+}\n+\n+static int build_pseudo_merge_bitmaps(struct bitmap_writer *writer,\n+\t\t\t\t struct bitmap_index *old_bitmap,\n+\t\t\t\t const uint32_t *mapping,\n+\t\t\t\t int *nr_stored)\n+{\n+\tsize_t i = bitmap_writer_nr_selected_commits(writer);\n+\tint ret = 0;\n+\n+\tif (!writer->pseudo_merges_nr)\n+\t\treturn 0;\n+\n+\ttrace2_region_enter(\"pack-bitmap-write\", \"building_pseudo_merge_bitmaps\",\n+\t\t\t writer->repo);\n+\n+\tfor (; i < writer->selected_nr; i++) {\n+\t\tstruct bitmapped_commit *merge = &writer->selected[i];\n+\t\tstruct commit_list *p;\n+\t\tstruct bitmap *parents = bitmap_new();\n+\t\tstruct ewah_bitmap *objects = NULL;\n+\n+\t\tif (!merge->pseudo_merge)\n+\t\t\tBUG(\"found non-pseudo merge commit at %\"PRIuMAX,\n+\t\t\t (uintmax_t)i);\n+\n+\t\tfor (p = merge->commit->parents; p; p = p->next) {\n+\t\t\tint found;\n+\t\t\tuint32_t pos = find_object_pos(writer,\n+\t\t\t\t\t\t &p->item->object.oid,\n+\t\t\t\t\t\t &found);\n+\t\t\tif (!found) {\n+\t\t\t\tbitmap_free(parents);\n+\t\t\t\tret = -1;\n+\t\t\t\tgoto done;\n+\t\t\t}\n+\t\t\tbitmap_set(parents, pos);\n+\t\t}\n+\n+\t\tmerge->pseudo_merge_parents = bitmap_to_ewah(parents);\n+\t\tbitmap_free(parents);\n+\n+\t\tif (build_pseudo_merge_bitmap(writer, old_bitmap, mapping,\n+\t\t\t\t\t merge->commit, &objects) < 0) {\n+\t\t\tret = -1;\n+\t\t\tgoto done;\n+\t\t}\n+\t\tmerge->bitmap = objects;\n+\n+\t\t(*nr_stored)++;\n+\t\tdisplay_progress(writer->progress, *nr_stored);\n+\t}\n+\n+done:\n+\ttrace2_region_leave(\"pack-bitmap-write\", \"building_pseudo_merge_bitmaps\",\n+\t\t\t writer->repo);\n+\n+\ttrace2_data_intmax(\"pack-bitmap-write\", writer->repo,\n+\t\t\t \"pseudo_merge_bitmap_nr\",\n+\t\t\t pseudo_merge_bitmap_nr);\n+\ttrace2_data_intmax(\"pack-bitmap-write\", writer->repo,\n+\t\t\t \"building_bitmaps_pseudo_merge_reused\",\n+\t\t\t reused_pseudo_merge_bitmaps_nr);\n+\ttrace2_data_intmax(\"pack-bitmap-write\", writer->repo,\n+\t\t\t \"pseudo_merge_bitmap_parents\",\n+\t\t\t pseudo_merge_bitmap_parents);\n+\n+\treturn ret;\n+}\n+\n static void store_selected(struct bitmap_writer *writer,\n \t\t\t struct bb_commit *ent, struct commit *commit)\n {\n@@ -821,6 +976,10 @@ int bitmap_writer_build(struct bitmap_writer *writer)\n \t\t\tbitmap_free(ent->bitmap);\n \t\tent->bitmap = NULL;\n \t}\n+\tif (closed &&\n+\t build_pseudo_merge_bitmaps(writer, old_bitmap, mapping,\n+\t\t\t\t &nr_stored) < 0)\n+\t\tclosed = 0;\n \tclear_prio_queue(&queue);\n \tclear_prio_queue(&tree_queue);\n \tbitmap_builder_clear(&bb);\n@@ -831,9 +990,6 @@ int bitmap_writer_build(struct bitmap_writer *writer)\n \t\t\t writer->repo);\n \ttrace2_data_intmax(\"pack-bitmap-write\", writer->repo,\n \t\t\t \"building_bitmaps_reused\", reused_bitmaps_nr);\n-\ttrace2_data_intmax(\"pack-bitmap-write\", writer->repo,\n-\t\t\t \"building_bitmaps_pseudo_merge_reused\",\n-\t\t\t reused_pseudo_merge_bitmaps_nr);\n \ttrace2_data_intmax(\"pack-bitmap-write\", writer->repo,\n \t\t\t \"fill_bitmap_commit_calls_nr\",\n \t\t\t fill_bitmap_commit_calls_nr);\n@@ -1015,23 +1171,6 @@ static void write_pseudo_merges(struct bitmap_writer *writer,\n \n \tCALLOC_ARRAY(pseudo_merge_ofs, writer->pseudo_merges_nr);\n \n-\tfor (i = 0; i < writer->pseudo_merges_nr; i++) {\n-\t\tstruct bitmapped_commit *merge = &writer->selected[base + i];\n-\t\tstruct commit_list *p;\n-\t\tstruct bitmap *parents = bitmap_new();\n-\n-\t\tif (!merge->pseudo_merge)\n-\t\t\tBUG(\"found non-pseudo merge commit at %\"PRIuMAX, (uintmax_t)i);\n-\n-\t\tfor (p = merge->commit->parents; p; p = p->next)\n-\t\t\tbitmap_set(parents,\n-\t\t\t\t find_object_pos(writer, &p->item->object.oid,\n-\t\t\t\t\t\t NULL));\n-\n-\t\tmerge->pseudo_merge_parents = bitmap_to_ewah(parents);\n-\t\tbitmap_free(parents);\n-\t}\n-\n \tstart = hashfile_total(f);\n \n \tfor (i = 0; i < writer->pseudo_merges_nr; i++) {\n@@ -1040,14 +1179,13 @@ static void write_pseudo_merges(struct bitmap_writer *writer,\n \t\tif (!merge->pseudo_merge)\n \t\t\tBUG(\"found non-pseudo merge commit at %\"PRIuMAX, (uintmax_t)i);\n \n-\t\tif (!merge->pseudo_merge_parents)\n-\t\t\tBUG(\"missing pseudo-merge parents bitmap for commit %s\",\n+\t\tif (!merge->pseudo_merge_parents || !merge->bitmap)\n+\t\t\tBUG(\"missing pseudo-merge bitmap for commit %s\",\n \t\t\t oid_to_hex(&merge->commit->object.oid));\n \n \t\tpseudo_merge_ofs[i] = hashfile_total(f);\n-\n \t\tdump_bitmap(f, merge->pseudo_merge_parents);\n-\t\tdump_bitmap(f, writer->selected[base+i].write_as);\n+\t\tdump_bitmap(f, merge->bitmap);\n \t}\n \n \tnext_ext = st_add(hashfile_total(f),\n-- \n2.54.0.rc1.84.g1cf18622df7\n"},{"id":"544257","messageId":"20260529060042.GA1106035@coredump.intra.peff.net","threadId":"65661","inReplyTo":"ahcCX+xAKFOL8HcW@nand.local","subject":"Re: [PATCH 3/8] pack-bitmap: reuse stored selected bitmaps","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2026-05-29T06:00:42Z","receivedAt":"2026-05-29T06:00:43Z","isPatch":true,"body":"On Wed, May 27, 2026 at 10:40:31AM -0400, Taylor Blau wrote:\n\n> > > Teach `fill_bitmap_commit()` to notice that case. For non-root commits in\n> > > the walk, look for a stored selected bitmap and OR it into the bitmap\n> > > being built. If one exists, skip the commit, its tree, and its parents.\n> >\n> > I feel like this _shouldn't_ be necessary, because the idea of the\n> > current writing code is to go from the roots up, following inverted\n> > parent pointers, and passing the bitmap up as we go. So whenever we\n> > visit a commit we should in theory have all of the ancestor's bits set\n> > in that bitmap. But I remember that the simple-and-stupid approach ended\n> > up being too memory hungry, so we pick some focal points in the graph\n> > and then fill them independently.\n> \n> It's sharing within the non-first parent history that is killing us\n> here. I think what you said is true in a completely linear repository\n> with no merges. But since we only pass commit masks from commits to\n> their first parents, we don't reuse any already-generated bitmaps for\n> common points in history not shared between commits' first parents.\n\nAh, that makes sense. I had forgotten exactly how the maximal-commit\nselection worked, and what we compromised versus the original naive\n\"build from the bottom up\" strategy.\n\n> Yeah, these were for my own curiosity as much as anything. I had written\n> them as a temporary measure in order to write the \"[...] there are 1,261\n> commits selected for bitmap coverage, and 1,382 maximal commits induced\n> [...]\" portion of the commit message above.\n> \n> Once I had written it, I found the result useful enough to keep around.\n\nMakes sense. It might help us (or even some very clueful user) debug or\nfine-tune parameters down the road.\n\n-Peff\n"},{"id":"544260","messageId":"20260529082622.GB1106035@coredump.intra.peff.net","threadId":"65661","inReplyTo":"ahciIDuESxNa9Fzn@nand.local","subject":"Re: [PATCH 6/8] pack-bitmap: sort bitmaps before XORing","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2026-05-29T08:26:22Z","receivedAt":"2026-05-29T08:26:24Z","isPatch":true,"body":"On Wed, May 27, 2026 at 12:56:00PM -0400, Taylor Blau wrote:\n\n> > If you have some spare CPU cycles to burn, I would be interested in a\n> > comparison of the bitmap size of your test repo using v2.30.0, v2.31.1,\n> > and this patch.\n> \n> I started running this experiment, but I don't think I actually have\n> enough CPU cycles to let it finish ;-). Pre-v2.31 bitmap generation is\n> *really* slow[^1], and after multiple hours (forcing the same selection\n> of bitmaps by back-porting and adjusting 'test-tool bitmap') I couldn't\n> seem to make any meaningful progress.\n\nOof. I forgot just how slow it could be. Thanks for trying.\n\n> I'm sure that you could get some plausible numbers out of benchmarking\n> this on a smaller repository. In case you're interested, here's the\n> patch I wrote on top of v2.30.0:\n\nI tried it myself on linux.git, which is the biggest repo I usually have\non hand. But it seemed to generate the same size back then, and now, and\nafter your xor-sorting patch. I'm not sure what's different between that\nand your super-big test case. Maybe just the number of bitmaps? Maybe\ngraph structure causing weird order of selection?\n\nI grabbed chromium.git (63GB!) and tried that, too. Its bitmap size\nshrinks a tiny bit with this patch (143MB to 140MB). So some\nimprovement, but not enough of an effect for me to slog through a v2.30\nbitmap build just to see if things changed back then.\n\nRegardless of whether the issue was introduced there, or was always\nlurking, I think the sort order introduced by this patch is the right\nthing to do.\n\n> > Certainly good numbers. The obvious follow-up question is: how does the\n> > reading side fare? I'd expect it to be a little better, if only because\n> > there are fewer bytes to consider when XOR-ing. But if there's some\n> > hidden assumption we're missing, then it could get wildly worse. It\n> > would be good to confirm that that didn't happen. ;)\n> \n> It doesn't make a huge difference. Prior to this patch, the timings on\n> my test repository for 'git rev-list --count --all --objects\n> --use-bitmap-index' go from:\n\nOK, good. I wasn't expecting great things, but just wanted to double\ncheck that bad things did not appear.\n\n-Peff\n"},{"id":"544261","messageId":"20260529083337.GC1106035@coredump.intra.peff.net","threadId":"65661","inReplyTo":"ahdE+Je5YK9JoE7B@nand.local","subject":"Re: [PATCH 8/8] pack-bitmap: build pseudo-merge bitmaps after regular bitmaps","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2026-05-29T08:33:37Z","receivedAt":"2026-05-29T08:33:38Z","isPatch":true,"body":"On Wed, May 27, 2026 at 03:24:40PM -0400, Taylor Blau wrote:\n\n> Below are some numbers that give you a sense of how the runtime scales\n> with the number of pseudo-merges. I'm relying exclusively on \"stable\"\n> pseudo-merges here since they have more predictable bucketing behavior,\n> though note that there isn't an exact way to dial in the number of these\n> so-called \"stable\" pseudo-merge groups. We can only control their *size*\n> (in terms of number of parents), so I ran the harness which produced the\n> above code with powers of 10 between [10^3, 10^6].\n> \n> Results are as follows:\n> \n> +------------+-------+----------+\n> | stableSize | count | time (s) |\n> +------------+-------+----------+\n> | 1000000 | 1 | 34.963 |\n> | 100000 | 3 | 36.954 |\n> | 10000 | 26 | 221.963 |\n> | 1000 | 252 | 2779.373 |\n> +------------+-------+----------+\n> \n> Which scales roughly like O(x^1.165) (the best fit function I could find\n> was t(n) = 25.18 + 4.386 * n^1.165, where 'n' is the number of\n> pseudo-merges, and t(n) is the time it took to generate them).\n> \n> So it does grow faster than linearly, but it's not too bad. The jump\n> from 26 to 252 pseudo-merges is pretty significant, though, but having\n> that many pseudo-merges is probably not something that we would want to\n> do in practice.\n\nOK, that matches my intuition. 1.165 is close enough that I can squint\nand call it linear. ;) I agree that probably you'd want to target a\ndozen or fewer pseudo-merges. In the long run we might be able to\nauto-tune this a bit, or at the very least document the tradeoffs and\nexpectations. But think that can only come after getting some more\nreal-world experience. For all we know the feature might not help at all\nin the real world, since any grouping strategy will be highly dependent\non heuristics about how refs are updated, what queries look like, and so\non.\n\nNot that I'm not optimistic, just that I think it is too soon to try\nwriting this stuff up.\n\n-Peff\n"},{"id":"544262","messageId":"20260529083439.GD1106035@coredump.intra.peff.net","threadId":"65661","inReplyTo":"cover.1779911733.git.me@ttaylorr.com","subject":"Re: [PATCH v2 0/8] pack-bitmap-write: speed up bitmap generation","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2026-05-29T08:34:39Z","receivedAt":"2026-05-29T08:34:40Z","isPatch":true,"body":"On Wed, May 27, 2026 at 03:55:44PM -0400, Taylor Blau wrote:\n\n> Here is a reroll of my series to improve the performance of reachability\n> bitmap generation, focusing on very large repositories and the penalty\n> to generate pseudo-merge reachability bitmaps.\n> \n> The series is largely unchanged since last time. Notable changes in this\n> round include:\n> \n> - minor refactoring in the pair of patches which consolidate the\n> `find_object_pos()` success path and introduce the object position\n> cache during bitmap fills, and\n> \n> - dropping a stale paragraph from the final patch's message, which\n> described follow-up commits that are no longer part of this series.\n\nThanks, this version looks good to me.\n\n-Peff\n"}]}