{"thread":{"id":"65704","subject":"[PATCH 0/3] pack-objects: support bitmaps and delta-islands with `--path-walk`","startedAt":"2026-05-27T23:18:37Z","lastAt":"2026-06-22T16:26:31Z","messageCount":33,"participants":["Taylor Blau","Derrick Stolee","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":3},"messages":[{"id":"544195","messageId":"cover.1779923907.git.me@ttaylorr.com","threadId":"65704","inReplyTo":null,"subject":"[PATCH 0/3] pack-objects: support bitmaps and delta-islands with `--path-walk`","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2026-05-27T23:18:34Z","receivedAt":"2026-05-27T23:18:37Z","isPatch":true,"body":"Note to the maintainer:\n\n * This series is based on 'ds/path-walk-filters' with Patrick's\n 'ps/clang-w-glibc-2.43-and-_Generic' merged in. The former has since\n graduated. These are the three remaining patches from my earlier RFC\n after Stolee's series incorporated the filter-related pieces.\n\nHere is a trimmed-down reroll of my series to make `--path-walk` work\nwith reachability bitmaps and delta-islands. This series was originally\nan RFC that was a companion to Stolee's recent patches to extend\n`--filter` support to `--path-walk` [1].\n\nSince the previous round, Stolee's series has graduated and incorporated\nthe filter-related patches from my earlier RFC [2]. What remains are the\nthree patches here that implement support for reachability bitmaps and\ndelta-islands under `--path-walk`.\n\n * The first patch allows `--path-walk` to use reachability bitmaps when\n they can answer the request, falling back to path-walk enumeration\n when they cannot. It also lets bitmap writing see the same commit\n candidates that the regular traversal would have shown to the bitmap\n selector.\n\n * The second patch is preparatory, and factors the\n delta-islands-specific tree-depth recording from `show_object()` into\n a helper.\n\n * The final patch teaches the path-walk callback to perform the same\n delta-islands side effects as the regular traversal: propagating\n island marks for commits, and recording tree depths for trees. This\n gives `resolve_tree_islands()` the same input in either enumeration\n mode, so the existing island checks can be reused unchanged.\n\nThanks in advance for your review!\n\n[1]: https://lore.kernel.org/git/pull.2101.git.1777731354.gitgitgadget@gmail.com/\n[2]: https://lore.kernel.org/git/cover.1777853408.git.me@ttaylorr.com/\n\nTaylor Blau (3):\n pack-objects: support reachability bitmaps with `--path-walk`\n pack-objects: extract `record_tree_depth()` helper\n pack-objects: support `--delta-islands` with `--path-walk`\n\n Documentation/git-pack-objects.adoc | 12 ++---\n builtin/pack-objects.c | 68 +++++++++++++++++++++--------\n t/t5310-pack-bitmaps.sh | 36 +++++++++++++++\n t/t5320-delta-islands.sh | 29 ++++++++++++\n 4 files changed, 122 insertions(+), 23 deletions(-)\n\n\nbase-commit: 45a9ecee26839cc880fdd5e704339dd3cf4ffc26\n-- \n2.54.0.22.ga642305e3c9\n"},{"id":"544196","messageId":"3fa8bfbfd59f5e287e516ed272cad0ef2230aa93.1779923907.git.me@ttaylorr.com","threadId":"65704","inReplyTo":"cover.1779923907.git.me@ttaylorr.com","subject":"[PATCH 1/3] pack-objects: support reachability bitmaps with `--path-walk`","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2026-05-27T23:18:38Z","receivedAt":"2026-05-27T23:18:40Z","isPatch":true,"body":"When 'pack-objects' is invoked with '--path-walk', it prevents us from\nusing reachability bitmaps.\n\nThis behavior dates back to 70664d2865c (pack-objects: add --path-walk\noption, 2025-05-16), which included a comment in the relevant portion of\nthe command-line arguments handling that read as follows:\n\n /*\n * We must disable the bitmaps because we are removing\n * the --objects / --objects-edge[-aggressive] options.\n */\n\nIn fb2c309b7d3 (pack-objects: pass --objects with --path-walk,\n2026-05-02), path-walk learned to pass '--objects' again, but still\nkept bitmap traversal disabled. That leaves two useful cases\nunsupported:\n\n * A path-walk repack that writes bitmaps does not give the bitmap\n selector any commits, because path-walk reveals commits through\n `add_objects_by_path()` rather than through `show_commit()`, where\n `index_commit_for_bitmap()` is normally called.\n\n * An invocation like \"git pack-objects --use-bitmap-index --path-walk\"\n never tries an existing bitmap, even when one is available and could\n answer the request.\n\nFortunately for us, neither restriction is required.\n\n * On the writing side: teach the path-walk object callback to call\n `index_commit_for_bitmap()` for commits that it adds to the pack.\n That gives the bitmap selector the commit candidates it would have\n seen from the regular traversal.\n\n * For bitmap reading, keep passing '--objects' to the internal rev_list\n machinery, but stop clearing `use_bitmap_index`. If an existing\n bitmap can answer the request, use it; otherwise fall back to\n path-walk's own enumeration.\n\nThere is one wrinkle when it comes to '--boundary', which we must not\npass into the bitmap walk in the presence of both '--path-walk' and\n'--use-bitmap-index'. Path-walk needs boundary commits when it performs\nits own traversal, in order to discover bases for thin packs, but the\nbitmap traversal expects the usual non-boundary state. Work around this\nby setting `revs->boundary` as late as possible within\n`get_object_list_path_walk()`, after any bitmap attempt has either\nsucceeded or declined to answer the request.\n\nSigned-off-by: Taylor Blau \n---\n Documentation/git-pack-objects.adoc | 6 +++--\n builtin/pack-objects.c | 18 +++++++++++++--\n t/t5310-pack-bitmaps.sh | 36 +++++++++++++++++++++++++++++\n 3 files changed, 56 insertions(+), 4 deletions(-)\n\ndiff --git a/Documentation/git-pack-objects.adoc b/Documentation/git-pack-objects.adoc\nindex 8a27aa19fd3..0adce8961a3 100644\n--- a/Documentation/git-pack-objects.adoc\n+++ b/Documentation/git-pack-objects.adoc\n@@ -402,8 +402,10 @@ will be automatically changed to version `1`.\n \tof filenames that cause collisions in Git's default name-hash\n \talgorithm.\n +\n-Incompatible with `--delta-islands`. The `--use-bitmap-index` option is\n-ignored in the presence of `--path-walk`. The `--path-walk` option\n+Incompatible with `--delta-islands`. When `--use-bitmap-index` is\n+specified with `--path-walk`, a successful bitmap traversal is used for\n+object enumeration, with path-walk remaining as the fallback traversal\n+when the bitmap cannot satisfy the request. The `--path-walk` option\n supports the `--filter=` forms `blob:none`, `blob:limit=`,\n `tree:0`, `object:type=`, and `sparse:`. These supported filter\n types can be combined with the `combine:+` form.\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex b783dc62bc9..e4dcb563b7d 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -4732,6 +4732,15 @@ static int add_objects_by_path(const char *path,\n \t\t\tcontinue;\n \n \t\tadd_object_entry(oid, type, path, exclude);\n+\n+\t\tif (type == OBJ_COMMIT && write_bitmap_index) {\n+\t\t\tstruct commit *commit;\n+\n+\t\t\tcommit = lookup_commit(the_repository, oid);\n+\t\t\tif (!commit)\n+\t\t\t\tdie(_(\"could not find commit %s\"), oid_to_hex(oid));\n+\t\t\tindex_commit_for_bitmap(commit);\n+\t\t}\n \t}\n \n \toe_end = to_pack.nr_objects;\n@@ -4764,6 +4773,13 @@ static int get_object_list_path_walk(struct rev_info *revs)\n \tinfo.path_fn = add_objects_by_path;\n \tinfo.path_fn_data = &processed;\n \n+\t/*\n+\t * Path-walk needs boundary commits to discover thin-pack bases, but\n+\t * bitmap traversal does not understand the boundary state. Set it\n+\t * here so any prior bitmap attempt sees the usual non-boundary walk.\n+\t */\n+\trevs->boundary = 1;\n+\n \t/*\n \t * Allow the --[no-]sparse option to be interesting here, if only\n \t * for testing purposes. Paths with no interesting objects will not\n@@ -5195,9 +5211,7 @@ int cmd_pack_objects(int argc,\n \t\t}\n \t}\n \tif (path_walk) {\n-\t\tstrvec_push(&rp, \"--boundary\");\n \t\tstrvec_push(&rp, \"--objects\");\n-\t\tuse_bitmap_index = 0;\n \t} else if (thin) {\n \t\tuse_internal_rev_list = 1;\n \t\tstrvec_push(&rp, shallow\ndiff --git a/t/t5310-pack-bitmaps.sh b/t/t5310-pack-bitmaps.sh\nindex f693cb56691..69c5da1580a 100755\n--- a/t/t5310-pack-bitmaps.sh\n+++ b/t/t5310-pack-bitmaps.sh\n@@ -577,6 +577,42 @@ test_bitmap_cases\n \n sane_unset GIT_TEST_PACK_USE_BITMAP_BOUNDARY_TRAVERSAL\n \n+test_expect_success 'path-walk repack can write and use bitmap indexes' '\n+\ttest_when_finished \"rm -rf path-walk-bitmap\" &&\n+\tgit init path-walk-bitmap &&\n+\t(\n+\t\tcd path-walk-bitmap &&\n+\t\ttest_commit first &&\n+\t\ttest_commit second &&\n+\t\ttest_commit third &&\n+\n+\t\tgit repack -a -d -b --path-walk &&\n+\t\tgit rev-list --test-bitmap --use-bitmap-index HEAD &&\n+\n+\t\tgit rev-parse HEAD >in &&\n+\n+\t\tgit rev-list --objects --no-object-names HEAD >expect.raw &&\n+\t\tsort expect.raw >expect &&\n+\n+\t\tfor reuse in true false\n+\t\tdo\n+\t\t\t: >trace.txt &&\n+\n+\t\t\tGIT_TRACE2_EVENT=\"$(pwd)/trace.txt\" \\\n+\t\t\tgit -c pack.allowPackReuse=$reuse pack-objects \\\n+\t\t\t\t--stdout --revs --path-walk --use-bitmap-index \\\n+\t\t\t\tout.pack &&\n+\t\t\tgrep \"\\\"category\\\":\\\"bitmap\\\",\\\"key\\\":\\\"bitmap/hits\\\"\" trace.txt &&\n+\n+\t\t\tgit index-pack out.pack &&\n+\n+\t\t\tlist_packed_objects out.idx >actual.raw &&\n+\t\t\tsort actual.raw >actual &&\n+\t\t\ttest_cmp expect actual || return 1\n+\t\tdone\n+\t)\n+'\n+\n test_expect_success 'incremental repack fails when bitmaps are requested' '\n \ttest_commit more-1 &&\n \ttest_must_fail git repack -d 2>err &&\n-- \n2.54.0.22.ga642305e3c9\n\n"},{"id":"544197","messageId":"bdae873eaab71ac7973dd8bec2e276e8f0fede75.1779923907.git.me@ttaylorr.com","threadId":"65704","inReplyTo":"cover.1779923907.git.me@ttaylorr.com","subject":"[PATCH 2/3] pack-objects: extract `record_tree_depth()` helper","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2026-05-27T23:18:41Z","receivedAt":"2026-05-27T23:18:43Z","isPatch":true,"body":"Prepare for a subsequent change that needs to record tree depths from a\nsecond call site by factoring the delta-islands tree-depth bookkeeping\nout of `show_object()` and into a helper, `record_tree_depth()`.\n\nThe helper looks up the object in `to_pack`, returns early when the\nobject was not added there, computes the depth from the slash count in\nthe supplied name, and preserves the existing max-depth-wins behavior\nwhen a tree is reached by more than one path.\n\nSigned-off-by: Taylor Blau \n---\n builtin/pack-objects.c | 32 ++++++++++++++++++--------------\n 1 file changed, 18 insertions(+), 14 deletions(-)\n\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex e4dcb563b7d..ec02e2b21d2 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -2722,6 +2722,22 @@ static inline void oe_set_tree_depth(struct packing_data *pack,\n \tpack->tree_depth[e - pack->objects] = tree_depth;\n }\n \n+static void record_tree_depth(const struct object_id *oid, const char *name)\n+{\n+\tconst char *p;\n+\tunsigned depth;\n+\tstruct object_entry *ent;\n+\n+\t/* the empty string is a root tree, which is depth 0 */\n+\tdepth = *name ? 1 : 0;\n+\tfor (p = strchr(name, '/'); p; p = strchr(p + 1, '/'))\n+\t\tdepth++;\n+\n+\tent = packlist_find(&to_pack, oid);\n+\tif (ent && depth > oe_tree_depth(&to_pack, ent))\n+\t\toe_set_tree_depth(&to_pack, ent, depth);\n+}\n+\n /*\n * Return the size of the object without doing any delta\n * reconstruction (so non-deltas are true object sizes, but deltas\n@@ -4375,20 +4391,8 @@ static void show_object(struct object *obj, const char *name,\n \tadd_preferred_base_object(name);\n \tadd_object_entry(&obj->oid, obj->type, name, 0);\n \n-\tif (use_delta_islands) {\n-\t\tconst char *p;\n-\t\tunsigned depth;\n-\t\tstruct object_entry *ent;\n-\n-\t\t/* the empty string is a root tree, which is depth 0 */\n-\t\tdepth = *name ? 1 : 0;\n-\t\tfor (p = strchr(name, '/'); p; p = strchr(p + 1, '/'))\n-\t\t\tdepth++;\n-\n-\t\tent = packlist_find(&to_pack, &obj->oid);\n-\t\tif (ent && depth > oe_tree_depth(&to_pack, ent))\n-\t\t\toe_set_tree_depth(&to_pack, ent, depth);\n-\t}\n+\tif (use_delta_islands)\n+\t\trecord_tree_depth(&obj->oid, name);\n }\n \n static void show_object__ma_allow_any(struct object *obj, const char *name, void *data)\n-- \n2.54.0.22.ga642305e3c9\n\n"},{"id":"544198","messageId":"a642305e3c9d089c539e1c52b89c417ab3dda498.1779923907.git.me@ttaylorr.com","threadId":"65704","inReplyTo":"cover.1779923907.git.me@ttaylorr.com","subject":"[PATCH 3/3] pack-objects: support `--delta-islands` with `--path-walk`","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2026-05-27T23:18:44Z","receivedAt":"2026-05-27T23:18:46Z","isPatch":true,"body":"Since the inception of `--path-walk`, this option has had a documented\nincompatibility with `--delta-islands`.\n\nWhen discussing those original patches on the list, a message from\nStolee in [1] noted the following:\n\n this could be remedied by [...] doing a separate walk to identify\n islands using the normal method\n\nIn a related portion of the thread, Peff explains[2]:\n\n The delta islands code already does its own tree walk to propagate\n the bits down (it does rely on the base walk's show_commit() to\n propagate through the commits).\n\n Once each object has its island bitmaps, I think however you\n choose to come up with delta candidates [...] you should be able\n to use it. It's fundamentally just answering the question of \"am\n I allowed to delta between these two objects\".\n\nThat is similar to what this patch does, and it turns out the cheaper\noption is sufficient: perform the same island side effects from the\npath-walk callback rather than doing a second walk.\n\nRecall how delta-islands are computed during a normal repack:\n\n - `show_commit()` calls `propagate_island_marks()` for each commit,\n which merges the commit's island bitset onto its root tree object and\n onto each of its parent commits.\n\n - `show_object()` for a tree records the tree's depth derived from the\n slash-separated pathname. Subsequent `resolve_tree_islands()` uses\n that depth to walk trees in increasing-depth order, propagating each\n tree's marks to its children.\n\n - At delta-search time, `in_same_island()` enforces that a delta\n target's island bitmap is a subset of its base's: every island that\n reaches the target must also reach the base.\n\nPath-walk's enumeration callback is `add_objects_by_path()`. It already\nadds objects to `to_pack`, but until now did not perform the\nisland-related side effects. Two things are needed:\n\n - For each commit batch, call `propagate_island_marks()` on commits,\n exactly as `show_commit()` does.\n\n We have to be careful about the order in which we call this function,\n and we must see a commit before its parents in order to have\n island marks to propagate.\n\n The path-walk batch preserves that order. Path-walk appends commits\n to its `OBJ_COMMIT` batch as they come back from the same\n `get_revision()` loop the regular traversal uses, and\n `add_objects_by_path()` iterates the batch in array order. So every\n commit reaches `propagate_island_marks()` in the same sequence that\n `show_commit()` would have seen it, and the descendant-first chain\n that the algorithm relies on is intact.\n\n Skip island propagation for excluded commits to match the regular\n traversal, whose `show_commit()` callback is only invoked for\n interesting commits. Boundary commits may still be present in\n path-walk's callback so they can serve as thin-pack bases, but they\n should not contribute island marks.\n\n - For each tree batch, record the tree's depth from the path. Use the\n `record_tree_depth()` helper from the previous commit so both\n callbacks behave identically, including the max-depth-wins behavior\n when a tree is reached via more than one path. The helper accepts\n both the `show_object()` path shape (\"foo\", \"foo/bar\") and the\n path-walk shape with a trailing slash (\"foo/\", \"foo/bar/\"), so depths\n recorded from either traversal mode are directly comparable.\n\n This is implicit in the implementation sketch from Peff above.\n `resolve_tree_islands()` sorts trees by `oe->tree_depth` in\n increasing-depth order before propagating marks down, so that a\n parent tree's marks are finalized before its children inherit them.\n Without recording the depth at path-walk time, every\n path-walk-discovered tree would land at depth 0 in `to_pack`, the\n sort would lose its ordering, and children could inherit marks from\n parents whose own contributions had not yet been merged in.\n\nWith those two pieces in place, `resolve_tree_islands()` receives the\nsame island inputs from path-walk as it would from the regular\ntraversal, so the existing island checks can be reused unchanged.\n\nDrop the documented incompatibility between `--path-walk` and\n`--delta-islands`, and add t5320 coverage for path-walk island repacks\nwith and without bitmap writing, as well as the same-island case where a\ndelta remains allowed.\n\n[1]: https://lore.kernel.org/git/9aa2471b-0850-4707-9733-d3b33609f5f2@gmail.com/\n[2]: https://lore.kernel.org/git/20240911063203.GA1538586@coredump.intra.peff.net/\n\nSigned-off-by: Taylor Blau \n---\n Documentation/git-pack-objects.adoc | 14 +++++++-------\n builtin/pack-objects.c | 22 ++++++++++++++++++----\n t/t5320-delta-islands.sh | 29 +++++++++++++++++++++++++++++\n 3 files changed, 54 insertions(+), 11 deletions(-)\n\ndiff --git a/Documentation/git-pack-objects.adoc b/Documentation/git-pack-objects.adoc\nindex 0adce8961a3..65cd00c152f 100644\n--- a/Documentation/git-pack-objects.adoc\n+++ b/Documentation/git-pack-objects.adoc\n@@ -402,13 +402,13 @@ will be automatically changed to version `1`.\n \tof filenames that cause collisions in Git's default name-hash\n \talgorithm.\n +\n-Incompatible with `--delta-islands`. When `--use-bitmap-index` is\n-specified with `--path-walk`, a successful bitmap traversal is used for\n-object enumeration, with path-walk remaining as the fallback traversal\n-when the bitmap cannot satisfy the request. The `--path-walk` option\n-supports the `--filter=` forms `blob:none`, `blob:limit=`,\n-`tree:0`, `object:type=`, and `sparse:`. These supported filter\n-types can be combined with the `combine:+` form.\n+When `--use-bitmap-index` is specified with `--path-walk`, a successful\n+bitmap traversal is used for object enumeration, with path-walk\n+remaining as the fallback traversal when the bitmap cannot satisfy the\n+request. The `--path-walk` option supports the `--filter=` forms\n+`blob:none`, `blob:limit=`, `tree:0`, `object:type=`, and\n+`sparse:`. These supported filter types can be combined with the\n+`combine:+` form.\n \n \n DELTA ISLANDS\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex ec02e2b21d2..f48ea7a888b 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -4737,13 +4737,29 @@ static int add_objects_by_path(const char *path,\n \n \t\tadd_object_entry(oid, type, path, exclude);\n \n-\t\tif (type == OBJ_COMMIT && write_bitmap_index) {\n+\t\tif (type == OBJ_COMMIT) {\n \t\t\tstruct commit *commit;\n \n+\t\t\tif (!write_bitmap_index && !use_delta_islands)\n+\t\t\t\tcontinue;\n+\n \t\t\tcommit = lookup_commit(the_repository, oid);\n \t\t\tif (!commit)\n \t\t\t\tdie(_(\"could not find commit %s\"), oid_to_hex(oid));\n-\t\t\tindex_commit_for_bitmap(commit);\n+\t\t\tif (write_bitmap_index)\n+\t\t\t\tindex_commit_for_bitmap(commit);\n+\t\t\t/*\n+\t\t\t * Skip island propagation for boundary commits.\n+\t\t\t * The regular traversal's show_commit() is only\n+\t\t\t * called for interesting commits; matching that\n+\t\t\t * here keeps path-walk from doing extra work that\n+\t\t\t * would only be a no-op anyway (boundary commits\n+\t\t\t * are not in island_marks).\n+\t\t\t */\n+\t\t\tif (use_delta_islands && !exclude)\n+\t\t\t\tpropagate_island_marks(the_repository, commit);\n+\t\t} else if (type == OBJ_TREE && use_delta_islands) {\n+\t\t\trecord_tree_depth(oid, path);\n \t\t}\n \t}\n \n@@ -5205,8 +5221,6 @@ int cmd_pack_objects(int argc,\n \t\tconst char *option = NULL;\n \t\tif (!path_walk_filter_compatible(&filter_options))\n \t\t\toption = \"--filter\";\n-\t\telse if (use_delta_islands)\n-\t\t\toption = \"--delta-islands\";\n \n \t\tif (option) {\n \t\t\twarning(_(\"cannot use %s with %s\"),\ndiff --git a/t/t5320-delta-islands.sh b/t/t5320-delta-islands.sh\nindex 2c961c70963..9b28344a0a3 100755\n--- a/t/t5320-delta-islands.sh\n+++ b/t/t5320-delta-islands.sh\n@@ -53,6 +53,35 @@ test_expect_success 'separate islands disallows delta' '\n \t! is_delta_base $two $one\n '\n \n+test_expect_success 'path-walk island repack respects islands' '\n+\tGIT_TRACE2_EVENT=\"$(pwd)/trace.path-walk-islands\" \\\n+\t\tgit -c \"pack.island=refs/heads/(.*)\" repack -adfi \\\n+\t\t--path-walk 2>err &&\n+\ttest_region pack-objects path-walk trace.path-walk-islands &&\n+\ttest_grep ! \"cannot use --delta-islands with --path-walk\" err &&\n+\t! is_delta_base $one $two &&\n+\t! is_delta_base $two $one\n+'\n+\n+test_expect_success 'path-walk island bitmap repack respects islands' '\n+\tGIT_TRACE2_EVENT=\"$(pwd)/trace.path-walk-island-bitmap\" \\\n+\t\tgit -c \"pack.island=refs/heads/(.*)\" repack -a -d -f -i -b \\\n+\t\t--path-walk 2>err &&\n+\ttest_region pack-objects path-walk trace.path-walk-island-bitmap &&\n+\ttest_path_is_file .git/objects/pack/*.bitmap &&\n+\tgit rev-list --test-bitmap --use-bitmap-index one &&\n+\ttest_grep ! \"cannot use --delta-islands with --path-walk\" err &&\n+\t! is_delta_base $one $two &&\n+\t! is_delta_base $two $one\n+'\n+\n+test_expect_success 'path-walk same island allows delta' '\n+\tGIT_TRACE2_EVENT=\"$(pwd)/trace.path-walk-same-island\" \\\n+\t\tgit -c \"pack.island=refs/heads\" repack -adfi --path-walk &&\n+\ttest_region pack-objects path-walk trace.path-walk-same-island &&\n+\tis_delta_base $one $two\n+'\n+\n test_expect_success 'same island allows delta' '\n \tgit -c \"pack.island=refs/heads\" repack -adfi &&\n \tis_delta_base $one $two\n-- \n2.54.0.22.ga642305e3c9\n"},{"id":"544229","messageId":"a708e23d-e0c2-48c9-86e9-1227f12edd53@gmail.com","threadId":"65704","inReplyTo":"cover.1779923907.git.me@ttaylorr.com","subject":"Re: [PATCH 0/3] pack-objects: support bitmaps and delta-islands with `--path-walk`","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2026-05-28T15:28:55Z","receivedAt":"2026-05-28T15:28:56Z","isPatch":true,"body":"On 5/27/26 7:18 PM, Taylor Blau wrote:\n\n> Here is a trimmed-down reroll of my series to make `--path-walk` work\n> with reachability bitmaps and delta-islands. This series was originally\n> an RFC that was a companion to Stolee's recent patches to extend\n> `--filter` support to `--path-walk` [1].\n> \n> Since the previous round, Stolee's series has graduated and incorporated\n> the filter-related patches from my earlier RFC [2]. What remains are the\n> three patches here that implement support for reachability bitmaps and\n> delta-islands under `--path-walk`.\n> \n> * The first patch allows `--path-walk` to use reachability bitmaps when\n> they can answer the request, falling back to path-walk enumeration\n> when they cannot. It also lets bitmap writing see the same commit\n> candidates that the regular traversal would have shown to the bitmap\n> selector.\n> \n> * The second patch is preparatory, and factors the\n> delta-islands-specific tree-depth recording from `show_object()` into\n> a helper.\n> \n> * The final patch teaches the path-walk callback to perform the same\n> delta-islands side effects as the regular traversal: propagating\n> island marks for commits, and recording tree depths for trees. This\n> gives `resolve_tree_islands()` the same input in either enumeration\n> mode, so the existing island checks can be reused unchanged.\n\nI've applied these patches locally and confirmed that each one passes the\ntest suite with GIT_TEST_PACK_PATH_WALK=1, which helps to confirm that\nthe changes are correct (all existing bitmap tests create and use the\nbitmaps with --path-walk unless explicitly disabled).\n\nShould we add GIT_TEST_PACK_PATH_WALK=1 to the test-var CI build, now\nthat this is going to be more commonly used?\n\nDo you have any end-to-end performance data to demonstrate that these\nchanges are effective at scale? Are we still producing packfiles with the\npack-file compression and now with .bitmap files? How does this impact\nthe performance of a clone or fetch when using a bitmap index at read\ntime?\n\nWith that in mind, should we update any t/perf/ test to cover some of\nthese scenarios? I'm running a few with GIT_TEST_PACK_PATH_WALK=1 on\nmy laptop as a test, but it's taking a while. If you have stats ready\nfrom your local testing, then that would be interesting.\n\nThanks,\n-Stolee\n\n"},{"id":"544276","messageId":"22a7e32f-f645-4f00-bc5b-6b4309e483c2@gmail.com","threadId":"65704","inReplyTo":"a708e23d-e0c2-48c9-86e9-1227f12edd53@gmail.com","subject":"Re: [PATCH 0/3] pack-objects: support bitmaps and delta-islands with `--path-walk`","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2026-05-29T17:26:33Z","receivedAt":"2026-05-29T17:26:35Z","isPatch":true,"body":"On 5/28/26 11:28 AM, Derrick Stolee wrote:\n> On 5/27/26 7:18 PM, Taylor Blau wrote:\n\n> Do you have any end-to-end performance data to demonstrate that these\n> changes are effective at scale? Are we still producing packfiles with the\n> pack-file compression and now with .bitmap files? How does this impact\n> the performance of a clone or fetch when using a bitmap index at read\n> time?\n\nHere's my attempt to use our existing performance tests to analyze the\nimpact of this series.\n\nRunning p5311 against the base of this topic and this topic with\nGIT_TEST_PACK_PATH_WALK=1, I get this output:\n\nTest HEAD~3 HEAD\n-----------------------------------------------------------------\n5311.4: server (1 days) (lookup=true) 0.02 0.03 +50.0%\n5311.5: size (1 days) 6.8K 124.9K +1730.9%\n5311.6: client (1 days) (lookup=true) 0.02 0.01 -50.0%\n5311.8: server (2 days) (lookup=true) 0.02 0.03 +50.0%\n5311.9: size (2 days) 6.8K 124.9K +1730.9%\n5311.10: client (2 days) (lookup=true) 0.02 0.01 -50.0%\n5311.12: server (4 days) (lookup=true) 0.02 0.03 +50.0%\n5311.13: size (4 days) 6.8K 124.9K +1730.9%\n5311.14: client (4 days) (lookup=true) 0.02 0.01 -50.0%\n5311.16: server (8 days) (lookup=true) 0.03 0.03 +0.0%\n5311.17: size (8 days) 37.3K 186.0K +398.2%\n5311.18: client (8 days) (lookup=true) 0.03 0.02 -33.3%\n5311.20: server (16 days) (lookup=true) 0.02 0.03 +50.0%\n5311.21: size (16 days) 37.3K 186.0K +398.2%\n5311.22: client (16 days) (lookup=true) 0.03 0.02 -33.3%\n5311.24: server (32 days) (lookup=true) 0.03 0.03 +0.0%\n5311.25: size (32 days) 46.5K 197.2K +324.3%\n5311.26: client (32 days) (lookup=true) 0.03 0.02 -33.3%\n5311.28: server (64 days) (lookup=true) 0.24 0.16 -33.3%\n5311.29: size (64 days) 1.5M 5.1M +239.8%\n5311.30: client (64 days) (lookup=true) 0.42 0.35 -16.7%\n5311.32: server (128 days) (lookup=true) 0.49 0.29 -40.8%\n5311.33: size (128 days) 4.1M 9.8M +139.5%\n5311.34: client (128 days) (lookup=true) 0.86 0.65 -24.4%\n5311.38: server (1 days) (lookup=false) 0.02 0.03 +50.0%\n5311.39: size (1 days) 6.8K 124.9K +1730.9%\n5311.40: client (1 days) (lookup=false) 0.02 0.02 +0.0%\n5311.42: server (2 days) (lookup=false) 0.02 0.03 +50.0%\n5311.43: size (2 days) 6.8K 124.9K +1730.9%\n5311.44: client (2 days) (lookup=false) 0.02 0.02 +0.0%\n5311.46: server (4 days) (lookup=false) 0.02 0.03 +50.0%\n5311.47: size (4 days) 6.8K 124.9K +1730.9%\n5311.48: client (4 days) (lookup=false) 0.02 0.02 +0.0%\n5311.50: server (8 days) (lookup=false) 0.02 0.03 +50.0%\n5311.51: size (8 days) 37.3K 186.0K +398.2%\n5311.52: client (8 days) (lookup=false) 0.03 0.02 -33.3%\n5311.54: server (16 days) (lookup=false) 0.02 0.03 +50.0%\n5311.55: size (16 days) 37.3K 186.0K +398.2%\n5311.56: client (16 days) (lookup=false) 0.03 0.02 -33.3%\n5311.58: server (32 days) (lookup=false) 0.03 0.03 +0.0%\n5311.59: size (32 days) 46.5K 197.2K +324.3%\n5311.60: client (32 days) (lookup=false) 0.03 0.02 -33.3%\n5311.62: server (64 days) (lookup=false) 0.25 0.17 -32.0%\n5311.63: size (64 days) 1.5M 5.1M +239.8%\n5311.64: client (64 days) (lookup=false) 0.43 0.37 -14.0%\n5311.66: server (128 days) (lookup=false) 0.50 0.29 -42.0%\n5311.67: size (128 days) 4.1M 9.8M +138.6%\n5311.68: client (128 days) (lookup=false) 0.87 0.67 -23.0%\n\nIt's important to realize that even with the test variable, the\npath-walk logic is overriding the bitmap logic in the HEAD~3\ncase.\n\nWhat's happening is that the path-walk mode (without bitmaps)\nis computing a smaller packfile for all of these cases. Some\nare significantly smaller, but only when it's a very small\npack anyway. The bitmap case is faster only for larger fetches.\n\nI did the same test without the path-walk feature and both columns\nlooked the same (as expected, no change due to this series) and\nthe data matched the path-walk test's HEAD column pretty closely.\nSo this shows that adding path-walk to bitmap-focused efforts is\nnot a regression on any of these dimensions.\n\nThis test was for my local copy of the Git repository, including\nall the forks I fetch. I hoped the results would be different\nfor repositories that have data shapes that struggle with\nname-hash collisions, but microsoft/fluentui is an example that\nI've used for path-walk repacks before and it had similar data.\n\nDo you have a good feeling for why the path-walk feature doesn't\nmake a huge change in these test scenarios?\n\nThanks,\n-Stolee\n\n"},{"id":"544282","messageId":"ahnx/oBWe9yyBZFg@nand.local","threadId":"65704","inReplyTo":"22a7e32f-f645-4f00-bc5b-6b4309e483c2@gmail.com","subject":"Re: [PATCH 0/3] pack-objects: support bitmaps and delta-islands with `--path-walk`","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2026-05-29T20:07:26Z","receivedAt":"2026-05-29T20:07:28Z","isPatch":true,"body":"On Fri, May 29, 2026 at 01:26:33PM -0400, Derrick Stolee wrote:\n> On 5/28/26 11:28 AM, Derrick Stolee wrote:\n> > On 5/27/26 7:18 PM, Taylor Blau wrote:\n>\n> > Do you have any end-to-end performance data to demonstrate that these\n> > changes are effective at scale? Are we still producing packfiles with the\n> > pack-file compression and now with .bitmap files? How does this impact\n> > the performance of a clone or fetch when using a bitmap index at read\n> > time?\n>\n> Here's my attempt to use our existing performance tests to analyze the\n> impact of this series.\n>\n> Running p5311 against the base of this topic and this topic with\n> GIT_TEST_PACK_PATH_WALK=1, I get this output:\n\nYikes. That's not great, but see below for what I think is going on.\n\n(As an aside, we can focus in on either lookup=true or lookup=false,\nsince these are just controlling whether or not the bitmap lookup table\nis written. On a repository as small as git.git, this shouldn't make a\nhuge difference either way. I have a separate series to make this the\ndefault and to clean up the t/perf suite accordingly, but haven't sent\nit to the list yet.)\n\n> Test HEAD~3 HEAD\n> -----------------------------------------------------------------\n> [...]\n\nI think this is either the primary reason why you're not seeing an\nimprovement here, or at least related to it...\n\n> Do you have a good feeling for why the path-walk feature doesn't\n> make a huge change in these test scenarios?\n\nI think the problem is that we're relying on the TEST_ variable to tell\npack-objects to generate a pack using --path-walk, but treat it as a\nfallback.\n\nI suspect that since p5311 invokes repack *without* the '--path-walk'\noption, we end up in this case within cmd_pack_objects():\n\n\tif (path_walk < 0) {\n\t\tif (use_bitmap_index > 0 ||\n\t\t !use_internal_rev_list)\n\t\t\tpath_walk = 0;\n\t\telse if (the_repository->gitdir &&\n\t\t\t the_repository->settings.pack_use_path_walk)\n\t\t\tpath_walk = 1;\n\t\telse\n\t\t\tpath_walk = git_env_bool(\"GIT_TEST_PACK_PATH_WALK\", 0);\n\t}\n\n, where `path_walk` is *not* set, but `use_bitmap_index` is since p5311\nset the 'pack.writeBitmaps' configuration (as a separate aside, this\nshould really prefer the non-deprecated 'repack.writeBitmaps' variant).\n\nSo in that case, we fall back to `path_walk = 0`, and don't even bother\nreading the `GIT_TEST_PACK_PATH_WALK` variable.\n\nIf I modify the perf test like so:\n\n--- 8< ---\ndiff --git a/t/perf/p5311-pack-bitmaps-fetch.sh b/t/perf/p5311-pack-bitmaps-fetch.sh\nindex 047efb995d6..1c9c99216e3 100755\n--- a/t/perf/p5311-pack-bitmaps-fetch.sh\n+++ b/t/perf/p5311-pack-bitmaps-fetch.sh\n@@ -13,7 +13,7 @@ test_fetch_bitmaps () {\n \ttest_expect_success 'create bitmapped server repo' '\n \t\tgit config pack.writebitmaps true &&\n \t\tgit config pack.writeBitmapLookupTable '\"$1\"' &&\n-\t\tgit repack -ad\n+\t\tgit repack -ad --path-walk\n \t'\n\n \t# simulate a fetch from a repository that last fetched N days ago, for\n--- >8 ---\n\n, then I can get significantly improved results when running without the\nGIT_TEST_PACK_PATH_WALK variablle (here I'm truncating the\n'lookup=false' case, which performs nearly identically):\n\n Test HEAD~3 HEAD\n ------------------------------------------------------------------------------------\n 5311.4: server (1 days) (lookup=true) 2.57(2.52+0.04) 0.03(0.02+0.00) -98.8%\n 5311.5: size (1 days) 153.4K 153.4K +0.0%\n 5311.6: client (1 days) (lookup=true) 0.00(0.01+0.00) 0.00(0.01+0.00) =\n 5311.8: server (2 days) (lookup=true) 2.60(2.55+0.04) 0.02(0.02+0.00) -99.2%\n 5311.9: size (2 days) 153.4K 153.4K +0.0%\n 5311.10: client (2 days) (lookup=true) 0.00(0.01+0.00) 0.00(0.01+0.00) =\n 5311.12: server (4 days) (lookup=true) 2.60(2.54+0.05) 0.03(0.03+0.00) -98.8%\n 5311.13: size (4 days) 209.0K 209.0K +0.0%\n 5311.14: client (4 days) (lookup=true) 0.01(0.02+0.00) 0.01(0.01+0.00) +0.0%\n 5311.16: server (8 days) (lookup=true) 2.58(2.53+0.04) 0.03(0.03+0.00) -98.8%\n 5311.17: size (8 days) 209.0K 209.0K +0.0%\n 5311.18: client (8 days) (lookup=true) 0.01(0.01+0.00) 0.01(0.02+0.00) +0.0%\n 5311.20: server (16 days) (lookup=true) 2.58(2.52+0.05) 0.03(0.03+0.00) -98.8%\n 5311.21: size (16 days) 209.0K 209.0K +0.0%\n 5311.22: client (16 days) (lookup=true) 0.01(0.02+0.00) 0.01(0.01+0.00) +0.0%\n 5311.24: server (32 days) (lookup=true) 2.61(2.58+0.03) 0.03(0.02+0.01) -98.9%\n 5311.25: size (32 days) 212.9K 212.9K +0.0%\n 5311.26: client (32 days) (lookup=true) 0.01(0.02+0.00) 0.02(0.02+0.00) +100.0%\n 5311.28: server (64 days) (lookup=true) 2.72(2.79+0.06) 0.19(0.30+0.03) -93.0%\n 5311.29: size (64 days) 4.5M 4.5M -0.0%\n 5311.30: client (64 days) (lookup=true) 0.49(0.58+0.02) 0.48(0.56+0.04) -2.0%\n 5311.32: server (128 days) (lookup=true) 2.90(3.21+0.09) 0.35(0.70+0.04) -87.9%\n 5311.33: size (128 days) 9.4M 9.5M +0.4%\n 5311.34: client (128 days) (lookup=true) 0.98(1.27+0.08) 0.98(1.33+0.06) +0.0%\n\nMy reading here is that we get significantly smaller packs (i.e. all\n'test_size' tests drop from HEAD~3 to HEAD) in the same amount of time\n(i.e. that all 'test_perf' tests are roughly flat).\n\nThat lines up with my expectation here, which is that even though we're\nusing bitmaps at read time, that's effectively seeding the verbatim pack\nreuse over a significantly smaller pack, producing a much smaller output\npack as a result.\n\nAs to whether we should modify the perf suite to test this, naturally I\nthink we should. Likely that looks like modifying p5313 to re-run\n`test_all_with_args` with '--use-bitmap-index' after repacking with\n--path-walk and generating bitmaps like so (untested):\n\n--- 8< ---\ndiff --git a/t/perf/p5313-pack-objects.sh b/t/perf/p5313-pack-objects.sh\nindex 46a6cd32d24..663717982b1 100755\n--- a/t/perf/p5313-pack-objects.sh\n+++ b/t/perf/p5313-pack-objects.sh\n@@ -22,6 +22,21 @@ test_expect_success 'create rev input' '\n \tEOF\n '\n\n+test_repack_with_args () {\n+\targs=\"$@\"\n+\texport args\n+\n+\ttest_perf \"repack with $args\" '\n+\t\tgit repack -adf $args\n+\t'\n+\n+\ttest_size \"repack size with $args\" '\n+\t\tgitdir=$(git rev-parse --git-dir) &&\n+\t\tpack=$(ls $gitdir/objects/pack/pack-*.pack) &&\n+\t\ttest_file_size \"$pack\"\n+\t'\n+}\n+\n test_all_with_args () {\n \tparameter=$1\n \texport parameter\n@@ -52,23 +67,22 @@ test_all_with_args () {\n \ttest_size \"shallow pack size with $parameter\" '\n \t\ttest_file_size out\n \t'\n-\n-\ttest_perf \"repack with $parameter\" '\n-\t\tgit repack -adf $parameter\n-\t'\n-\n-\ttest_size \"repack size with $parameter\" '\n-\t\tgitdir=$(git rev-parse --git-dir) &&\n-\t\tpack=$(ls $gitdir/objects/pack/pack-*.pack) &&\n-\t\ttest_file_size \"$pack\"\n-\t'\n }\n\n for version in 1 2\n do\n-\ttest_all_with_args --name-hash-version=$version\n+\targ=\"--name-hash-version=$version\" &&\n+\n+\ttest_all_with_args \"$arg\" &&\n+\ttest_repack_with_args \"$arg\" || return 1\n done\n\n test_all_with_args --path-walk\n+test_repack_with_args --path-walk\n+\n+# inverted order here: we want to test using reachability bitmaps on a\n+# pack written with --path-walk\n+test_repack_with_args --path-walk --write-bitmap-index\n+test_all_with_args --use-bitmap-index\n\n test_done\n--- >8 ---\n\nI don't have a strong opinion on whether or not we should include that\nin this series or elsewhere.\n\nThanks,\nTaylor\n"},{"id":"544291","messageId":"2d68fdb2-ac05-4331-b53e-53c2e9a2b3d4@gmail.com","threadId":"65704","inReplyTo":"ahnx/oBWe9yyBZFg@nand.local","subject":"Re: [PATCH 0/3] pack-objects: support bitmaps and delta-islands with `--path-walk`","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2026-05-29T21:28:32Z","receivedAt":"2026-05-29T21:28:34Z","isPatch":true,"body":"On 5/29/2026 4:07 PM, Taylor Blau wrote:\n> On Fri, May 29, 2026 at 01:26:33PM -0400, Derrick Stolee wrote:\n>> On 5/28/26 11:28 AM, Derrick Stolee wrote:\n>>> On 5/27/26 7:18 PM, Taylor Blau wrote:\n>>\n>>> Do you have any end-to-end performance data to demonstrate that these\n>>> changes are effective at scale? Are we still producing packfiles with the\n>>> pack-file compression and now with .bitmap files? How does this impact\n>>> the performance of a clone or fetch when using a bitmap index at read\n>>> time?\n>>\n>> Here's my attempt to use our existing performance tests to analyze the\n>> impact of this series.\n>>\n>> Running p5311 against the base of this topic and this topic with\n>> GIT_TEST_PACK_PATH_WALK=1, I get this output:\n> \n> Yikes. That's not great, but see below for what I think is going on.\n> \n> (As an aside, we can focus in on either lookup=true or lookup=false,\n> since these are just controlling whether or not the bitmap lookup table\n> is written. On a repository as small as git.git, this shouldn't make a\n> huge difference either way. I have a separate series to make this the\n> default and to clean up the t/perf suite accordingly, but haven't sent\n> it to the list yet.)\n> \n>> Test HEAD~3 HEAD\n>> -----------------------------------------------------------------\n>> [...]\n> \n> I think this is either the primary reason why you're not seeing an\n> improvement here, or at least related to it...\n> \n>> Do you have a good feeling for why the path-walk feature doesn't\n>> make a huge change in these test scenarios?\n> \n> I think the problem is that we're relying on the TEST_ variable to tell\n> pack-objects to generate a pack using --path-walk, but treat it as a\n> fallback.\n> \n> I suspect that since p5311 invokes repack *without* the '--path-walk'\n> option, we end up in this case within cmd_pack_objects():\n> \n> \tif (path_walk < 0) {\n> \t\tif (use_bitmap_index > 0 ||\n> \t\t !use_internal_rev_list)\n> \t\t\tpath_walk = 0;\n> \t\telse if (the_repository->gitdir &&\n> \t\t\t the_repository->settings.pack_use_path_walk)\n> \t\t\tpath_walk = 1;\n> \t\telse\n> \t\t\tpath_walk = git_env_bool(\"GIT_TEST_PACK_PATH_WALK\", 0);\n> \t}\n> \n> , where `path_walk` is *not* set, but `use_bitmap_index` is since p5311\n> set the 'pack.writeBitmaps' configuration (as a separate aside, this\n> should really prefer the non-deprecated 'repack.writeBitmaps' variant).\nI see. When `--use-bitmap-index` is specified, then the test variable is\nignored. So my tests aren't actually measuring the intended end state.\n\n> So in that case, we fall back to `path_walk = 0`, and don't even bother\n> reading the `GIT_TEST_PACK_PATH_WALK` variable.\n> \n> If I modify the perf test like so:\n> \n> --- 8< ---\n> diff --git a/t/perf/p5311-pack-bitmaps-fetch.sh b/t/perf/p5311-pack-bitmaps-fetch.sh\n> index 047efb995d6..1c9c99216e3 100755\n> --- a/t/perf/p5311-pack-bitmaps-fetch.sh\n> +++ b/t/perf/p5311-pack-bitmaps-fetch.sh\n> @@ -13,7 +13,7 @@ test_fetch_bitmaps () {\n> \ttest_expect_success 'create bitmapped server repo' '\n> \t\tgit config pack.writebitmaps true &&\n> \t\tgit config pack.writeBitmapLookupTable '\"$1\"' &&\n> -\t\tgit repack -ad\n> +\t\tgit repack -ad --path-walk\n> \t'\n> \n> \t# simulate a fetch from a repository that last fetched N days ago, for\n> --- >8 ---\n> , then I can get significantly improved results when running without the\n> GIT_TEST_PACK_PATH_WALK variablle (here I'm truncating the\n> 'lookup=false' case, which performs nearly identically):\n> \n> Test HEAD~3 HEAD\n> ------------------------------------------------------------------------------------\n> 5311.4: server (1 days) (lookup=true) 2.57(2.52+0.04) 0.03(0.02+0.00) -98.8%\n> 5311.5: size (1 days) 153.4K 153.4K +0.0%\n> 5311.6: client (1 days) (lookup=true) 0.00(0.01+0.00) 0.00(0.01+0.00) =\n> 5311.8: server (2 days) (lookup=true) 2.60(2.55+0.04) 0.02(0.02+0.00) -99.2%\n> 5311.9: size (2 days) 153.4K 153.4K +0.0%\n> 5311.10: client (2 days) (lookup=true) 0.00(0.01+0.00) 0.00(0.01+0.00) =\n> 5311.12: server (4 days) (lookup=true) 2.60(2.54+0.05) 0.03(0.03+0.00) -98.8%\n> 5311.13: size (4 days) 209.0K 209.0K +0.0%\n> 5311.14: client (4 days) (lookup=true) 0.01(0.02+0.00) 0.01(0.01+0.00) +0.0%\n> 5311.16: server (8 days) (lookup=true) 2.58(2.53+0.04) 0.03(0.03+0.00) -98.8%\n> 5311.17: size (8 days) 209.0K 209.0K +0.0%\n> 5311.18: client (8 days) (lookup=true) 0.01(0.01+0.00) 0.01(0.02+0.00) +0.0%\n> 5311.20: server (16 days) (lookup=true) 2.58(2.52+0.05) 0.03(0.03+0.00) -98.8%\n> 5311.21: size (16 days) 209.0K 209.0K +0.0%\n> 5311.22: client (16 days) (lookup=true) 0.01(0.02+0.00) 0.01(0.01+0.00) +0.0%\n> 5311.24: server (32 days) (lookup=true) 2.61(2.58+0.03) 0.03(0.02+0.01) -98.9%\n> 5311.25: size (32 days) 212.9K 212.9K +0.0%\n> 5311.26: client (32 days) (lookup=true) 0.01(0.02+0.00) 0.02(0.02+0.00) +100.0%\n> 5311.28: server (64 days) (lookup=true) 2.72(2.79+0.06) 0.19(0.30+0.03) -93.0%\n> 5311.29: size (64 days) 4.5M 4.5M -0.0%\n> 5311.30: client (64 days) (lookup=true) 0.49(0.58+0.02) 0.48(0.56+0.04) -2.0%\n> 5311.32: server (128 days) (lookup=true) 2.90(3.21+0.09) 0.35(0.70+0.04) -87.9%\n> 5311.33: size (128 days) 9.4M 9.5M +0.4%\n> 5311.34: client (128 days) (lookup=true) 0.98(1.27+0.08) 0.98(1.33+0.06) +0.0%\n> \n> My reading here is that we get significantly smaller packs (i.e. all\n> 'test_size' tests drop from HEAD~3 to HEAD) in the same amount of time\n> (i.e. that all 'test_perf' tests are roughly flat).\n\nThe sizes don't shrink, and in one case increases by a small amount. I'm\nhappy to count those cases as noise from multi-threaded delta calculations\nbeing less deterministic.\n\nThe _time_ taken to compute the packfiles is what decreases, though, which\nis promising.\n\n> That lines up with my expectation here, which is that even though we're\n> using bitmaps at read time, that's effectively seeding the verbatim pack\n> reuse over a significantly smaller pack, producing a much smaller output\n> pack as a result.\n\nCan you double-check this reasoning with my read of the data? The size\nisn't changing, but the computation time is.\n\n> As to whether we should modify the perf suite to test this, naturally I\n> think we should. Likely that looks like modifying p5313 to re-run\n> `test_all_with_args` with '--use-bitmap-index' after repacking with\n> --path-walk and generating bitmaps like so (untested):\n> \n> --- 8< ---\n> diff --git a/t/perf/p5313-pack-objects.sh b/t/perf/p5313-pack-objects.sh\n> index 46a6cd32d24..663717982b1 100755\n> --- a/t/perf/p5313-pack-objects.sh\n> +++ b/t/perf/p5313-pack-objects.sh\n> @@ -22,6 +22,21 @@ test_expect_success 'create rev input' '\n> \tEOF\n> '\n> \n> +test_repack_with_args () {\n> +\targs=\"$@\"\n> +\texport args\n> +\n> +\ttest_perf \"repack with $args\" '\n> +\t\tgit repack -adf $args\n> +\t'\n> +\n> +\ttest_size \"repack size with $args\" '\n> +\t\tgitdir=$(git rev-parse --git-dir) &&\n> +\t\tpack=$(ls $gitdir/objects/pack/pack-*.pack) &&\n> +\t\ttest_file_size \"$pack\"\n> +\t'\n> +}\n> +\nI see that these tests are extracted from test_all_... below:\n\n> test_all_with_args () {\n> \tparameter=$1\n> \texport parameter\n> @@ -52,23 +67,22 @@ test_all_with_args () {\n> \ttest_size \"shallow pack size with $parameter\" '\n> \t\ttest_file_size out\n> \t'\n> -\n> -\ttest_perf \"repack with $parameter\" '\n> -\t\tgit repack -adf $parameter\n> -\t'\n> -\n> -\ttest_size \"repack size with $parameter\" '\n> -\t\tgitdir=$(git rev-parse --git-dir) &&\n> -\t\tpack=$(ls $gitdir/objects/pack/pack-*.pack) &&\n> -\t\ttest_file_size \"$pack\"\n> -\t'\n> }\n\nBecause the --use-bitmap-index and --write-bitmap-index args\naren't appropriate across these different commands.\n\nnit: the diff would be more obvious if test_repack_with_args\nwas defined after test_all_with_args so the hunk of existing\ntests wouldn't appear in the diff.\n\n> for version in 1 2\n> do\n> -\ttest_all_with_args --name-hash-version=$version\n> +\targ=\"--name-hash-version=$version\" &&\n> +\n> +\ttest_all_with_args \"$arg\" &&\n> +\ttest_repack_with_args \"$arg\" || return 1\n> done\n> \n> test_all_with_args --path-walk\n> +test_repack_with_args --path-walk\n> +\n> +# inverted order here: we want to test using reachability bitmaps on a\n> +# pack written with --path-walk\n> +test_repack_with_args --path-walk --write-bitmap-index\n> +test_all_with_args --use-bitmap-index\n\nSo this allows us to test all of the different modes.\n\n> --- >8 ---\n> \n> I don't have a strong opinion on whether or not we should include that\n> in this series or elsewhere.\nI'm interested to see some results of your new p5313 test\nto make sure that we are getting expected size changes for\nthe repack, since the p5311 tests were more focused on the\nthin fetch pack (and didn't show a change in size).\n\nFor that, I'd be interested to see this test be included in\na patch for future reference, too.\n\nThanks,\n-Stolee\n\n"},{"id":"544292","messageId":"ahoRQZX6OXYKPCmd@nand.local","threadId":"65704","inReplyTo":"2d68fdb2-ac05-4331-b53e-53c2e9a2b3d4@gmail.com","subject":"Re: [PATCH 0/3] pack-objects: support bitmaps and delta-islands with `--path-walk`","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2026-05-29T22:20:49Z","receivedAt":"2026-05-29T22:20:54Z","isPatch":true,"body":"On Fri, May 29, 2026 at 05:28:32PM -0400, Derrick Stolee wrote:\n> > My reading here is that we get significantly smaller packs (i.e. all\n> > 'test_size' tests drop from HEAD~3 to HEAD) in the same amount of time\n> > (i.e. that all 'test_perf' tests are roughly flat).\n>\n> The sizes don't shrink, and in one case increases by a small amount. I'm\n> happy to count those cases as noise from multi-threaded delta calculations\n> being less deterministic.\n>\n> The _time_ taken to compute the packfiles is what decreases, though, which\n> is promising.\n>\n> > That lines up with my expectation here, which is that even though we're\n> > using bitmaps at read time, that's effectively seeding the verbatim pack\n> > reuse over a significantly smaller pack, producing a much smaller output\n> > pack as a result.\n>\n> Can you double-check this reasoning with my read of the data? The size\n> isn't changing, but the computation time is.\n\nYeah, that's right, and my apologies for being in a slight rush when\nsending this to you ;-).\n\nThe size staying flat makes sense, since both packs were generated with\n--path-walk, we're just changing the way they're served. In HEAD~3, that\npack is generated on-the-fly and sent over to the client. At HEAD, we're\ndoing verbatim reuse over an already-existing pack which we got via\nrepacking (also generated with --path-walk).\n\nSo I think you get to the same end-result (more or less, modulo usual\ndelta patching via pack-reuse), but the time to get there drops\nsignificantly since we don't have to (re)compute the pack.\n\n> > +test_repack_with_args () {\n> > +\targs=\"$@\"\n> > +\texport args\n> > +\n> > +\ttest_perf \"repack with $args\" '\n> > +\t\tgit repack -adf $args\n> > +\t'\n> > +\n> > +\ttest_size \"repack size with $args\" '\n> > +\t\tgitdir=$(git rev-parse --git-dir) &&\n> > +\t\tpack=$(ls $gitdir/objects/pack/pack-*.pack) &&\n> > +\t\ttest_file_size \"$pack\"\n> > +\t'\n> > +}\n> > +\n> I see that these tests are extracted from test_all_... below:\n>\n> [...]\n>\n> Because the --use-bitmap-index and --write-bitmap-index args\n> aren't appropriate across these different commands.\n\nExactly.\n\n> nit: the diff would be more obvious if test_repack_with_args\n> was defined after test_all_with_args so the hunk of existing\n> tests wouldn't appear in the diff.\n\nFair enough :-).\n\n> > for version in 1 2\n> > do\n> > -\ttest_all_with_args --name-hash-version=$version\n> > +\targ=\"--name-hash-version=$version\" &&\n> > +\n> > +\ttest_all_with_args \"$arg\" &&\n> > +\ttest_repack_with_args \"$arg\" || return 1\n> > done\n> >\n> > test_all_with_args --path-walk\n> > +test_repack_with_args --path-walk\n> > +\n> > +# inverted order here: we want to test using reachability bitmaps on a\n> > +# pack written with --path-walk\n> > +test_repack_with_args --path-walk --write-bitmap-index\n> > +test_all_with_args --use-bitmap-index\n>\n> So this allows us to test all of the different modes.\n>\n> > --- >8 ---\n> >\n> > I don't have a strong opinion on whether or not we should include that\n> > in this series or elsewhere.\n>\n> I'm interested to see some results of your new p5313 test\n> to make sure that we are getting expected size changes for\n> the repack, since the p5311 tests were more focused on the\n> thin fetch pack (and didn't show a change in size).\n>\n> For that, I'd be interested to see this test be included in\n> a patch for future reference, too.\n\nWill do.\n\nThanks,\nTaylor\n"},{"id":"544556","messageId":"cover.1780438896.git.me@ttaylorr.com","threadId":"65704","inReplyTo":"cover.1779923907.git.me@ttaylorr.com","subject":"[PATCH v2 0/4] pack-objects: support bitmaps and delta-islands with `--path-walk`","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2026-06-02T22:21:40Z","receivedAt":"2026-06-02T22:21:43Z","isPatch":true,"body":"Note to the maintainer:\n\n * This series is based on 'ds/path-walk-filters' with Patrick's\n 'ps/clang-w-glibc-2.43-and-_Generic' merged in. The former has since\n graduated. These are the three remaining patches from my earlier RFC\n after Stolee's series incorporated the filter-related pieces.\n\nHere is a very small reroll of my series to make `--path-walk` work with\nreachability bitmaps and delta-islands.\n\nSince the previous round, the only changes are:\n\n * A new commit making some adjustments to p5311 to facilitate\n performance testing bitmaps in repositories repacked with\n '--path-walk'.\n\n * Updates to (what is now) the second commit's message, including\n performance results based on the aforementioned changes.\n\nOutside of the above, the series is otherwise unchanged.\n\nThanks in advance for your review!\n\nTaylor Blau (4):\n t/perf: drop p5311's lookup-table permutation\n pack-objects: support reachability bitmaps with `--path-walk`\n pack-objects: extract `record_tree_depth()` helper\n pack-objects: support `--delta-islands` with `--path-walk`\n\n Documentation/git-pack-objects.adoc | 12 ++---\n builtin/pack-objects.c | 68 +++++++++++++++++++++--------\n t/perf/p5311-pack-bitmaps-fetch.sh | 20 +++++----\n t/t5310-pack-bitmaps.sh | 36 +++++++++++++++\n t/t5320-delta-islands.sh | 29 ++++++++++++\n 5 files changed, 134 insertions(+), 31 deletions(-)\n\nRange-diff against v1:\n-: ----------- > 1: 52d63e8910e t/perf: drop p5311's lookup-table permutation\n1: 3fa8bfbfd59 ! 2: ffad584a43e pack-objects: support reachability bitmaps with `--path-walk`\n @@ Commit message\n bitmap can answer the request, use it; otherwise fall back to\n path-walk's own enumeration.\n \n + As a result, we can see significantly reduced pack sizes from p5311\n + before this commit:\n +\n + Test HEAD^ HEAD\n + ----------------------------------------------------------------------------------\n + 5311.38: server (1 days, --path-walk) 2.56(2.52+0.03) 0.01(0.01+0.00) -99.6%\n + 5311.39: size (1 days, --path-walk) 123.9K 123.9K +0.0%\n + 5311.40: client (1 days, --path-walk) 0.00(0.01+0.00) 0.00(0.00+0.00) =\n + 5311.42: server (2 days, --path-walk) 2.57(2.52+0.05) 0.01(0.01+0.00) -99.6%\n + 5311.43: size (2 days, --path-walk) 123.9K 123.9K +0.0%\n + 5311.44: client (2 days, --path-walk) 0.00(0.00+0.00) 0.00(0.00+0.00) =\n + 5311.46: server (4 days, --path-walk) 2.58(2.51+0.07) 0.01(0.01+0.00) -99.6%\n + 5311.47: size (4 days, --path-walk) 123.9K 123.9K +0.0%\n + 5311.48: client (4 days, --path-walk) 0.00(0.00+0.00) 0.00(0.00+0.00) =\n + 5311.50: server (8 days, --path-walk) 2.58(2.53+0.04) 0.02(0.02+0.00) -99.2%\n + 5311.51: size (8 days, --path-walk) 152.4K 152.4K +0.0%\n + 5311.52: client (8 days, --path-walk) 0.00(0.01+0.00) 0.00(0.01+0.00) =\n + 5311.54: server (16 days, --path-walk) 2.58(2.52+0.05) 0.03(0.02+0.00) -98.8%\n + 5311.55: size (16 days, --path-walk) 205.3K 205.3K +0.0%\n + 5311.56: client (16 days, --path-walk) 0.01(0.01+0.00) 0.01(0.01+0.00) +0.0%\n + 5311.58: server (32 days, --path-walk) 2.59(2.53+0.06) 0.03(0.03+0.00) -98.8%\n + 5311.59: size (32 days, --path-walk) 209.3K 209.3K +0.0%\n + 5311.60: client (32 days, --path-walk) 0.01(0.02+0.00) 0.01(0.02+0.00) +0.0%\n + 5311.62: server (64 days, --path-walk) 2.70(2.76+0.06) 0.16(0.24+0.04) -94.1%\n + 5311.63: size (64 days, --path-walk) 4.1M 4.1M +0.0%\n + 5311.64: client (64 days, --path-walk) 0.44(0.50+0.02) 0.44(0.51+0.02) +0.0%\n + 5311.66: server (128 days, --path-walk) 2.88(3.20+0.05) 0.34(0.65+0.05) -88.2%\n + 5311.67: size (128 days, --path-walk) 9.0M 9.0M -0.0%\n + 5311.68: client (128 days, --path-walk) 0.93(1.22+0.07) 0.93(1.20+0.08) +0.0%\n +\n + We get the same size of output pack, but this commit allows us to do so\n + in a significantly shorter amount of time. Intuitively, we're generating\n + the same pack (hence the unchanged 'test_size' output from run to run),\n + but varying how we get there. Before this commit, pack-objects prefers\n + '--path-walk' to '--use-bitmap-index', so we generate the output pack by\n + performing a normal '--path-walk' traversal. With this commit, we are\n + operating over a *repacked* state (that itself was done with a\n + '--path-walk' traversal), but are able to perform pack-reuse on that\n + repacked state via bitmaps.\n +\n There is one wrinkle when it comes to '--boundary', which we must not\n pass into the bitmap walk in the presence of both '--path-walk' and\n '--use-bitmap-index'. Path-walk needs boundary commits when it performs\n its own traversal, in order to discover bases for thin packs, but the\n - bitmap traversal expects the usual non-boundary state. Work around this\n - by setting `revs->boundary` as late as possible within\n - `get_object_list_path_walk()`, after any bitmap attempt has either\n - succeeded or declined to answer the request.\n + bitmap traversal does not expect this. Work around this by setting\n + `revs->boundary` as late as possible within the '--path-walk' traversal,\n + after any bitmap attempt has either succeeded or declined to answer the\n + request.\n \n Signed-off-by: Taylor Blau \n \n @@ builtin/pack-objects.c: int cmd_pack_objects(int argc,\n \t\tuse_internal_rev_list = 1;\n \t\tstrvec_push(&rp, shallow\n \n + ## t/perf/p5311-pack-bitmaps-fetch.sh ##\n +@@ t/perf/p5311-pack-bitmaps-fetch.sh: test_description='performance of fetches from bitmapped packs'\n + . ./perf-lib.sh\n + \n + test_fetch_bitmaps () {\n ++\targv=$1\n ++\texport argv\n ++\n + \ttest_expect_success 'setup test directory' '\n + \t\trm -fr * .git\n + \t'\n + \n + \ttest_perf_default_repo\n + \n +-\ttest_expect_success 'create bitmapped server repo' '\n ++\ttest_expect_success \"create bitmapped server repo ${argv:+($argv)}\" '\n + \t\tgit config pack.writebitmaps true &&\n +-\t\tgit repack -ad\n ++\t\tgit repack -ad $argv\n + \t'\n + \n + \t# simulate a fetch from a repository that last fetched N days ago, for\n +@@ t/perf/p5311-pack-bitmaps-fetch.sh: test_fetch_bitmaps () {\n + \t# and assume the first entry in the chain that is N days older than the current\n + \t# HEAD is where the HEAD would have been then.\n + \tfor days in 1 2 4 8 16 32 64 128; do\n +-\t\ttitle=$(printf '%10s' \"($days days)\")\n ++\t\ttitle=$(printf '%10s' \"($days days${argv:+, $argv})\")\n + \t\ttest_expect_success \"setup revs from $days days ago\" '\n + \t\t\tnow=$(git log -1 --format=%ct HEAD) &&\n + \t\t\tthen=$(($now - ($days * 86400))) &&\n +@@ t/perf/p5311-pack-bitmaps-fetch.sh: test_fetch_bitmaps () {\n + \tdone\n + }\n + \n +-test_fetch_bitmaps\n ++for argv in '' --path-walk\n ++do\n ++\ttest_fetch_bitmaps $argv || return 1\n ++done\n + \n + test_done\n +\n ## t/t5310-pack-bitmaps.sh ##\n @@ t/t5310-pack-bitmaps.sh: test_bitmap_cases\n \n2: bdae873eaab = 3: 069c50d3370 pack-objects: extract `record_tree_depth()` helper\n3: a642305e3c9 = 4: ae57607b57f pack-objects: support `--delta-islands` with `--path-walk`\n\nbase-commit: 45a9ecee26839cc880fdd5e704339dd3cf4ffc26\n-- \n2.54.0.23.gae57607b57f\n"},{"id":"544557","messageId":"52d63e8910e4ca716405713d48cedeb26026a3b3.1780438896.git.me@ttaylorr.com","threadId":"65704","inReplyTo":"cover.1780438896.git.me@ttaylorr.com","subject":"[PATCH v2 1/4] t/perf: drop p5311's lookup-table permutation","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2026-06-02T22:21:44Z","receivedAt":"2026-06-02T22:21:46Z","isPatch":true,"body":"p5311 measures the cost of serving a fetch from a bitmapped pack and\nindexing the resulting pack on the client. Since 761416ef91d\n(bitmap-lookup-table: add performance tests for lookup table,\n2022-08-14), p5311 effectively runs itself twice: once with the bitmap's\nlookup table extension enabled, and again with it disabled.\n\nThis comparison has served its useful purpose, as the lookup table is\nalmost four years old, and the de-facto default in server-side Git\ndeployments.\n\nA following commit will want to test a different combination (repacking\nwith and without '--path-walk' instead of the lookup table). Instead of\nmultiplying the current test count by two again to produce four\nvariations of `test_fetch_bitmaps()`, drop the lookup table option to\nreduce the number of perf tests we run. Retain `test_fetch_bitmaps()`\nitself, since we will use this in the future for the new\nparameterization.\n\n(As an aside, a future commit outside of this series will adjust the\ndefault value of 'pack.writeBitmapLookupTable' to \"true\", matching the\nde-facto norm for deployments where the existence of bitmap lookup\ntables is meaningful. Punt on that to a later series and instead make\nthe minimal change for now.)\n\nSuggested-by: Derrick Stolee \nSigned-off-by: Taylor Blau \n---\n t/perf/p5311-pack-bitmaps-fetch.sh | 8 +++-----\n 1 file changed, 3 insertions(+), 5 deletions(-)\n\ndiff --git a/t/perf/p5311-pack-bitmaps-fetch.sh b/t/perf/p5311-pack-bitmaps-fetch.sh\nindex 047efb995d6..5bea5c64e7b 100755\n--- a/t/perf/p5311-pack-bitmaps-fetch.sh\n+++ b/t/perf/p5311-pack-bitmaps-fetch.sh\n@@ -12,7 +12,6 @@ test_fetch_bitmaps () {\n \n \ttest_expect_success 'create bitmapped server repo' '\n \t\tgit config pack.writebitmaps true &&\n-\t\tgit config pack.writeBitmapLookupTable '\"$1\"' &&\n \t\tgit repack -ad\n \t'\n \n@@ -32,7 +31,7 @@ test_fetch_bitmaps () {\n \t\t\t} >revs\n \t\t'\n \n-\t\ttest_perf \"server $title (lookup=$1)\" '\n+\t\ttest_perf \"server $title\" '\n \t\t\tgit pack-objects --stdout --revs \\\n \t\t\t\t\t--thin --delta-base-offset \\\n \t\t\t\t\ttmp.pack\n@@ -42,13 +41,12 @@ test_fetch_bitmaps () {\n \t\t\ttest_file_size tmp.pack\n \t\t'\n \n-\t\ttest_perf \"client $title (lookup=$1)\" '\n+\t\ttest_perf \"client $title\" '\n \t\t\tgit index-pack --stdin --fix-thin boundary` as late as possible within the '--path-walk' traversal,\nafter any bitmap attempt has either succeeded or declined to answer the\nrequest.\n\nSigned-off-by: Taylor Blau \n---\n Documentation/git-pack-objects.adoc | 6 +++--\n builtin/pack-objects.c | 18 +++++++++++++--\n t/perf/p5311-pack-bitmaps-fetch.sh | 14 +++++++----\n t/t5310-pack-bitmaps.sh | 36 +++++++++++++++++++++++++++++\n 4 files changed, 66 insertions(+), 8 deletions(-)\n\ndiff --git a/Documentation/git-pack-objects.adoc b/Documentation/git-pack-objects.adoc\nindex 8a27aa19fd3..0adce8961a3 100644\n--- a/Documentation/git-pack-objects.adoc\n+++ b/Documentation/git-pack-objects.adoc\n@@ -402,8 +402,10 @@ will be automatically changed to version `1`.\n \tof filenames that cause collisions in Git's default name-hash\n \talgorithm.\n +\n-Incompatible with `--delta-islands`. The `--use-bitmap-index` option is\n-ignored in the presence of `--path-walk`. The `--path-walk` option\n+Incompatible with `--delta-islands`. When `--use-bitmap-index` is\n+specified with `--path-walk`, a successful bitmap traversal is used for\n+object enumeration, with path-walk remaining as the fallback traversal\n+when the bitmap cannot satisfy the request. The `--path-walk` option\n supports the `--filter=` forms `blob:none`, `blob:limit=`,\n `tree:0`, `object:type=`, and `sparse:`. These supported filter\n types can be combined with the `combine:+` form.\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex b783dc62bc9..e4dcb563b7d 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -4732,6 +4732,15 @@ static int add_objects_by_path(const char *path,\n \t\t\tcontinue;\n \n \t\tadd_object_entry(oid, type, path, exclude);\n+\n+\t\tif (type == OBJ_COMMIT && write_bitmap_index) {\n+\t\t\tstruct commit *commit;\n+\n+\t\t\tcommit = lookup_commit(the_repository, oid);\n+\t\t\tif (!commit)\n+\t\t\t\tdie(_(\"could not find commit %s\"), oid_to_hex(oid));\n+\t\t\tindex_commit_for_bitmap(commit);\n+\t\t}\n \t}\n \n \toe_end = to_pack.nr_objects;\n@@ -4764,6 +4773,13 @@ static int get_object_list_path_walk(struct rev_info *revs)\n \tinfo.path_fn = add_objects_by_path;\n \tinfo.path_fn_data = &processed;\n \n+\t/*\n+\t * Path-walk needs boundary commits to discover thin-pack bases, but\n+\t * bitmap traversal does not understand the boundary state. Set it\n+\t * here so any prior bitmap attempt sees the usual non-boundary walk.\n+\t */\n+\trevs->boundary = 1;\n+\n \t/*\n \t * Allow the --[no-]sparse option to be interesting here, if only\n \t * for testing purposes. Paths with no interesting objects will not\n@@ -5195,9 +5211,7 @@ int cmd_pack_objects(int argc,\n \t\t}\n \t}\n \tif (path_walk) {\n-\t\tstrvec_push(&rp, \"--boundary\");\n \t\tstrvec_push(&rp, \"--objects\");\n-\t\tuse_bitmap_index = 0;\n \t} else if (thin) {\n \t\tuse_internal_rev_list = 1;\n \t\tstrvec_push(&rp, shallow\ndiff --git a/t/perf/p5311-pack-bitmaps-fetch.sh b/t/perf/p5311-pack-bitmaps-fetch.sh\nindex 5bea5c64e7b..1b115d921a1 100755\n--- a/t/perf/p5311-pack-bitmaps-fetch.sh\n+++ b/t/perf/p5311-pack-bitmaps-fetch.sh\n@@ -4,15 +4,18 @@ test_description='performance of fetches from bitmapped packs'\n . ./perf-lib.sh\n \n test_fetch_bitmaps () {\n+\targv=$1\n+\texport argv\n+\n \ttest_expect_success 'setup test directory' '\n \t\trm -fr * .git\n \t'\n \n \ttest_perf_default_repo\n \n-\ttest_expect_success 'create bitmapped server repo' '\n+\ttest_expect_success \"create bitmapped server repo ${argv:+($argv)}\" '\n \t\tgit config pack.writebitmaps true &&\n-\t\tgit repack -ad\n+\t\tgit repack -ad $argv\n \t'\n \n \t# simulate a fetch from a repository that last fetched N days ago, for\n@@ -20,7 +23,7 @@ test_fetch_bitmaps () {\n \t# and assume the first entry in the chain that is N days older than the current\n \t# HEAD is where the HEAD would have been then.\n \tfor days in 1 2 4 8 16 32 64 128; do\n-\t\ttitle=$(printf '%10s' \"($days days)\")\n+\t\ttitle=$(printf '%10s' \"($days days${argv:+, $argv})\")\n \t\ttest_expect_success \"setup revs from $days days ago\" '\n \t\t\tnow=$(git log -1 --format=%ct HEAD) &&\n \t\t\tthen=$(($now - ($days * 86400))) &&\n@@ -47,6 +50,9 @@ test_fetch_bitmaps () {\n \tdone\n }\n \n-test_fetch_bitmaps\n+for argv in '' --path-walk\n+do\n+\ttest_fetch_bitmaps $argv || return 1\n+done\n \n test_done\ndiff --git a/t/t5310-pack-bitmaps.sh b/t/t5310-pack-bitmaps.sh\nindex f693cb56691..69c5da1580a 100755\n--- a/t/t5310-pack-bitmaps.sh\n+++ b/t/t5310-pack-bitmaps.sh\n@@ -577,6 +577,42 @@ test_bitmap_cases\n \n sane_unset GIT_TEST_PACK_USE_BITMAP_BOUNDARY_TRAVERSAL\n \n+test_expect_success 'path-walk repack can write and use bitmap indexes' '\n+\ttest_when_finished \"rm -rf path-walk-bitmap\" &&\n+\tgit init path-walk-bitmap &&\n+\t(\n+\t\tcd path-walk-bitmap &&\n+\t\ttest_commit first &&\n+\t\ttest_commit second &&\n+\t\ttest_commit third &&\n+\n+\t\tgit repack -a -d -b --path-walk &&\n+\t\tgit rev-list --test-bitmap --use-bitmap-index HEAD &&\n+\n+\t\tgit rev-parse HEAD >in &&\n+\n+\t\tgit rev-list --objects --no-object-names HEAD >expect.raw &&\n+\t\tsort expect.raw >expect &&\n+\n+\t\tfor reuse in true false\n+\t\tdo\n+\t\t\t: >trace.txt &&\n+\n+\t\t\tGIT_TRACE2_EVENT=\"$(pwd)/trace.txt\" \\\n+\t\t\tgit -c pack.allowPackReuse=$reuse pack-objects \\\n+\t\t\t\t--stdout --revs --path-walk --use-bitmap-index \\\n+\t\t\t\tout.pack &&\n+\t\t\tgrep \"\\\"category\\\":\\\"bitmap\\\",\\\"key\\\":\\\"bitmap/hits\\\"\" trace.txt &&\n+\n+\t\t\tgit index-pack out.pack &&\n+\n+\t\t\tlist_packed_objects out.idx >actual.raw &&\n+\t\t\tsort actual.raw >actual &&\n+\t\t\ttest_cmp expect actual || return 1\n+\t\tdone\n+\t)\n+'\n+\n test_expect_success 'incremental repack fails when bitmaps are requested' '\n \ttest_commit more-1 &&\n \ttest_must_fail git repack -d 2>err &&\n-- \n2.54.0.23.gae57607b57f\n\n"},{"id":"544559","messageId":"069c50d337002680e19eb6c35e62491c35b3becf.1780438896.git.me@ttaylorr.com","threadId":"65704","inReplyTo":"cover.1780438896.git.me@ttaylorr.com","subject":"[PATCH v2 3/4] pack-objects: extract `record_tree_depth()` helper","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2026-06-02T22:21:50Z","receivedAt":"2026-06-02T22:21:52Z","isPatch":true,"body":"Prepare for a subsequent change that needs to record tree depths from a\nsecond call site by factoring the delta-islands tree-depth bookkeeping\nout of `show_object()` and into a helper, `record_tree_depth()`.\n\nThe helper looks up the object in `to_pack`, returns early when the\nobject was not added there, computes the depth from the slash count in\nthe supplied name, and preserves the existing max-depth-wins behavior\nwhen a tree is reached by more than one path.\n\nSigned-off-by: Taylor Blau \n---\n builtin/pack-objects.c | 32 ++++++++++++++++++--------------\n 1 file changed, 18 insertions(+), 14 deletions(-)\n\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex e4dcb563b7d..ec02e2b21d2 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -2722,6 +2722,22 @@ static inline void oe_set_tree_depth(struct packing_data *pack,\n \tpack->tree_depth[e - pack->objects] = tree_depth;\n }\n \n+static void record_tree_depth(const struct object_id *oid, const char *name)\n+{\n+\tconst char *p;\n+\tunsigned depth;\n+\tstruct object_entry *ent;\n+\n+\t/* the empty string is a root tree, which is depth 0 */\n+\tdepth = *name ? 1 : 0;\n+\tfor (p = strchr(name, '/'); p; p = strchr(p + 1, '/'))\n+\t\tdepth++;\n+\n+\tent = packlist_find(&to_pack, oid);\n+\tif (ent && depth > oe_tree_depth(&to_pack, ent))\n+\t\toe_set_tree_depth(&to_pack, ent, depth);\n+}\n+\n /*\n * Return the size of the object without doing any delta\n * reconstruction (so non-deltas are true object sizes, but deltas\n@@ -4375,20 +4391,8 @@ static void show_object(struct object *obj, const char *name,\n \tadd_preferred_base_object(name);\n \tadd_object_entry(&obj->oid, obj->type, name, 0);\n \n-\tif (use_delta_islands) {\n-\t\tconst char *p;\n-\t\tunsigned depth;\n-\t\tstruct object_entry *ent;\n-\n-\t\t/* the empty string is a root tree, which is depth 0 */\n-\t\tdepth = *name ? 1 : 0;\n-\t\tfor (p = strchr(name, '/'); p; p = strchr(p + 1, '/'))\n-\t\t\tdepth++;\n-\n-\t\tent = packlist_find(&to_pack, &obj->oid);\n-\t\tif (ent && depth > oe_tree_depth(&to_pack, ent))\n-\t\t\toe_set_tree_depth(&to_pack, ent, depth);\n-\t}\n+\tif (use_delta_islands)\n+\t\trecord_tree_depth(&obj->oid, name);\n }\n \n static void show_object__ma_allow_any(struct object *obj, const char *name, void *data)\n-- \n2.54.0.23.gae57607b57f\n\n"},{"id":"544560","messageId":"ae57607b57f810ca76e926530eeb5710df2e5b80.1780438896.git.me@ttaylorr.com","threadId":"65704","inReplyTo":"cover.1780438896.git.me@ttaylorr.com","subject":"[PATCH v2 4/4] pack-objects: support `--delta-islands` with `--path-walk`","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2026-06-02T22:21:53Z","receivedAt":"2026-06-02T22:21:56Z","isPatch":true,"body":"Since the inception of `--path-walk`, this option has had a documented\nincompatibility with `--delta-islands`.\n\nWhen discussing those original patches on the list, a message from\nStolee in [1] noted the following:\n\n this could be remedied by [...] doing a separate walk to identify\n islands using the normal method\n\nIn a related portion of the thread, Peff explains[2]:\n\n The delta islands code already does its own tree walk to propagate\n the bits down (it does rely on the base walk's show_commit() to\n propagate through the commits).\n\n Once each object has its island bitmaps, I think however you\n choose to come up with delta candidates [...] you should be able\n to use it. It's fundamentally just answering the question of \"am\n I allowed to delta between these two objects\".\n\nThat is similar to what this patch does, and it turns out the cheaper\noption is sufficient: perform the same island side effects from the\npath-walk callback rather than doing a second walk.\n\nRecall how delta-islands are computed during a normal repack:\n\n - `show_commit()` calls `propagate_island_marks()` for each commit,\n which merges the commit's island bitset onto its root tree object and\n onto each of its parent commits.\n\n - `show_object()` for a tree records the tree's depth derived from the\n slash-separated pathname. Subsequent `resolve_tree_islands()` uses\n that depth to walk trees in increasing-depth order, propagating each\n tree's marks to its children.\n\n - At delta-search time, `in_same_island()` enforces that a delta\n target's island bitmap is a subset of its base's: every island that\n reaches the target must also reach the base.\n\nPath-walk's enumeration callback is `add_objects_by_path()`. It already\nadds objects to `to_pack`, but until now did not perform the\nisland-related side effects. Two things are needed:\n\n - For each commit batch, call `propagate_island_marks()` on commits,\n exactly as `show_commit()` does.\n\n We have to be careful about the order in which we call this function,\n and we must see a commit before its parents in order to have\n island marks to propagate.\n\n The path-walk batch preserves that order. Path-walk appends commits\n to its `OBJ_COMMIT` batch as they come back from the same\n `get_revision()` loop the regular traversal uses, and\n `add_objects_by_path()` iterates the batch in array order. So every\n commit reaches `propagate_island_marks()` in the same sequence that\n `show_commit()` would have seen it, and the descendant-first chain\n that the algorithm relies on is intact.\n\n Skip island propagation for excluded commits to match the regular\n traversal, whose `show_commit()` callback is only invoked for\n interesting commits. Boundary commits may still be present in\n path-walk's callback so they can serve as thin-pack bases, but they\n should not contribute island marks.\n\n - For each tree batch, record the tree's depth from the path. Use the\n `record_tree_depth()` helper from the previous commit so both\n callbacks behave identically, including the max-depth-wins behavior\n when a tree is reached via more than one path. The helper accepts\n both the `show_object()` path shape (\"foo\", \"foo/bar\") and the\n path-walk shape with a trailing slash (\"foo/\", \"foo/bar/\"), so depths\n recorded from either traversal mode are directly comparable.\n\n This is implicit in the implementation sketch from Peff above.\n `resolve_tree_islands()` sorts trees by `oe->tree_depth` in\n increasing-depth order before propagating marks down, so that a\n parent tree's marks are finalized before its children inherit them.\n Without recording the depth at path-walk time, every\n path-walk-discovered tree would land at depth 0 in `to_pack`, the\n sort would lose its ordering, and children could inherit marks from\n parents whose own contributions had not yet been merged in.\n\nWith those two pieces in place, `resolve_tree_islands()` receives the\nsame island inputs from path-walk as it would from the regular\ntraversal, so the existing island checks can be reused unchanged.\n\nDrop the documented incompatibility between `--path-walk` and\n`--delta-islands`, and add t5320 coverage for path-walk island repacks\nwith and without bitmap writing, as well as the same-island case where a\ndelta remains allowed.\n\n[1]: https://lore.kernel.org/git/9aa2471b-0850-4707-9733-d3b33609f5f2@gmail.com/\n[2]: https://lore.kernel.org/git/20240911063203.GA1538586@coredump.intra.peff.net/\n\nSigned-off-by: Taylor Blau \n---\n Documentation/git-pack-objects.adoc | 14 +++++++-------\n builtin/pack-objects.c | 22 ++++++++++++++++++----\n t/t5320-delta-islands.sh | 29 +++++++++++++++++++++++++++++\n 3 files changed, 54 insertions(+), 11 deletions(-)\n\ndiff --git a/Documentation/git-pack-objects.adoc b/Documentation/git-pack-objects.adoc\nindex 0adce8961a3..65cd00c152f 100644\n--- a/Documentation/git-pack-objects.adoc\n+++ b/Documentation/git-pack-objects.adoc\n@@ -402,13 +402,13 @@ will be automatically changed to version `1`.\n \tof filenames that cause collisions in Git's default name-hash\n \talgorithm.\n +\n-Incompatible with `--delta-islands`. When `--use-bitmap-index` is\n-specified with `--path-walk`, a successful bitmap traversal is used for\n-object enumeration, with path-walk remaining as the fallback traversal\n-when the bitmap cannot satisfy the request. The `--path-walk` option\n-supports the `--filter=` forms `blob:none`, `blob:limit=`,\n-`tree:0`, `object:type=`, and `sparse:`. These supported filter\n-types can be combined with the `combine:+` form.\n+When `--use-bitmap-index` is specified with `--path-walk`, a successful\n+bitmap traversal is used for object enumeration, with path-walk\n+remaining as the fallback traversal when the bitmap cannot satisfy the\n+request. The `--path-walk` option supports the `--filter=` forms\n+`blob:none`, `blob:limit=`, `tree:0`, `object:type=`, and\n+`sparse:`. These supported filter types can be combined with the\n+`combine:+` form.\n \n \n DELTA ISLANDS\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex ec02e2b21d2..f48ea7a888b 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -4737,13 +4737,29 @@ static int add_objects_by_path(const char *path,\n \n \t\tadd_object_entry(oid, type, path, exclude);\n \n-\t\tif (type == OBJ_COMMIT && write_bitmap_index) {\n+\t\tif (type == OBJ_COMMIT) {\n \t\t\tstruct commit *commit;\n \n+\t\t\tif (!write_bitmap_index && !use_delta_islands)\n+\t\t\t\tcontinue;\n+\n \t\t\tcommit = lookup_commit(the_repository, oid);\n \t\t\tif (!commit)\n \t\t\t\tdie(_(\"could not find commit %s\"), oid_to_hex(oid));\n-\t\t\tindex_commit_for_bitmap(commit);\n+\t\t\tif (write_bitmap_index)\n+\t\t\t\tindex_commit_for_bitmap(commit);\n+\t\t\t/*\n+\t\t\t * Skip island propagation for boundary commits.\n+\t\t\t * The regular traversal's show_commit() is only\n+\t\t\t * called for interesting commits; matching that\n+\t\t\t * here keeps path-walk from doing extra work that\n+\t\t\t * would only be a no-op anyway (boundary commits\n+\t\t\t * are not in island_marks).\n+\t\t\t */\n+\t\t\tif (use_delta_islands && !exclude)\n+\t\t\t\tpropagate_island_marks(the_repository, commit);\n+\t\t} else if (type == OBJ_TREE && use_delta_islands) {\n+\t\t\trecord_tree_depth(oid, path);\n \t\t}\n \t}\n \n@@ -5205,8 +5221,6 @@ int cmd_pack_objects(int argc,\n \t\tconst char *option = NULL;\n \t\tif (!path_walk_filter_compatible(&filter_options))\n \t\t\toption = \"--filter\";\n-\t\telse if (use_delta_islands)\n-\t\t\toption = \"--delta-islands\";\n \n \t\tif (option) {\n \t\t\twarning(_(\"cannot use %s with %s\"),\ndiff --git a/t/t5320-delta-islands.sh b/t/t5320-delta-islands.sh\nindex 2c961c70963..9b28344a0a3 100755\n--- a/t/t5320-delta-islands.sh\n+++ b/t/t5320-delta-islands.sh\n@@ -53,6 +53,35 @@ test_expect_success 'separate islands disallows delta' '\n \t! is_delta_base $two $one\n '\n \n+test_expect_success 'path-walk island repack respects islands' '\n+\tGIT_TRACE2_EVENT=\"$(pwd)/trace.path-walk-islands\" \\\n+\t\tgit -c \"pack.island=refs/heads/(.*)\" repack -adfi \\\n+\t\t--path-walk 2>err &&\n+\ttest_region pack-objects path-walk trace.path-walk-islands &&\n+\ttest_grep ! \"cannot use --delta-islands with --path-walk\" err &&\n+\t! is_delta_base $one $two &&\n+\t! is_delta_base $two $one\n+'\n+\n+test_expect_success 'path-walk island bitmap repack respects islands' '\n+\tGIT_TRACE2_EVENT=\"$(pwd)/trace.path-walk-island-bitmap\" \\\n+\t\tgit -c \"pack.island=refs/heads/(.*)\" repack -a -d -f -i -b \\\n+\t\t--path-walk 2>err &&\n+\ttest_region pack-objects path-walk trace.path-walk-island-bitmap &&\n+\ttest_path_is_file .git/objects/pack/*.bitmap &&\n+\tgit rev-list --test-bitmap --use-bitmap-index one &&\n+\ttest_grep ! \"cannot use --delta-islands with --path-walk\" err &&\n+\t! is_delta_base $one $two &&\n+\t! is_delta_base $two $one\n+'\n+\n+test_expect_success 'path-walk same island allows delta' '\n+\tGIT_TRACE2_EVENT=\"$(pwd)/trace.path-walk-same-island\" \\\n+\t\tgit -c \"pack.island=refs/heads\" repack -adfi --path-walk &&\n+\ttest_region pack-objects path-walk trace.path-walk-same-island &&\n+\tis_delta_base $one $two\n+'\n+\n test_expect_success 'same island allows delta' '\n \tgit -c \"pack.island=refs/heads\" repack -adfi &&\n \tis_delta_base $one $two\n-- \n2.54.0.23.gae57607b57f\n"},{"id":"545372","messageId":"6e4a8764-3c56-42c8-a87e-40a94c6c34e9@gmail.com","threadId":"65704","inReplyTo":"ffad584a43ebf3cb2138e8dce7daef84ab72712f.1780438896.git.me@ttaylorr.com","subject":"Re: [PATCH v2 2/4] pack-objects: support reachability bitmaps with `--path-walk`","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2026-06-12T13:03:41Z","receivedAt":"2026-06-12T13:03:44Z","isPatch":true,"body":"On 6/2/2026 6:21 PM, Taylor Blau wrote:\n\n> As a result, we can see significantly reduced pack sizes from p5311\n> before this commit:\n\nI mentioned this before, but the pack _sizes_ aren't changing in this\nexample. We are computing them more quickly, though. \n> Test HEAD^ HEAD\n> ----------------------------------------------------------------------------------\n> 5311.38: server (1 days, --path-walk) 2.56(2.52+0.03) 0.01(0.01+0.00) -99.6%\n> 5311.39: size (1 days, --path-walk) 123.9K 123.9K +0.0%\n> 5311.40: client (1 days, --path-walk) 0.00(0.01+0.00) 0.00(0.00+0.00) =\n> 5311.42: server (2 days, --path-walk) 2.57(2.52+0.05) 0.01(0.01+0.00) -99.6%\n> 5311.43: size (2 days, --path-walk) 123.9K 123.9K +0.0%\n> 5311.44: client (2 days, --path-walk) 0.00(0.00+0.00) 0.00(0.00+0.00) =\n> 5311.46: server (4 days, --path-walk) 2.58(2.51+0.07) 0.01(0.01+0.00) -99.6%\n> 5311.47: size (4 days, --path-walk) 123.9K 123.9K +0.0%\n> 5311.48: client (4 days, --path-walk) 0.00(0.00+0.00) 0.00(0.00+0.00) =\n> 5311.50: server (8 days, --path-walk) 2.58(2.53+0.04) 0.02(0.02+0.00) -99.2%\n> 5311.51: size (8 days, --path-walk) 152.4K 152.4K +0.0%\n> 5311.52: client (8 days, --path-walk) 0.00(0.01+0.00) 0.00(0.01+0.00) =\n> 5311.54: server (16 days, --path-walk) 2.58(2.52+0.05) 0.03(0.02+0.00) -98.8%\n> 5311.55: size (16 days, --path-walk) 205.3K 205.3K +0.0%\n> 5311.56: client (16 days, --path-walk) 0.01(0.01+0.00) 0.01(0.01+0.00) +0.0%\n> 5311.58: server (32 days, --path-walk) 2.59(2.53+0.06) 0.03(0.03+0.00) -98.8%\n> 5311.59: size (32 days, --path-walk) 209.3K 209.3K +0.0%\n> 5311.60: client (32 days, --path-walk) 0.01(0.02+0.00) 0.01(0.02+0.00) +0.0%\n> 5311.62: server (64 days, --path-walk) 2.70(2.76+0.06) 0.16(0.24+0.04) -94.1%\n> 5311.63: size (64 days, --path-walk) 4.1M 4.1M +0.0%\n> 5311.64: client (64 days, --path-walk) 0.44(0.50+0.02) 0.44(0.51+0.02) +0.0%\n> 5311.66: server (128 days, --path-walk) 2.88(3.20+0.05) 0.34(0.65+0.05) -88.2%\n> 5311.67: size (128 days, --path-walk) 9.0M 9.0M -0.0%\n> 5311.68: client (128 days, --path-walk) 0.93(1.22+0.07) 0.93(1.20+0.08) +0.0%\n\nSince we are testing --path-walk on both sides, the change across this\ncommit is that we are using the bitmaps for the \"counting objects\" phase\nand then potentially using the --path-walk algorithm to construct the\npackfile.\n\nThe fact that the packfile sizes are _identical_ is suspicious to me. I'd\nexpect some amount of difference here due to the change in algorithm. It's\npossible that this could be explained by the repository shape not getting\nany benefit from --path-walk because there are no name-hash collisions to\nworry about.\n\nThe one thing that might be hinting towards _some_ difference is that the\nrelative sizes are showing as both \"+0.0%\" and \"-0.0%\", so perhaps the\nexact sizes do have differences that are hidden behind the human-readable\nsizes: 4.1M -> 4.1M is +0.0% but 9.0M -> 9.0M is -0.0%.\n\n> We get the same size of output pack, but this commit allows us to do so\n> in a significantly shorter amount of time.\n\nOk, you have the correct interpretation here, just a lingering typo in\nthe earlier sentence before the table.\n\n> Intuitively, we're generating\n> the same pack (hence the unchanged 'test_size' output from run to run),\n> but varying how we get there. Before this commit, pack-objects prefers\n> '--path-walk' to '--use-bitmap-index', so we generate the output pack by\n> performing a normal '--path-walk' traversal. With this commit, we are\n> operating over a *repacked* state (that itself was done with a\n> '--path-walk' traversal), but are able to perform pack-reuse on that\n> repacked state via bitmaps.\n\nAnd I wonder if the test setup creates a situation where we are always\nreusing deltas from the underlying packfile, so the --path-walk algorithm\nisn't doing anything to help with delta compression at this point and the\ndifference in this patch is that we are replacing the object reachability\ncalculation entirely with bitmaps.\n\nI suppose what I'm really worried about is that I'm hoping to see some\nevidence from a large-scale test that demonstrates that the two algorithms\nare working in tandem in a non-trivial way. I haven't seen it yet, but I\nalso don't have evidence that they _aren't_ working together.\n\nThanks,\n-Stolee\n\n"},{"id":"545374","messageId":"849c659f-efa8-430a-bfac-0c26a3ed1aaa@gmail.com","threadId":"65704","inReplyTo":"ffad584a43ebf3cb2138e8dce7daef84ab72712f.1780438896.git.me@ttaylorr.com","subject":"Re: [PATCH v2 2/4] pack-objects: support reachability bitmaps with `--path-walk`","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2026-06-12T13:24:32Z","receivedAt":"2026-06-12T13:24:35Z","isPatch":true,"body":"On 6/2/2026 6:21 PM, Taylor Blau wrote:\n> When 'pack-objects' is invoked with '--path-walk', it prevents us from\n> using reachability bitmaps.\n\nMy earlier response focused on the _use_ of bitmaps when creating a\npackfile, but your patch also enables _writing_ bitmaps with the\n--path-walk option, which is significant and potentially more\ninteresting from my perspective: we have evidence that --path-walk\ncan produce significantly smaller packfiles than the standard\nalgorithm, and once those packfiles are created we can benefit from\nthat size in later packfile creation steps by reusing those deltas.\n\nIn this sense, I think the _writing_ is more important during a\nrepack scenario. The fetch/clone scenarios can benefit directly even\nwithout integrating --path-walk with --use-bitmap-indexes.\n\n> * A path-walk repack that writes bitmaps does not give the bitmap\n> selector any commits, because path-walk reveals commits through\n> `add_objects_by_path()` rather than through `show_commit()`, where\n> `index_commit_for_bitmap()` is normally called.\n\n...\n\n> * On the writing side: teach the path-walk object callback to call\n> `index_commit_for_bitmap()` for commits that it adds to the pack.\n> That gives the bitmap selector the commit candidates it would have\n> seen from the regular traversal.\n\nMy earlier reply to this patch was focused on the performance results\nwhen using the \"reading bitmaps\" case, and I expressed suspicion about\nthe \"exact\" sizes of the packfiles.\n\nEven more important here is that we have demonstrated examples of repos\nthat change their packfile size when using the --path-walk method. We\nshould demonstrate that the size continues to shrink with --path-walk\neven when producing a matching .bitmap file with --write-bitmap-index.\n\nThe other thing that I notice here is that the bitmaps will need to\ncompute their reachable object set independently from the path-walk\nalgorithm. But I suppose that already happens separately from the\nrevision-walk approach that normally produces the packfile contents.\n\nNote: A lot of my thoughts around asking for more evidence here is\nthat this patch seems suspiciously simple for integrating two\ncomplicated features. The test suite (especially with\nGIT_TEST_PACK_PATH_WALK=1) helps to guarantee that the result is\n_correct_, but with performance features like this it's not enough to\n\"just\" be correct. I want to see that we're having the intended\nresults.\n\nFrom my perspective, the point of integrating these two things are:\n\n1. Reachability bitmaps make it much faster to discover the reachable\n set and reuse bits of existing packfiles. (Your performance table\n demonstrates this is true.)\n\n2. The --path-walk option can shrink packfile sizes by grouping\n trees and blobs by path before those paths collide in the name-hash\n sort. (I haven't seen evidence that this is happening.)\n\nWith evidence of (1) and not (2), it's not clear from the data that\nthese features are integrating completely. Without looking at the\ncode, those numbers would be the same if we had instead swapped the\npreference of \"the --path-walk option disables bitmaps\" to \"bitmaps\ndisable --path-walk\".\n\nFinally, I'll just note that I don't expect the _bitmaps_ to change\nsize dramatically. The --path-walk option does change the order of\nthe objects for its first pass of delta compression, but then uses\nthe (name-hash, size) sort to finalize the object ordering, so the\nfinal object ordering _should_ be the same (unless I'm mistaken, in\nwhich case the bitmaps could change size due to bitmap compression\nconcerns).\n\nThanks,\n-Stolee\n\n\n"},{"id":"545612","messageId":"xmqqjyrzbjyf.fsf@gitster.g","threadId":"65704","inReplyTo":"ffad584a43ebf3cb2138e8dce7daef84ab72712f.1780438896.git.me@ttaylorr.com","subject":"Re: [PATCH v2 2/4] pack-objects: support reachability bitmaps with `--path-walk`","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2026-06-15T20:57:28Z","receivedAt":"2026-06-15T20:57:31Z","isPatch":true,"body":"Taylor Blau writes:\n\n> diff --git a/t/t5310-pack-bitmaps.sh b/t/t5310-pack-bitmaps.sh\n> index f693cb56691..69c5da1580a 100755\n> --- a/t/t5310-pack-bitmaps.sh\n> +++ b/t/t5310-pack-bitmaps.sh\n> ...\n> +\t\tfor reuse in true false\n> +\t\tdo\n> +\t\t\t: >trace.txt &&\n> +\n> +\t\t\tGIT_TRACE2_EVENT=\"$(pwd)/trace.txt\" \\\n> +\t\t\tgit -c pack.allowPackReuse=$reuse pack-objects \\\n> +\t\t\t\t--stdout --revs --path-walk --use-bitmap-index \\\n> +\t\t\t\tout.pack &&\n> +\t\t\tgrep \"\\\"category\\\":\\\"bitmap\\\",\\\"key\\\":\\\"bitmap/hits\\\"\" trace.txt &&\n\nThis gets flagged by updated test linter X-<. Use test_grep to\npacify it.\n\n"},{"id":"545955","messageId":"ajVNQYo9ntbKyPvB@nand.local","threadId":"65704","inReplyTo":"xmqqjyrzbjyf.fsf@gitster.g","subject":"Re: [PATCH v2 2/4] pack-objects: support reachability bitmaps with `--path-walk`","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2026-06-19T14:08:01Z","receivedAt":"2026-06-19T14:08:04Z","isPatch":true,"body":"On Mon, Jun 15, 2026 at 01:57:28PM -0700, Junio C Hamano wrote:\n> Taylor Blau writes:\n>\n> > diff --git a/t/t5310-pack-bitmaps.sh b/t/t5310-pack-bitmaps.sh\n> > index f693cb56691..69c5da1580a 100755\n> > --- a/t/t5310-pack-bitmaps.sh\n> > +++ b/t/t5310-pack-bitmaps.sh\n> > ...\n> > +\t\tfor reuse in true false\n> > +\t\tdo\n> > +\t\t\t: >trace.txt &&\n> > +\n> > +\t\t\tGIT_TRACE2_EVENT=\"$(pwd)/trace.txt\" \\\n> > +\t\t\tgit -c pack.allowPackReuse=$reuse pack-objects \\\n> > +\t\t\t\t--stdout --revs --path-walk --use-bitmap-index \\\n> > +\t\t\t\tout.pack &&\n> > +\t\t\tgrep \"\\\"category\\\":\\\"bitmap\\\",\\\"key\\\":\\\"bitmap/hits\\\"\" trace.txt &&\n>\n> This gets flagged by updated test linter X-<. Use test_grep to\n> pacify it.\n\nOops, thanks for spotting.\n\nThanks,\nTaylor\n"},{"id":"545956","messageId":"ajVPJGXuhugDcT+A@nand.local","threadId":"65704","inReplyTo":"6e4a8764-3c56-42c8-a87e-40a94c6c34e9@gmail.com","subject":"Re: [PATCH v2 2/4] pack-objects: support reachability bitmaps with `--path-walk`","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2026-06-19T14:16:04Z","receivedAt":"2026-06-19T14:16:07Z","isPatch":true,"body":"On Fri, Jun 12, 2026 at 09:03:41AM -0400, Derrick Stolee wrote:\n> On 6/2/2026 6:21 PM, Taylor Blau wrote:\n>\n> > As a result, we can see significantly reduced pack sizes from p5311\n> > before this commit:\n>\n> I mentioned this before, but the pack _sizes_ aren't changing in this\n> example. We are computing them more quickly, though.\n\nThanks for pointing this out. The paragraph following the perf output\nbelow correctly explains the results (\"We get the same size of output\npack, but [...]\"), but this one is obviously wrong.\n\n> Since we are testing --path-walk on both sides, the change across this\n> commit is that we are using the bitmaps for the \"counting objects\" phase\n> and then potentially using the --path-walk algorithm to construct the\n> packfile.\n\nI'm not sure I agree here. Because we are using bitmaps, we're relying\non pack-reuse to construct the output pack, not --path-walk. I mentioned\nin git-pack-objects(1), but the combination of seeing \"--path-walk\" and\n\"--use-bitmap-index\" together only means that we will use a path-walk\ntraversal as fallback if we can't get an answer by relying on bitmaps.\n\n> And I wonder if the test setup creates a situation where we are always\n> reusing deltas from the underlying packfile, so the --path-walk algorithm\n> isn't doing anything to help with delta compression at this point and the\n> difference in this patch is that we are replacing the object reachability\n> calculation entirely with bitmaps.\n>\n> I suppose what I'm really worried about is that I'm hoping to see some\n> evidence from a large-scale test that demonstrates that the two algorithms\n> are working in tandem in a non-trivial way. I haven't seen it yet, but I\n> also don't have evidence that they _aren't_ working together.\n\nYour thinking is correct here that the test setup intentionally creates\na situation where we are reusing objects/deltas verbatim from the\nbitmapped pack.\n\nI'm not sure what \"working in tandem\" means here. At read time, the two\noptions mutually exclude one another, meaning we'll use bitmaps if we\nhave them, or do a path-walk traversal otherwise (or if the bitmaps we\nhave are somehow insufficient to perform the traversal).\n\nThe goal of this patch is not to demonstrate that the two work together\nat the same time, but rather that we can write a pack using --path-walk,\nand generate reachability bitmaps simultaneously.\n\nLet me know if you have more thoughts on what \"working together in a\nnon-trivial\" way would look like here. If there are ways to improve the\ncompatibility of these two features in a way that yields better\nperformance via either smaller packs, faster generation, or both, I'm\nall ears :-).\n\nThanks,\nTaylor\n"},{"id":"545957","messageId":"ajVSHvL+On9AEV+g@nand.local","threadId":"65704","inReplyTo":"849c659f-efa8-430a-bfac-0c26a3ed1aaa@gmail.com","subject":"Re: [PATCH v2 2/4] pack-objects: support reachability bitmaps with `--path-walk`","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2026-06-19T14:28:46Z","receivedAt":"2026-06-19T14:28:49Z","isPatch":true,"body":"On Fri, Jun 12, 2026 at 09:24:32AM -0400, Derrick Stolee wrote:\n> On 6/2/2026 6:21 PM, Taylor Blau wrote:\n> > When 'pack-objects' is invoked with '--path-walk', it prevents us from\n> > using reachability bitmaps.\n>\n> My earlier response focused on the _use_ of bitmaps when creating a\n> packfile, but your patch also enables _writing_ bitmaps with the\n> --path-walk option, which is significant and potentially more\n> interesting from my perspective: we have evidence that --path-walk\n> can produce significantly smaller packfiles than the standard\n> algorithm, and once those packfiles are created we can benefit from\n> that size in later packfile creation steps by reusing those deltas.\n\nI am perhaps splitting hairs here, but I would frame the use of bitmaps\nwhen reading with \"--path-walk\" as \"either/or\" not \"both/and\". The main\ngoal of this patch is to enable us to still generate bitmaps when\n*writing* a pack with \"--path-walk\".\n\n> Even more important here is that we have demonstrated examples of repos\n> that change their packfile size when using the --path-walk method. We\n> should demonstrate that the size continues to shrink with --path-walk\n> even when producing a matching .bitmap file with --write-bitmap-index.\n\nThat's fair. One way to do this would be to:\n\n--- 8< ---\ndiff --git a/t/perf/p5311-pack-bitmaps-fetch.sh b/t/perf/p5311-pack-bitmaps-fetch.sh\nindex 1b115d921a1..c1aed3e2aef 100755\n--- a/t/perf/p5311-pack-bitmaps-fetch.sh\n+++ b/t/perf/p5311-pack-bitmaps-fetch.sh\n@@ -18,6 +18,10 @@ test_fetch_bitmaps () {\n \t\tgit repack -ad $argv\n \t'\n\n+\ttest_size \"size of bitmapped pack ${argv:+($argv)}\" '\n+\t\ttest_file_size .git/objects/pack/pack-*.pack\n+\t'\n+\n \t# simulate a fetch from a repository that last fetched N days ago, for\n \t# various values of N. We do so by following the first-parent chain,\n \t# and assume the first entry in the chain that is N days older than the current\n--- >8 ---\n\n, which gives us:\n\n Test HEAD^ HEAD\n ----------------------------------------------------------------------------------------\n 5311.3: size of bitmapped pack 278.8M 278.8M -0.0%\n 5311.38: size of bitmapped pack (--path-walk) 278.7M 278.7M +0.0%\n\n(eliding other tests). I considered whether there are other interesting\ntests, but I think \"repack\" is the right layer to run perf tests, since\nyou're always writing a closed pack. We could try different subsets of\nthe repository's objects (which would also have to be closed), but I\ndon't think this is that interesting.\n\n> The other thing that I notice here is that the bitmaps will need to\n> compute their reachable object set independently from the path-walk\n> algorithm. But I suppose that already happens separately from the\n> revision-walk approach that normally produces the packfile contents.\n\nRight. The only wrinkle here is how we handle the internal traversal's\n\"--boundary\" option, but see the last paragraph in the commit message\nfor details on why the proposed approach is OK.\n\n> >From my perspective, the point of integrating these two things are:\n>\n> 1. Reachability bitmaps make it much faster to discover the reachable\n> set and reuse bits of existing packfiles. (Your performance table\n> demonstrates this is true.)\n>\n> 2. The --path-walk option can shrink packfile sizes by grouping\n> trees and blobs by path before those paths collide in the name-hash\n> sort. (I haven't seen evidence that this is happening.)\n>\n> With evidence of (1) and not (2), it's not clear from the data that\n> these features are integrating completely. Without looking at the\n> code, those numbers would be the same if we had instead swapped the\n> preference of \"the --path-walk option disables bitmaps\" to \"bitmaps\n> disable --path-walk\".\n\nLet me know if modifying the perf test as above (and including the\nrelevant results in the commit message) would be sufficient in\naddressing your concern.\n\nThanks,\nTaylor\n"},{"id":"545959","messageId":"ec45260a-1d4e-49d1-9aa8-9ec94ecd9b23@gmail.com","threadId":"65704","inReplyTo":"ajVPJGXuhugDcT+A@nand.local","subject":"Re: [PATCH v2 2/4] pack-objects: support reachability bitmaps with `--path-walk`","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2026-06-19T14:36:54Z","receivedAt":"2026-06-19T14:36:56Z","isPatch":true,"body":"On 6/19/2026 10:16 AM, Taylor Blau wrote:\n> On Fri, Jun 12, 2026 at 09:03:41AM -0400, Derrick Stolee wrote:\n>> On 6/2/2026 6:21 PM, Taylor Blau wrote:\n>>\n>>> As a result, we can see significantly reduced pack sizes from p5311\n>>> before this commit:\n>>\n>> I mentioned this before, but the pack _sizes_ aren't changing in this\n>> example. We are computing them more quickly, though.\n> \n> Thanks for pointing this out. The paragraph following the perf output\n> below correctly explains the results (\"We get the same size of output\n> pack, but [...]\"), but this one is obviously wrong.\n> \n>> Since we are testing --path-walk on both sides, the change across this\n>> commit is that we are using the bitmaps for the \"counting objects\" phase\n>> and then potentially using the --path-walk algorithm to construct the\n>> packfile.\n> \n> I'm not sure I agree here. Because we are using bitmaps, we're relying\n> on pack-reuse to construct the output pack, not --path-walk. I mentioned\n> in git-pack-objects(1), but the combination of seeing \"--path-walk\" and\n> \"--use-bitmap-index\" together only means that we will use a path-walk\n> traversal as fallback if we can't get an answer by relying on bitmaps.\nI guess my thought was that we'd construct bitmaps when they are\navailable, but how do we walk objects to get the objects for commits\nthat are not represented by bitmaps?\n\nBut you make a good point: we don't need to do that for functional\nuse: the bitmap code does an object walk to produce a bitmap, and it's\nall in a layer \"below\" the pack-objects code.\n\nSo essentially, this _isn't_ a combined approach: it's \"use bitmaps if\nwe can, and fall back to --path-walk if we can't\" which is changing\nfrom our previous behavior of \"--path-walk means we don't try to use\nbitmaps\".\n\nThanks,\n-Stolee\n\n"},{"id":"545960","messageId":"131d7ad3-7791-4d6f-bdf3-afa6b0831a71@gmail.com","threadId":"65704","inReplyTo":"ajVSHvL+On9AEV+g@nand.local","subject":"Re: [PATCH v2 2/4] pack-objects: support reachability bitmaps with `--path-walk`","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2026-06-19T14:40:51Z","receivedAt":"2026-06-19T14:40:54Z","isPatch":true,"body":"On 6/19/2026 10:28 AM, Taylor Blau wrote:\n> On Fri, Jun 12, 2026 at 09:24:32AM -0400, Derrick Stolee wrote:\n>> On 6/2/2026 6:21 PM, Taylor Blau wrote:\n>>> When 'pack-objects' is invoked with '--path-walk', it prevents us from\n>>> using reachability bitmaps.\n>>\n>> My earlier response focused on the _use_ of bitmaps when creating a\n>> packfile, but your patch also enables _writing_ bitmaps with the\n>> --path-walk option, which is significant and potentially more\n>> interesting from my perspective: we have evidence that --path-walk\n>> can produce significantly smaller packfiles than the standard\n>> algorithm, and once those packfiles are created we can benefit from\n>> that size in later packfile creation steps by reusing those deltas.\n> \n> I am perhaps splitting hairs here, but I would frame the use of bitmaps\n> when reading with \"--path-walk\" as \"either/or\" not \"both/and\". The main\n> goal of this patch is to enable us to still generate bitmaps when\n> *writing* a pack with \"--path-walk\".\n\nYes. I was confused but your response to the earlier thread made this\nmore clear. I'm no longer confused. \n>> Even more important here is that we have demonstrated examples of repos\n>> that change their packfile size when using the --path-walk method. We\n>> should demonstrate that the size continues to shrink with --path-walk\n>> even when producing a matching .bitmap file with --write-bitmap-index.\n> \n> That's fair. One way to do this would be to:\n> \n> --- 8< ---\n> diff --git a/t/perf/p5311-pack-bitmaps-fetch.sh b/t/perf/p5311-pack-bitmaps-fetch.sh\n> index 1b115d921a1..c1aed3e2aef 100755\n> --- a/t/perf/p5311-pack-bitmaps-fetch.sh\n> +++ b/t/perf/p5311-pack-bitmaps-fetch.sh\n> @@ -18,6 +18,10 @@ test_fetch_bitmaps () {\n> \t\tgit repack -ad $argv\n> \t'\n> \n> +\ttest_size \"size of bitmapped pack ${argv:+($argv)}\" '\n> +\t\ttest_file_size .git/objects/pack/pack-*.pack\n> +\t'\n> +\n> \t# simulate a fetch from a repository that last fetched N days ago, for\n> \t# various values of N. We do so by following the first-parent chain,\n> \t# and assume the first entry in the chain that is N days older than the current\n> --- >8 ---\n> \n> , which gives us:\n> \n> Test HEAD^ HEAD\n> ----------------------------------------------------------------------------------------\n> 5311.3: size of bitmapped pack 278.8M 278.8M -0.0%\n> 5311.38: size of bitmapped pack (--path-walk) 278.7M 278.7M +0.0%\n> \n> (eliding other tests). I considered whether there are other interesting\n> tests, but I think \"repack\" is the right layer to run perf tests, since\n> you're always writing a closed pack. We could try different subsets of\n> the repository's objects (which would also have to be closed), but I\n> don't think this is that interesting.\n\nThis sort of thing does help to show that we're getting different\nbehavior when repacking with and without --path-walk. And this test\nis showing the slightest change for git.git, but is likely more\nimpactful for the other repos I've used to demonstrate the benefits.\n\nSo this is the kind of data I'm hoping to see, but also with data\nfrom other repos whose data shapes benefit from --path-walk more\nthan git.git and repos where name-hash v1 is sufficient to give a\nsimilar result.\n\nI'd also like to see if the repack _time_ changes with this, but\nthese direct size comparisons are the biggest indicator I'd like to\nsee.\n\n>> The other thing that I notice here is that the bitmaps will need to\n>> compute their reachable object set independently from the path-walk\n>> algorithm. But I suppose that already happens separately from the\n>> revision-walk approach that normally produces the packfile contents.\n> \n> Right. The only wrinkle here is how we handle the internal traversal's\n> \"--boundary\" option, but see the last paragraph in the commit message\n> for details on why the proposed approach is OK.\n> \n>> >From my perspective, the point of integrating these two things are:\n>>\n>> 1. Reachability bitmaps make it much faster to discover the reachable\n>> set and reuse bits of existing packfiles. (Your performance table\n>> demonstrates this is true.)\n>>\n>> 2. The --path-walk option can shrink packfile sizes by grouping\n>> trees and blobs by path before those paths collide in the name-hash\n>> sort. (I haven't seen evidence that this is happening.)\n>>\n>> With evidence of (1) and not (2), it's not clear from the data that\n>> these features are integrating completely. Without looking at the\n>> code, those numbers would be the same if we had instead swapped the\n>> preference of \"the --path-walk option disables bitmaps\" to \"bitmaps\n>> disable --path-walk\".\n> \n> Let me know if modifying the perf test as above (and including the\n> relevant results in the commit message) would be sufficient in\n> addressing your concern.\nYes, the perf test modification and data reporting is the only\nmissing thing at this point. You've helped me better understand the\n\"integration\" between the features during fetches and clones.\n\nThanks,\n-Stolee\n"},{"id":"545961","messageId":"ajVWYdTThVic+O+f@nand.local","threadId":"65704","inReplyTo":"ec45260a-1d4e-49d1-9aa8-9ec94ecd9b23@gmail.com","subject":"Re: [PATCH v2 2/4] pack-objects: support reachability bitmaps with `--path-walk`","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2026-06-19T14:46:57Z","receivedAt":"2026-06-19T14:47:00Z","isPatch":true,"body":"On Fri, Jun 19, 2026 at 10:36:54AM -0400, Derrick Stolee wrote:\n> On 6/19/2026 10:16 AM, Taylor Blau wrote:\n> > On Fri, Jun 12, 2026 at 09:03:41AM -0400, Derrick Stolee wrote:\n> >> On 6/2/2026 6:21 PM, Taylor Blau wrote:\n> >>\n> >>> As a result, we can see significantly reduced pack sizes from p5311\n> >>> before this commit:\n> >>\n> >> I mentioned this before, but the pack _sizes_ aren't changing in this\n> >> example. We are computing them more quickly, though.\n> >\n> > Thanks for pointing this out. The paragraph following the perf output\n> > below correctly explains the results (\"We get the same size of output\n> > pack, but [...]\"), but this one is obviously wrong.\n> >\n> >> Since we are testing --path-walk on both sides, the change across this\n> >> commit is that we are using the bitmaps for the \"counting objects\" phase\n> >> and then potentially using the --path-walk algorithm to construct the\n> >> packfile.\n> >\n> > I'm not sure I agree here. Because we are using bitmaps, we're relying\n> > on pack-reuse to construct the output pack, not --path-walk. I mentioned\n> > in git-pack-objects(1), but the combination of seeing \"--path-walk\" and\n> > \"--use-bitmap-index\" together only means that we will use a path-walk\n> > traversal as fallback if we can't get an answer by relying on bitmaps.\n>\n> I guess my thought was that we'd construct bitmaps when they are\n> available, but how do we walk objects to get the objects for commits\n> that are not represented by bitmaps?\n\nGood question, and we use the existing bitmap traversal (or the\nboundary-based one, if enabled). In that case we really want something\nthat is topological and not path-based, so we can terminate the walk as\nsoon as we run into an existing set bit, or something on the negated\nside of the query.\n\n> But you make a good point: we don't need to do that for functional\n> use: the bitmap code does an object walk to produce a bitmap, and it's\n> all in a layer \"below\" the pack-objects code.\n>\n> So essentially, this _isn't_ a combined approach: it's \"use bitmaps if\n> we can, and fall back to --path-walk if we can't\" which is changing\n> from our previous behavior of \"--path-walk means we don't try to use\n> bitmaps\".\n\nExactly!\n\nThanks,\nTaylor\n"},{"id":"545962","messageId":"ajVXlcHgIF2XkmMQ@nand.local","threadId":"65704","inReplyTo":"131d7ad3-7791-4d6f-bdf3-afa6b0831a71@gmail.com","subject":"Re: [PATCH v2 2/4] pack-objects: support reachability bitmaps with `--path-walk`","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2026-06-19T14:52:05Z","receivedAt":"2026-06-19T14:52:08Z","isPatch":true,"body":"On Fri, Jun 19, 2026 at 10:40:51AM -0400, Derrick Stolee wrote:\n> > [...]\n> > , which gives us:\n> >\n> > Test HEAD^ HEAD\n> > ----------------------------------------------------------------------------------------\n> > 5311.3: size of bitmapped pack 278.8M 278.8M -0.0%\n> > 5311.38: size of bitmapped pack (--path-walk) 278.7M 278.7M +0.0%\n> >\n> > (eliding other tests). I considered whether there are other interesting\n> > tests, but I think \"repack\" is the right layer to run perf tests, since\n> > you're always writing a closed pack. We could try different subsets of\n> > the repository's objects (which would also have to be closed), but I\n> > don't think this is that interesting.\n>\n> This sort of thing does help to show that we're getting different\n> behavior when repacking with and without --path-walk. And this test\n> is showing the slightest change for git.git, but is likely more\n> impactful for the other repos I've used to demonstrate the benefits.\n>\n> So this is the kind of data I'm hoping to see, but also with data\n> from other repos whose data shapes benefit from --path-walk more\n> than git.git and repos where name-hash v1 is sufficient to give a\n> similar result.\n\nI'm glad this is the sort of data you're looking for. I'm happy to run\nthis on other repositories.\n\n> I'd also like to see if the repack _time_ changes with this, but\n> these direct size comparisons are the biggest indicator I'd like to\n> see.\n\nUnfortunately a timing comparison is kind of a pain here. We'd have to\nuse test_perf, which will perform the same repack multiple times. We\ncould do that, though it's wasteful, and changes like bf4a60874af\n(p5326: generate pack bitmaps before writing the MIDX bitmap,\n2021-09-17) move us in the opposite direction.\n\nI'm not opposed to changing this to test_perf if you feel strongly about\nit.\n\nThanks,\nTaylor\n"},{"id":"545978","messageId":"7afdaf77-07f5-4d48-955d-e153d148f647@gmail.com","threadId":"65704","inReplyTo":"ajVXlcHgIF2XkmMQ@nand.local","subject":"Re: [PATCH v2 2/4] pack-objects: support reachability bitmaps with `--path-walk`","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2026-06-19T15:33:47Z","receivedAt":"2026-06-19T15:33:49Z","isPatch":true,"body":"On 6/19/2026 10:52 AM, Taylor Blau wrote:\n> On Fri, Jun 19, 2026 at 10:40:51AM -0400, Derrick Stolee wrote:\n>>> [...]\n>>> , which gives us:\n>>>\n>>> Test HEAD^ HEAD\n>>> ----------------------------------------------------------------------------------------\n>>> 5311.3: size of bitmapped pack 278.8M 278.8M -0.0%\n>>> 5311.38: size of bitmapped pack (--path-walk) 278.7M 278.7M +0.0%\n>>>\n>>> (eliding other tests). I considered whether there are other interesting\n>>> tests, but I think \"repack\" is the right layer to run perf tests, since\n>>> you're always writing a closed pack. We could try different subsets of\n>>> the repository's objects (which would also have to be closed), but I\n>>> don't think this is that interesting.\n>>\n>> This sort of thing does help to show that we're getting different\n>> behavior when repacking with and without --path-walk. And this test\n>> is showing the slightest change for git.git, but is likely more\n>> impactful for the other repos I've used to demonstrate the benefits.\n>>\n>> So this is the kind of data I'm hoping to see, but also with data\n>> from other repos whose data shapes benefit from --path-walk more\n>> than git.git and repos where name-hash v1 is sufficient to give a\n>> similar result.\n> \n> I'm glad this is the sort of data you're looking for. I'm happy to run\n> this on other repositories.\n> \n>> I'd also like to see if the repack _time_ changes with this, but\n>> these direct size comparisons are the biggest indicator I'd like to\n>> see.\n> \n> Unfortunately a timing comparison is kind of a pain here. We'd have to\n> use test_perf, which will perform the same repack multiple times. We\n> could do that, though it's wasteful, and changes like bf4a60874af\n> (p5326: generate pack bitmaps before writing the MIDX bitmap,\n> 2021-09-17) move us in the opposite direction.\n> \n> I'm not opposed to changing this to test_perf if you feel strongly about\n> it.\nRepacking is expensive and time-consuming. I care a bit about it,\nbut not as much as I care about the size difference. Feel free to\nskip the time performance impact for now.\n\nThanks,\n-Stolee\n\n"},{"id":"546096","messageId":"cover.1782082975.git.me@ttaylorr.com","threadId":"65704","inReplyTo":"cover.1779923907.git.me@ttaylorr.com","subject":"[PATCH v3 0/4] pack-objects: support bitmaps and delta-islands with `--path-walk`","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2026-06-21T23:02:55Z","receivedAt":"2026-06-21T23:02:58Z","isPatch":true,"body":"Note to the maintainer:\n\n * This series is still based on 'ds/path-walk-filters' with Patrick's\n 'ps/clang-w-glibc-2.43-and-_Generic' merged in.\n\nHere is another small reroll of my series to make `--path-walk` work\nwith reachability bitmaps and delta-islands.\n\nThis round addresses Stolee's request to demonstrate the repack-size\nside of the integration between `--path-walk` and bitmap writing, and\nfixes an errant \"grep\" in the test suite.\n\nChanges since v2 include:\n\n * p5311 now forces a fresh repack with '-F' when building its bitmapped\n test repository. This avoids reusing deltas from a non-'--path-walk'\n pack when we are trying to measure a pack produced by `--path-walk`.\n\n * p5311 now records the size of the bitmapped pack, both with and\n without `--path-walk`, to show that writing bitmaps during a\n `--path-walk` repack does not lose the pack-size improvement that\n `--path-walk` provides in repositories where it helps.\n\n * The second patch's commit message has updated p5311 numbers from a\n recent fluentui clone, fixing the \"pack sizes\" typo and documenting\n the new bitmapped-pack-size comparison.\n\n * The t5310 grep assertion now uses `test_grep`, as suggested by Junio.\n\nOutside of the above, the series is functionally unchanged.\n\nThanks in advance for another look.\n\nTaylor Blau (4):\n t/perf: drop p5311's lookup-table permutation\n pack-objects: support reachability bitmaps with `--path-walk`\n pack-objects: extract `record_tree_depth()` helper\n pack-objects: support `--delta-islands` with `--path-walk`\n\n Documentation/git-pack-objects.adoc | 12 ++---\n builtin/pack-objects.c | 68 +++++++++++++++++++++--------\n t/perf/p5311-pack-bitmaps-fetch.sh | 24 ++++++----\n t/t5310-pack-bitmaps.sh | 36 +++++++++++++++\n t/t5320-delta-islands.sh | 29 ++++++++++++\n 5 files changed, 138 insertions(+), 31 deletions(-)\n\nRange-diff against v2:\n1: 52d63e8910e = 1: b1dbf30ddbe t/perf: drop p5311's lookup-table permutation\n2: ffad584a43e ! 2: 1884f495809 pack-objects: support reachability bitmaps with `--path-walk`\n @@ Commit message\n bitmap can answer the request, use it; otherwise fall back to\n path-walk's own enumeration.\n \n - As a result, we can see significantly reduced pack sizes from p5311\n - before this commit:\n + As a result, we can see significantly reduced pack generation times from\n + p5311 (with our `GIT_PERF_REPO` set to a recent clone of the fluentui\n + repository) before this commit:\n \n - Test HEAD^ HEAD\n - ----------------------------------------------------------------------------------\n - 5311.38: server (1 days, --path-walk) 2.56(2.52+0.03) 0.01(0.01+0.00) -99.6%\n - 5311.39: size (1 days, --path-walk) 123.9K 123.9K +0.0%\n - 5311.40: client (1 days, --path-walk) 0.00(0.01+0.00) 0.00(0.00+0.00) =\n - 5311.42: server (2 days, --path-walk) 2.57(2.52+0.05) 0.01(0.01+0.00) -99.6%\n - 5311.43: size (2 days, --path-walk) 123.9K 123.9K +0.0%\n - 5311.44: client (2 days, --path-walk) 0.00(0.00+0.00) 0.00(0.00+0.00) =\n - 5311.46: server (4 days, --path-walk) 2.58(2.51+0.07) 0.01(0.01+0.00) -99.6%\n - 5311.47: size (4 days, --path-walk) 123.9K 123.9K +0.0%\n - 5311.48: client (4 days, --path-walk) 0.00(0.00+0.00) 0.00(0.00+0.00) =\n - 5311.50: server (8 days, --path-walk) 2.58(2.53+0.04) 0.02(0.02+0.00) -99.2%\n - 5311.51: size (8 days, --path-walk) 152.4K 152.4K +0.0%\n - 5311.52: client (8 days, --path-walk) 0.00(0.01+0.00) 0.00(0.01+0.00) =\n - 5311.54: server (16 days, --path-walk) 2.58(2.52+0.05) 0.03(0.02+0.00) -98.8%\n - 5311.55: size (16 days, --path-walk) 205.3K 205.3K +0.0%\n - 5311.56: client (16 days, --path-walk) 0.01(0.01+0.00) 0.01(0.01+0.00) +0.0%\n - 5311.58: server (32 days, --path-walk) 2.59(2.53+0.06) 0.03(0.03+0.00) -98.8%\n - 5311.59: size (32 days, --path-walk) 209.3K 209.3K +0.0%\n - 5311.60: client (32 days, --path-walk) 0.01(0.02+0.00) 0.01(0.02+0.00) +0.0%\n - 5311.62: server (64 days, --path-walk) 2.70(2.76+0.06) 0.16(0.24+0.04) -94.1%\n - 5311.63: size (64 days, --path-walk) 4.1M 4.1M +0.0%\n - 5311.64: client (64 days, --path-walk) 0.44(0.50+0.02) 0.44(0.51+0.02) +0.0%\n - 5311.66: server (128 days, --path-walk) 2.88(3.20+0.05) 0.34(0.65+0.05) -88.2%\n - 5311.67: size (128 days, --path-walk) 9.0M 9.0M -0.0%\n - 5311.68: client (128 days, --path-walk) 0.93(1.22+0.07) 0.93(1.20+0.08) +0.0%\n + Test HEAD^ HEAD\n + ----------------------------------------------------------------------------------------\n + 5311.40: server (1 days, --path-walk) 1.43(1.39+0.04) 0.01(0.01+0.00) -99.3%\n + 5311.41: size (1 days, --path-walk) 139.6K 139.7K +0.0%\n + 5311.42: client (1 days, --path-walk) 0.02(0.02+0.00) 0.02(0.02+0.00) +0.0%\n + 5311.44: server (2 days, --path-walk) 1.43(1.39+0.04) 0.01(0.00+0.00) -99.3%\n + 5311.45: size (2 days, --path-walk) 139.6K 139.7K +0.0%\n + 5311.46: client (2 days, --path-walk) 0.02(0.02+0.00) 0.02(0.02+0.00) +0.0%\n + 5311.48: server (4 days, --path-walk) 1.44(1.39+0.04) 0.01(0.01+0.00) -99.3%\n + 5311.49: size (4 days, --path-walk) 238.1K 238.1K +0.0%\n + 5311.50: client (4 days, --path-walk) 0.03(0.03+0.00) 0.03(0.03+0.00) +0.0%\n + 5311.52: server (8 days, --path-walk) 1.43(1.39+0.03) 0.01(0.00+0.00) -99.3%\n + 5311.53: size (8 days, --path-walk) 344.9K 344.9K +0.0%\n + 5311.54: client (8 days, --path-walk) 0.07(0.07+0.00) 0.07(0.08+0.00) +0.0%\n + 5311.56: server (16 days, --path-walk) 1.47(1.44+0.03) 0.10(0.08+0.01) -93.2%\n + 5311.57: size (16 days, --path-walk) 844.0K 844.0K +0.0%\n + 5311.58: client (16 days, --path-walk) 0.09(0.09+0.00) 0.09(0.09+0.00) +0.0%\n + 5311.60: server (32 days, --path-walk) 1.52(1.50+0.05) 0.14(0.15+0.02) -90.8%\n + 5311.61: size (32 days, --path-walk) 4.2M 4.2M +0.1%\n + 5311.62: client (32 days, --path-walk) 0.34(0.48+0.02) 0.34(0.45+0.05) +0.0%\n + 5311.64: server (64 days, --path-walk) 1.55(1.52+0.06) 0.15(0.15+0.04) -90.3%\n + 5311.65: size (64 days, --path-walk) 6.4M 6.4M -0.0%\n + 5311.66: client (64 days, --path-walk) 0.51(0.79+0.05) 0.51(0.80+0.06) +0.0%\n + 5311.68: server (128 days, --path-walk) 1.59(1.57+0.06) 0.16(0.21+0.01) -89.9%\n + 5311.69: size (128 days, --path-walk) 8.4M 8.4M -0.0%\n + 5311.70: client (128 days, --path-walk) 0.72(1.44+0.08) 0.71(1.47+0.09) -1.4%\n \n We get the same size of output pack, but this commit allows us to do so\n in a significantly shorter amount of time. Intuitively, we're generating\n @@ Commit message\n '--path-walk' traversal), but are able to perform pack-reuse on that\n repacked state via bitmaps.\n \n + When comparing the size of the repacked pack with/without '--path-walk'\n + on the previous commit versus this one, we see that (a) the repacked size\n + improves significantly with '--path-walk', and that (b) writing bitmaps\n + during repacking does not regress this improvement:\n +\n + Test HEAD^ HEAD\n + ----------------------------------------------------------------------------------------\n + 5311.3: size of bitmapped pack 558.4M 558.5M +0.0%\n + 5311.38: size of bitmapped pack (--path-walk) 164.4M 164.4M +0.0%\n +\n + (Note that to observe an improvement here, we must repack with '-F' in\n + order to avoid reusing non-'--path-walk' deltas, which would otherwise\n + skew our results.)\n +\n There is one wrinkle when it comes to '--boundary', which we must not\n pass into the bitmap walk in the presence of both '--path-walk' and\n '--use-bitmap-index'. Path-walk needs boundary commits when it performs\n @@ t/perf/p5311-pack-bitmaps-fetch.sh: test_description='performance of fetches fro\n +\ttest_expect_success \"create bitmapped server repo ${argv:+($argv)}\" '\n \t\tgit config pack.writebitmaps true &&\n -\t\tgit repack -ad\n -+\t\tgit repack -ad $argv\n ++\t\tgit repack -adF $argv\n ++\t'\n ++\n ++\ttest_size \"size of bitmapped pack ${argv:+($argv)}\" '\n ++\t\ttest_file_size .git/objects/pack/pack-*.pack\n \t'\n \n \t# simulate a fetch from a repository that last fetched N days ago, for\n @@ t/t5310-pack-bitmaps.sh: test_bitmap_cases\n +\t\t\tgit -c pack.allowPackReuse=$reuse pack-objects \\\n +\t\t\t\t--stdout --revs --path-walk --use-bitmap-index \\\n +\t\t\t\tout.pack &&\n -+\t\t\tgrep \"\\\"category\\\":\\\"bitmap\\\",\\\"key\\\":\\\"bitmap/hits\\\"\" trace.txt &&\n ++\t\t\ttest_grep \"\\\"category\\\":\\\"bitmap\\\",\\\"key\\\":\\\"bitmap/hits\\\"\" trace.txt &&\n +\n +\t\t\tgit index-pack out.pack &&\n +\n3: 069c50d3370 = 3: 315ee0b1988 pack-objects: extract `record_tree_depth()` helper\n4: ae57607b57f = 4: 371fc4317ad pack-objects: support `--delta-islands` with `--path-walk`\n\nbase-commit: 45a9ecee26839cc880fdd5e704339dd3cf4ffc26\n-- \n2.54.0.23.g371fc4317ad\n"},{"id":"546097","messageId":"b1dbf30ddbe9ecc2c005dc3a33a161774638044e.1782082975.git.me@ttaylorr.com","threadId":"65704","inReplyTo":"cover.1782082975.git.me@ttaylorr.com","subject":"[PATCH v3 1/4] t/perf: drop p5311's lookup-table permutation","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2026-06-21T23:02:59Z","receivedAt":"2026-06-21T23:03:02Z","isPatch":true,"body":"p5311 measures the cost of serving a fetch from a bitmapped pack and\nindexing the resulting pack on the client. Since 761416ef91d\n(bitmap-lookup-table: add performance tests for lookup table,\n2022-08-14), p5311 effectively runs itself twice: once with the bitmap's\nlookup table extension enabled, and again with it disabled.\n\nThis comparison has served its useful purpose, as the lookup table is\nalmost four years old, and the de-facto default in server-side Git\ndeployments.\n\nA following commit will want to test a different combination (repacking\nwith and without '--path-walk' instead of the lookup table). Instead of\nmultiplying the current test count by two again to produce four\nvariations of `test_fetch_bitmaps()`, drop the lookup table option to\nreduce the number of perf tests we run. Retain `test_fetch_bitmaps()`\nitself, since we will use this in the future for the new\nparameterization.\n\n(As an aside, a future commit outside of this series will adjust the\ndefault value of 'pack.writeBitmapLookupTable' to \"true\", matching the\nde-facto norm for deployments where the existence of bitmap lookup\ntables is meaningful. Punt on that to a later series and instead make\nthe minimal change for now.)\n\nSuggested-by: Derrick Stolee \nSigned-off-by: Taylor Blau \n---\n t/perf/p5311-pack-bitmaps-fetch.sh | 8 +++-----\n 1 file changed, 3 insertions(+), 5 deletions(-)\n\ndiff --git a/t/perf/p5311-pack-bitmaps-fetch.sh b/t/perf/p5311-pack-bitmaps-fetch.sh\nindex 047efb995d6..5bea5c64e7b 100755\n--- a/t/perf/p5311-pack-bitmaps-fetch.sh\n+++ b/t/perf/p5311-pack-bitmaps-fetch.sh\n@@ -12,7 +12,6 @@ test_fetch_bitmaps () {\n \n \ttest_expect_success 'create bitmapped server repo' '\n \t\tgit config pack.writebitmaps true &&\n-\t\tgit config pack.writeBitmapLookupTable '\"$1\"' &&\n \t\tgit repack -ad\n \t'\n \n@@ -32,7 +31,7 @@ test_fetch_bitmaps () {\n \t\t\t} >revs\n \t\t'\n \n-\t\ttest_perf \"server $title (lookup=$1)\" '\n+\t\ttest_perf \"server $title\" '\n \t\t\tgit pack-objects --stdout --revs \\\n \t\t\t\t\t--thin --delta-base-offset \\\n \t\t\t\t\ttmp.pack\n@@ -42,13 +41,12 @@ test_fetch_bitmaps () {\n \t\t\ttest_file_size tmp.pack\n \t\t'\n \n-\t\ttest_perf \"client $title (lookup=$1)\" '\n+\t\ttest_perf \"client $title\" '\n \t\t\tgit index-pack --stdin --fix-thin boundary` as late as possible within the '--path-walk' traversal,\nafter any bitmap attempt has either succeeded or declined to answer the\nrequest.\n\nSigned-off-by: Taylor Blau \n---\n Documentation/git-pack-objects.adoc | 6 +++--\n builtin/pack-objects.c | 18 +++++++++++++--\n t/perf/p5311-pack-bitmaps-fetch.sh | 18 +++++++++++----\n t/t5310-pack-bitmaps.sh | 36 +++++++++++++++++++++++++++++\n 4 files changed, 70 insertions(+), 8 deletions(-)\n\ndiff --git a/Documentation/git-pack-objects.adoc b/Documentation/git-pack-objects.adoc\nindex 8a27aa19fd3..0adce8961a3 100644\n--- a/Documentation/git-pack-objects.adoc\n+++ b/Documentation/git-pack-objects.adoc\n@@ -402,8 +402,10 @@ will be automatically changed to version `1`.\n \tof filenames that cause collisions in Git's default name-hash\n \talgorithm.\n +\n-Incompatible with `--delta-islands`. The `--use-bitmap-index` option is\n-ignored in the presence of `--path-walk`. The `--path-walk` option\n+Incompatible with `--delta-islands`. When `--use-bitmap-index` is\n+specified with `--path-walk`, a successful bitmap traversal is used for\n+object enumeration, with path-walk remaining as the fallback traversal\n+when the bitmap cannot satisfy the request. The `--path-walk` option\n supports the `--filter=` forms `blob:none`, `blob:limit=`,\n `tree:0`, `object:type=`, and `sparse:`. These supported filter\n types can be combined with the `combine:+` form.\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex b783dc62bc9..e4dcb563b7d 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -4732,6 +4732,15 @@ static int add_objects_by_path(const char *path,\n \t\t\tcontinue;\n \n \t\tadd_object_entry(oid, type, path, exclude);\n+\n+\t\tif (type == OBJ_COMMIT && write_bitmap_index) {\n+\t\t\tstruct commit *commit;\n+\n+\t\t\tcommit = lookup_commit(the_repository, oid);\n+\t\t\tif (!commit)\n+\t\t\t\tdie(_(\"could not find commit %s\"), oid_to_hex(oid));\n+\t\t\tindex_commit_for_bitmap(commit);\n+\t\t}\n \t}\n \n \toe_end = to_pack.nr_objects;\n@@ -4764,6 +4773,13 @@ static int get_object_list_path_walk(struct rev_info *revs)\n \tinfo.path_fn = add_objects_by_path;\n \tinfo.path_fn_data = &processed;\n \n+\t/*\n+\t * Path-walk needs boundary commits to discover thin-pack bases, but\n+\t * bitmap traversal does not understand the boundary state. Set it\n+\t * here so any prior bitmap attempt sees the usual non-boundary walk.\n+\t */\n+\trevs->boundary = 1;\n+\n \t/*\n \t * Allow the --[no-]sparse option to be interesting here, if only\n \t * for testing purposes. Paths with no interesting objects will not\n@@ -5195,9 +5211,7 @@ int cmd_pack_objects(int argc,\n \t\t}\n \t}\n \tif (path_walk) {\n-\t\tstrvec_push(&rp, \"--boundary\");\n \t\tstrvec_push(&rp, \"--objects\");\n-\t\tuse_bitmap_index = 0;\n \t} else if (thin) {\n \t\tuse_internal_rev_list = 1;\n \t\tstrvec_push(&rp, shallow\ndiff --git a/t/perf/p5311-pack-bitmaps-fetch.sh b/t/perf/p5311-pack-bitmaps-fetch.sh\nindex 5bea5c64e7b..50506216227 100755\n--- a/t/perf/p5311-pack-bitmaps-fetch.sh\n+++ b/t/perf/p5311-pack-bitmaps-fetch.sh\n@@ -4,15 +4,22 @@ test_description='performance of fetches from bitmapped packs'\n . ./perf-lib.sh\n \n test_fetch_bitmaps () {\n+\targv=$1\n+\texport argv\n+\n \ttest_expect_success 'setup test directory' '\n \t\trm -fr * .git\n \t'\n \n \ttest_perf_default_repo\n \n-\ttest_expect_success 'create bitmapped server repo' '\n+\ttest_expect_success \"create bitmapped server repo ${argv:+($argv)}\" '\n \t\tgit config pack.writebitmaps true &&\n-\t\tgit repack -ad\n+\t\tgit repack -adF $argv\n+\t'\n+\n+\ttest_size \"size of bitmapped pack ${argv:+($argv)}\" '\n+\t\ttest_file_size .git/objects/pack/pack-*.pack\n \t'\n \n \t# simulate a fetch from a repository that last fetched N days ago, for\n@@ -20,7 +27,7 @@ test_fetch_bitmaps () {\n \t# and assume the first entry in the chain that is N days older than the current\n \t# HEAD is where the HEAD would have been then.\n \tfor days in 1 2 4 8 16 32 64 128; do\n-\t\ttitle=$(printf '%10s' \"($days days)\")\n+\t\ttitle=$(printf '%10s' \"($days days${argv:+, $argv})\")\n \t\ttest_expect_success \"setup revs from $days days ago\" '\n \t\t\tnow=$(git log -1 --format=%ct HEAD) &&\n \t\t\tthen=$(($now - ($days * 86400))) &&\n@@ -47,6 +54,9 @@ test_fetch_bitmaps () {\n \tdone\n }\n \n-test_fetch_bitmaps\n+for argv in '' --path-walk\n+do\n+\ttest_fetch_bitmaps $argv || return 1\n+done\n \n test_done\ndiff --git a/t/t5310-pack-bitmaps.sh b/t/t5310-pack-bitmaps.sh\nindex f693cb56691..7924208d99c 100755\n--- a/t/t5310-pack-bitmaps.sh\n+++ b/t/t5310-pack-bitmaps.sh\n@@ -577,6 +577,42 @@ test_bitmap_cases\n \n sane_unset GIT_TEST_PACK_USE_BITMAP_BOUNDARY_TRAVERSAL\n \n+test_expect_success 'path-walk repack can write and use bitmap indexes' '\n+\ttest_when_finished \"rm -rf path-walk-bitmap\" &&\n+\tgit init path-walk-bitmap &&\n+\t(\n+\t\tcd path-walk-bitmap &&\n+\t\ttest_commit first &&\n+\t\ttest_commit second &&\n+\t\ttest_commit third &&\n+\n+\t\tgit repack -a -d -b --path-walk &&\n+\t\tgit rev-list --test-bitmap --use-bitmap-index HEAD &&\n+\n+\t\tgit rev-parse HEAD >in &&\n+\n+\t\tgit rev-list --objects --no-object-names HEAD >expect.raw &&\n+\t\tsort expect.raw >expect &&\n+\n+\t\tfor reuse in true false\n+\t\tdo\n+\t\t\t: >trace.txt &&\n+\n+\t\t\tGIT_TRACE2_EVENT=\"$(pwd)/trace.txt\" \\\n+\t\t\tgit -c pack.allowPackReuse=$reuse pack-objects \\\n+\t\t\t\t--stdout --revs --path-walk --use-bitmap-index \\\n+\t\t\t\tout.pack &&\n+\t\t\ttest_grep \"\\\"category\\\":\\\"bitmap\\\",\\\"key\\\":\\\"bitmap/hits\\\"\" trace.txt &&\n+\n+\t\t\tgit index-pack out.pack &&\n+\n+\t\t\tlist_packed_objects out.idx >actual.raw &&\n+\t\t\tsort actual.raw >actual &&\n+\t\t\ttest_cmp expect actual || return 1\n+\t\tdone\n+\t)\n+'\n+\n test_expect_success 'incremental repack fails when bitmaps are requested' '\n \ttest_commit more-1 &&\n \ttest_must_fail git repack -d 2>err &&\n-- \n2.54.0.23.g371fc4317ad\n\n"},{"id":"546099","messageId":"315ee0b1988a91e53321d9df8ab6d8312074806e.1782082975.git.me@ttaylorr.com","threadId":"65704","inReplyTo":"cover.1782082975.git.me@ttaylorr.com","subject":"[PATCH v3 3/4] pack-objects: extract `record_tree_depth()` helper","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2026-06-21T23:03:07Z","receivedAt":"2026-06-21T23:03:09Z","isPatch":true,"body":"Prepare for a subsequent change that needs to record tree depths from a\nsecond call site by factoring the delta-islands tree-depth bookkeeping\nout of `show_object()` and into a helper, `record_tree_depth()`.\n\nThe helper looks up the object in `to_pack`, returns early when the\nobject was not added there, computes the depth from the slash count in\nthe supplied name, and preserves the existing max-depth-wins behavior\nwhen a tree is reached by more than one path.\n\nSigned-off-by: Taylor Blau \n---\n builtin/pack-objects.c | 32 ++++++++++++++++++--------------\n 1 file changed, 18 insertions(+), 14 deletions(-)\n\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex e4dcb563b7d..ec02e2b21d2 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -2722,6 +2722,22 @@ static inline void oe_set_tree_depth(struct packing_data *pack,\n \tpack->tree_depth[e - pack->objects] = tree_depth;\n }\n \n+static void record_tree_depth(const struct object_id *oid, const char *name)\n+{\n+\tconst char *p;\n+\tunsigned depth;\n+\tstruct object_entry *ent;\n+\n+\t/* the empty string is a root tree, which is depth 0 */\n+\tdepth = *name ? 1 : 0;\n+\tfor (p = strchr(name, '/'); p; p = strchr(p + 1, '/'))\n+\t\tdepth++;\n+\n+\tent = packlist_find(&to_pack, oid);\n+\tif (ent && depth > oe_tree_depth(&to_pack, ent))\n+\t\toe_set_tree_depth(&to_pack, ent, depth);\n+}\n+\n /*\n * Return the size of the object without doing any delta\n * reconstruction (so non-deltas are true object sizes, but deltas\n@@ -4375,20 +4391,8 @@ static void show_object(struct object *obj, const char *name,\n \tadd_preferred_base_object(name);\n \tadd_object_entry(&obj->oid, obj->type, name, 0);\n \n-\tif (use_delta_islands) {\n-\t\tconst char *p;\n-\t\tunsigned depth;\n-\t\tstruct object_entry *ent;\n-\n-\t\t/* the empty string is a root tree, which is depth 0 */\n-\t\tdepth = *name ? 1 : 0;\n-\t\tfor (p = strchr(name, '/'); p; p = strchr(p + 1, '/'))\n-\t\t\tdepth++;\n-\n-\t\tent = packlist_find(&to_pack, &obj->oid);\n-\t\tif (ent && depth > oe_tree_depth(&to_pack, ent))\n-\t\t\toe_set_tree_depth(&to_pack, ent, depth);\n-\t}\n+\tif (use_delta_islands)\n+\t\trecord_tree_depth(&obj->oid, name);\n }\n \n static void show_object__ma_allow_any(struct object *obj, const char *name, void *data)\n-- \n2.54.0.23.g371fc4317ad\n\n"},{"id":"546100","messageId":"371fc4317ad696264af01b63d1809c3235a632c2.1782082975.git.me@ttaylorr.com","threadId":"65704","inReplyTo":"cover.1782082975.git.me@ttaylorr.com","subject":"[PATCH v3 4/4] pack-objects: support `--delta-islands` with `--path-walk`","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2026-06-21T23:03:10Z","receivedAt":"2026-06-21T23:03:13Z","isPatch":true,"body":"Since the inception of `--path-walk`, this option has had a documented\nincompatibility with `--delta-islands`.\n\nWhen discussing those original patches on the list, a message from\nStolee in [1] noted the following:\n\n this could be remedied by [...] doing a separate walk to identify\n islands using the normal method\n\nIn a related portion of the thread, Peff explains[2]:\n\n The delta islands code already does its own tree walk to propagate\n the bits down (it does rely on the base walk's show_commit() to\n propagate through the commits).\n\n Once each object has its island bitmaps, I think however you\n choose to come up with delta candidates [...] you should be able\n to use it. It's fundamentally just answering the question of \"am\n I allowed to delta between these two objects\".\n\nThat is similar to what this patch does, and it turns out the cheaper\noption is sufficient: perform the same island side effects from the\npath-walk callback rather than doing a second walk.\n\nRecall how delta-islands are computed during a normal repack:\n\n - `show_commit()` calls `propagate_island_marks()` for each commit,\n which merges the commit's island bitset onto its root tree object and\n onto each of its parent commits.\n\n - `show_object()` for a tree records the tree's depth derived from the\n slash-separated pathname. Subsequent `resolve_tree_islands()` uses\n that depth to walk trees in increasing-depth order, propagating each\n tree's marks to its children.\n\n - At delta-search time, `in_same_island()` enforces that a delta\n target's island bitmap is a subset of its base's: every island that\n reaches the target must also reach the base.\n\nPath-walk's enumeration callback is `add_objects_by_path()`. It already\nadds objects to `to_pack`, but until now did not perform the\nisland-related side effects. Two things are needed:\n\n - For each commit batch, call `propagate_island_marks()` on commits,\n exactly as `show_commit()` does.\n\n We have to be careful about the order in which we call this function,\n and we must see a commit before its parents in order to have\n island marks to propagate.\n\n The path-walk batch preserves that order. Path-walk appends commits\n to its `OBJ_COMMIT` batch as they come back from the same\n `get_revision()` loop the regular traversal uses, and\n `add_objects_by_path()` iterates the batch in array order. So every\n commit reaches `propagate_island_marks()` in the same sequence that\n `show_commit()` would have seen it, and the descendant-first chain\n that the algorithm relies on is intact.\n\n Skip island propagation for excluded commits to match the regular\n traversal, whose `show_commit()` callback is only invoked for\n interesting commits. Boundary commits may still be present in\n path-walk's callback so they can serve as thin-pack bases, but they\n should not contribute island marks.\n\n - For each tree batch, record the tree's depth from the path. Use the\n `record_tree_depth()` helper from the previous commit so both\n callbacks behave identically, including the max-depth-wins behavior\n when a tree is reached via more than one path. The helper accepts\n both the `show_object()` path shape (\"foo\", \"foo/bar\") and the\n path-walk shape with a trailing slash (\"foo/\", \"foo/bar/\"), so depths\n recorded from either traversal mode are directly comparable.\n\n This is implicit in the implementation sketch from Peff above.\n `resolve_tree_islands()` sorts trees by `oe->tree_depth` in\n increasing-depth order before propagating marks down, so that a\n parent tree's marks are finalized before its children inherit them.\n Without recording the depth at path-walk time, every\n path-walk-discovered tree would land at depth 0 in `to_pack`, the\n sort would lose its ordering, and children could inherit marks from\n parents whose own contributions had not yet been merged in.\n\nWith those two pieces in place, `resolve_tree_islands()` receives the\nsame island inputs from path-walk as it would from the regular\ntraversal, so the existing island checks can be reused unchanged.\n\nDrop the documented incompatibility between `--path-walk` and\n`--delta-islands`, and add t5320 coverage for path-walk island repacks\nwith and without bitmap writing, as well as the same-island case where a\ndelta remains allowed.\n\n[1]: https://lore.kernel.org/git/9aa2471b-0850-4707-9733-d3b33609f5f2@gmail.com/\n[2]: https://lore.kernel.org/git/20240911063203.GA1538586@coredump.intra.peff.net/\n\nSigned-off-by: Taylor Blau \n---\n Documentation/git-pack-objects.adoc | 14 +++++++-------\n builtin/pack-objects.c | 22 ++++++++++++++++++----\n t/t5320-delta-islands.sh | 29 +++++++++++++++++++++++++++++\n 3 files changed, 54 insertions(+), 11 deletions(-)\n\ndiff --git a/Documentation/git-pack-objects.adoc b/Documentation/git-pack-objects.adoc\nindex 0adce8961a3..65cd00c152f 100644\n--- a/Documentation/git-pack-objects.adoc\n+++ b/Documentation/git-pack-objects.adoc\n@@ -402,13 +402,13 @@ will be automatically changed to version `1`.\n \tof filenames that cause collisions in Git's default name-hash\n \talgorithm.\n +\n-Incompatible with `--delta-islands`. When `--use-bitmap-index` is\n-specified with `--path-walk`, a successful bitmap traversal is used for\n-object enumeration, with path-walk remaining as the fallback traversal\n-when the bitmap cannot satisfy the request. The `--path-walk` option\n-supports the `--filter=` forms `blob:none`, `blob:limit=`,\n-`tree:0`, `object:type=`, and `sparse:`. These supported filter\n-types can be combined with the `combine:+` form.\n+When `--use-bitmap-index` is specified with `--path-walk`, a successful\n+bitmap traversal is used for object enumeration, with path-walk\n+remaining as the fallback traversal when the bitmap cannot satisfy the\n+request. The `--path-walk` option supports the `--filter=` forms\n+`blob:none`, `blob:limit=`, `tree:0`, `object:type=`, and\n+`sparse:`. These supported filter types can be combined with the\n+`combine:+` form.\n \n \n DELTA ISLANDS\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex ec02e2b21d2..f48ea7a888b 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -4737,13 +4737,29 @@ static int add_objects_by_path(const char *path,\n \n \t\tadd_object_entry(oid, type, path, exclude);\n \n-\t\tif (type == OBJ_COMMIT && write_bitmap_index) {\n+\t\tif (type == OBJ_COMMIT) {\n \t\t\tstruct commit *commit;\n \n+\t\t\tif (!write_bitmap_index && !use_delta_islands)\n+\t\t\t\tcontinue;\n+\n \t\t\tcommit = lookup_commit(the_repository, oid);\n \t\t\tif (!commit)\n \t\t\t\tdie(_(\"could not find commit %s\"), oid_to_hex(oid));\n-\t\t\tindex_commit_for_bitmap(commit);\n+\t\t\tif (write_bitmap_index)\n+\t\t\t\tindex_commit_for_bitmap(commit);\n+\t\t\t/*\n+\t\t\t * Skip island propagation for boundary commits.\n+\t\t\t * The regular traversal's show_commit() is only\n+\t\t\t * called for interesting commits; matching that\n+\t\t\t * here keeps path-walk from doing extra work that\n+\t\t\t * would only be a no-op anyway (boundary commits\n+\t\t\t * are not in island_marks).\n+\t\t\t */\n+\t\t\tif (use_delta_islands && !exclude)\n+\t\t\t\tpropagate_island_marks(the_repository, commit);\n+\t\t} else if (type == OBJ_TREE && use_delta_islands) {\n+\t\t\trecord_tree_depth(oid, path);\n \t\t}\n \t}\n \n@@ -5205,8 +5221,6 @@ int cmd_pack_objects(int argc,\n \t\tconst char *option = NULL;\n \t\tif (!path_walk_filter_compatible(&filter_options))\n \t\t\toption = \"--filter\";\n-\t\telse if (use_delta_islands)\n-\t\t\toption = \"--delta-islands\";\n \n \t\tif (option) {\n \t\t\twarning(_(\"cannot use %s with %s\"),\ndiff --git a/t/t5320-delta-islands.sh b/t/t5320-delta-islands.sh\nindex 2c961c70963..9b28344a0a3 100755\n--- a/t/t5320-delta-islands.sh\n+++ b/t/t5320-delta-islands.sh\n@@ -53,6 +53,35 @@ test_expect_success 'separate islands disallows delta' '\n \t! is_delta_base $two $one\n '\n \n+test_expect_success 'path-walk island repack respects islands' '\n+\tGIT_TRACE2_EVENT=\"$(pwd)/trace.path-walk-islands\" \\\n+\t\tgit -c \"pack.island=refs/heads/(.*)\" repack -adfi \\\n+\t\t--path-walk 2>err &&\n+\ttest_region pack-objects path-walk trace.path-walk-islands &&\n+\ttest_grep ! \"cannot use --delta-islands with --path-walk\" err &&\n+\t! is_delta_base $one $two &&\n+\t! is_delta_base $two $one\n+'\n+\n+test_expect_success 'path-walk island bitmap repack respects islands' '\n+\tGIT_TRACE2_EVENT=\"$(pwd)/trace.path-walk-island-bitmap\" \\\n+\t\tgit -c \"pack.island=refs/heads/(.*)\" repack -a -d -f -i -b \\\n+\t\t--path-walk 2>err &&\n+\ttest_region pack-objects path-walk trace.path-walk-island-bitmap &&\n+\ttest_path_is_file .git/objects/pack/*.bitmap &&\n+\tgit rev-list --test-bitmap --use-bitmap-index one &&\n+\ttest_grep ! \"cannot use --delta-islands with --path-walk\" err &&\n+\t! is_delta_base $one $two &&\n+\t! is_delta_base $two $one\n+'\n+\n+test_expect_success 'path-walk same island allows delta' '\n+\tGIT_TRACE2_EVENT=\"$(pwd)/trace.path-walk-same-island\" \\\n+\t\tgit -c \"pack.island=refs/heads\" repack -adfi --path-walk &&\n+\ttest_region pack-objects path-walk trace.path-walk-same-island &&\n+\tis_delta_base $one $two\n+'\n+\n test_expect_success 'same island allows delta' '\n \tgit -c \"pack.island=refs/heads\" repack -adfi &&\n \tis_delta_base $one $two\n-- \n2.54.0.23.g371fc4317ad\n"},{"id":"546116","messageId":"xmqqmrwn3u4x.fsf@gitster.g","threadId":"65704","inReplyTo":"cover.1782082975.git.me@ttaylorr.com","subject":"Re: [PATCH v3 0/4] pack-objects: support bitmaps and delta-islands with `--path-walk`","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2026-06-22T07:35:10Z","receivedAt":"2026-06-22T07:35:13Z","isPatch":true,"body":"Taylor Blau writes:\n\n> Note to the maintainer:\n>\n> * This series is still based on 'ds/path-walk-filters' with Patrick's\n> 'ps/clang-w-glibc-2.43-and-_Generic' merged in.\n>\n> Here is another small reroll of my series to make `--path-walk` work\n> with reachability bitmaps and delta-islands.\n>\n> This round addresses Stolee's request to demonstrate the repack-size\n> side of the integration between `--path-walk` and bitmap writing, and\n> fixes an errant \"grep\" in the test suite.\n>\n> Changes since v2 include:\n>\n> * p5311 now forces a fresh repack with '-F' when building its bitmapped\n> test repository. This avoids reusing deltas from a non-'--path-walk'\n> pack when we are trying to measure a pack produced by `--path-walk`.\n>\n> * p5311 now records the size of the bitmapped pack, both with and\n> without `--path-walk`, to show that writing bitmaps during a\n> `--path-walk` repack does not lose the pack-size improvement that\n> `--path-walk` provides in repositories where it helps.\n>\n> * The second patch's commit message has updated p5311 numbers from a\n> recent fluentui clone, fixing the \"pack sizes\" typo and documenting\n> the new bitmapped-pack-size comparison.\n>\n> * The t5310 grep assertion now uses `test_grep`, as suggested by Junio.\n>\n> Outside of the above, the series is functionally unchanged.\n>\n> Thanks in advance for another look.\n>\n> Taylor Blau (4):\n> t/perf: drop p5311's lookup-table permutation\n> pack-objects: support reachability bitmaps with `--path-walk`\n> pack-objects: extract `record_tree_depth()` helper\n> pack-objects: support `--delta-islands` with `--path-walk`\n\nVery cleanly implemented. I am not confident that I have followed\nthe detailed logic around delta islands in the last step but the\nearlier three patches looked trivially good.\n\nThanks. Will replace.\n"},{"id":"546181","messageId":"b6ed816c-030b-400a-9fb6-6671fd3cb0b0@gmail.com","threadId":"65704","inReplyTo":"xmqqmrwn3u4x.fsf@gitster.g","subject":"Re: [PATCH v3 0/4] pack-objects: support bitmaps and delta-islands with `--path-walk`","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2026-06-22T13:36:02Z","receivedAt":"2026-06-22T13:36:04Z","isPatch":true,"body":"On 6/22/2026 3:35 AM, Junio C Hamano wrote:\n> Taylor Blau writes:\n\n>> Outside of the above, the series is functionally unchanged.\n>>\n>> Thanks in advance for another look.\n>>\n>> Taylor Blau (4):\n>> t/perf: drop p5311's lookup-table permutation\n>> pack-objects: support reachability bitmaps with `--path-walk`\n>> pack-objects: extract `record_tree_depth()` helper\n>> pack-objects: support `--delta-islands` with `--path-walk`\n> \n> Very cleanly implemented. I am not confident that I have followed\n> the detailed logic around delta islands in the last step but the\n> earlier three patches looked trivially good.\nI've been happy with the code, subject to the new data that is presented\nwith this version confirming the expected performance benefits. I also\nlack confidence in the delta islands features, but based on my weak\nunderstanding it looks correct. I believe that Taylor has the right\nexpertise here to make up for my lack of context.\n\nThanks,\n-Stolee\n"},{"id":"546191","messageId":"xmqqwlvq1qyy.fsf@gitster.g","threadId":"65704","inReplyTo":"b6ed816c-030b-400a-9fb6-6671fd3cb0b0@gmail.com","subject":"Re: [PATCH v3 0/4] pack-objects: support bitmaps and delta-islands with `--path-walk`","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2026-06-22T16:26:29Z","receivedAt":"2026-06-22T16:26:31Z","isPatch":true,"body":"Derrick Stolee writes:\n\n> On 6/22/2026 3:35 AM, Junio C Hamano wrote:\n>> Taylor Blau writes:\n>\n>>> Outside of the above, the series is functionally unchanged.\n>>>\n>>> Thanks in advance for another look.\n>>>\n>>> Taylor Blau (4):\n>>> t/perf: drop p5311's lookup-table permutation\n>>> pack-objects: support reachability bitmaps with `--path-walk`\n>>> pack-objects: extract `record_tree_depth()` helper\n>>> pack-objects: support `--delta-islands` with `--path-walk`\n>> \n>> Very cleanly implemented. I am not confident that I have followed\n>> the detailed logic around delta islands in the last step but the\n>> earlier three patches looked trivially good.\n> I've been happy with the code, subject to the new data that is presented\n> with this version confirming the expected performance benefits. I also\n> lack confidence in the delta islands features, but based on my weak\n> understanding it looks correct. I believe that Taylor has the right\n> expertise here to make up for my lack of context.\n\nThanks. Let me mark the topic for 'next' then.\n"}]}