Note to the maintainer:

 * This series is based on 'ds/path-walk-filters' with Patrick's
   'ps/clang-w-glibc-2.43-and-_Generic' merged in. The former has since
   graduated. These are the three remaining patches from my earlier RFC
   after Stolee's series incorporated the filter-related pieces.

Here is a trimmed-down reroll of my series to make `--path-walk` work with reachability bitmaps and delta-islands. This series was originally an RFC that was a companion to Stolee's recent patches to extend `--filter` support to `--path-walk` [1].

Since the previous round, Stolee's series has graduated and incorporated the filter-related patches from my earlier RFC [2]. What remains are the three patches here that implement support for reachability bitmaps and delta-islands under `--path-walk`.

 * The first patch allows `--path-walk` to use reachability bitmaps when
   they can answer the request, falling back to path-walk enumeration
   when they cannot. It also lets bitmap writing see the same commit
   candidates that the regular traversal would have shown to the bitmap
   selector.

 * The second patch is preparatory, and factors the
   delta-islands-specific tree-depth recording from `show_object()` into
   a helper.

 * The final patch teaches the path-walk callback to perform the same
   delta-islands side effects as the regular traversal: propagating
   island marks for commits, and recording tree depths for trees. This
   gives `resolve_tree_islands()` the same input in either enumeration
   mode, so the existing island checks can be reused unchanged.

Thanks in advance for your review!

[1]: https://lore.kernel.org/git/pull.2101.git.1777731354.gitgitgadget@gmail.com/ [2]: https://lore.kernel.org/git/cover.1777853408.git.me@ttaylorr.com/

Taylor Blau (3):
  pack-objects: support reachability bitmaps with `--path-walk`
  pack-objects: extract `record_tree_depth()` helper
  pack-objects: support `--delta-islands` with `--path-walk`

 Documentation/git-pack-objects.adoc | 12 ++---
 builtin/pack-objects.c              | 68 +++++++++++++++++++++--------
 t/t5310-pack-bitmaps.sh             | 36 +++++++++++++++
 t/t5320-delta-islands.sh            | 29 ++++++++++++
 4 files changed, 122 insertions(+), 23 deletions(-)

base-commit: 45a9ecee26839cc880fdd5e704339dd3cf4ffc26

When 'pack-objects' is invoked with '--path-walk', it prevents us from using reachability bitmaps.

This behavior dates back to 70664d2865c (pack-objects: add --path-walk option, 2025-05-16), which included a comment in the relevant portion of the command-line arguments handling that read as follows:

    /*
     * We must disable the bitmaps because we are removing
     * the --objects / --objects-edge[-aggressive] options.
     */

In fb2c309b7d3 (pack-objects: pass --objects with --path-walk, 2026-05-02), path-walk learned to pass '--objects' again, but still kept bitmap traversal disabled. That leaves two useful cases unsupported:

 * A path-walk repack that writes bitmaps does not give the bitmap
   selector any commits, because path-walk reveals commits through
   `add_objects_by_path()` rather than through `show_commit()`, where
   `index_commit_for_bitmap()` is normally called.

 * An invocation like "git pack-objects --use-bitmap-index --path-walk"
   never tries an existing bitmap, even when one is available and could
   answer the request.

Fortunately for us, neither restriction is required.

 * On the writing side: teach the path-walk object callback to call
   `index_commit_for_bitmap()` for commits that it adds to the pack.
   That gives the bitmap selector the commit candidates it would have
   seen from the regular traversal.

 * For bitmap reading, keep passing '--objects' to the internal rev_list
   machinery, but stop clearing `use_bitmap_index`. If an existing
   bitmap can answer the request, use it; otherwise fall back to
   path-walk's own enumeration.

There is one wrinkle when it comes to '--boundary', which we must not pass into the bitmap walk in the presence of both '--path-walk' and '--use-bitmap-index'. Path-walk needs boundary commits when it performs its own traversal, in order to discover bases for thin packs, but the bitmap traversal expects the usual non-boundary state. Work around this by setting `revs->boundary` as late as possible within `get_object_list_path_walk()`, after any bitmap attempt has either succeeded or declined to answer the request.

Signed-off-by: Taylor Blau <me@ttaylorr.com>
---
 Documentation/git-pack-objects.adoc |  6 +++--
 builtin/pack-objects.c              | 18 +++++++++++++--
 t/t5310-pack-bitmaps.sh             | 36 +++++++++++++++++++++++++++++
 3 files changed, 56 insertions(+), 4 deletions(-)

Prepare for a subsequent change that needs to record tree depths from a second call site by factoring the delta-islands tree-depth bookkeeping out of `show_object()` and into a helper, `record_tree_depth()`.

The helper looks up the object in `to_pack`, returns early when the object was not added there, computes the depth from the slash count in the supplied name, and preserves the existing max-depth-wins behavior when a tree is reached by more than one path.

Signed-off-by: Taylor Blau <me@ttaylorr.com>
---
 builtin/pack-objects.c | 32 ++++++++++++++++++--------------
 1 file changed, 18 insertions(+), 14 deletions(-)

Since the inception of `--path-walk`, this option has had a documented incompatibility with `--delta-islands`.

When discussing those original patches on the list, a message from Stolee in [1] noted the following:

    this could be remedied by [...] doing a separate walk to identify
    islands using the normal method

In a related portion of the thread, Peff explains[2]:

    The delta islands code already does its own tree walk to propagate
    the bits down (it does rely on the base walk's show_commit() to
    propagate through the commits).

    Once each object has its island bitmaps, I think however you
    choose to come up with delta candidates [...] you should be able
    to use it. It's fundamentally just answering the question of "am
    I allowed to delta between these two objects".

That is similar to what this patch does, and it turns out the cheaper option is sufficient: perform the same island side effects from the path-walk callback rather than doing a second walk.

Recall how delta-islands are computed during a normal repack:

 - `show_commit()` calls `propagate_island_marks()` for each commit,
   which merges the commit's island bitset onto its root tree object and
   onto each of its parent commits.

 - `show_object()` for a tree records the tree's depth derived from the
   slash-separated pathname. Subsequent `resolve_tree_islands()` uses
   that depth to walk trees in increasing-depth order, propagating each
   tree's marks to its children.

 - At delta-search time, `in_same_island()` enforces that a delta
   target's island bitmap is a subset of its base's: every island that
   reaches the target must also reach the base.

Path-walk's enumeration callback is `add_objects_by_path()`. It already adds objects to `to_pack`, but until now did not perform the island-related side effects. Two things are needed:

 - For each commit batch, call `propagate_island_marks()` on commits,
   exactly as `show_commit()` does.

   We have to be careful about the order in which we call this function,
   and we must see a commit before its parents in order to have
   island marks to propagate.

   The path-walk batch preserves that order. Path-walk appends commits
   to its `OBJ_COMMIT` batch as they come back from the same
   `get_revision()` loop the regular traversal uses, and
   `add_objects_by_path()` iterates the batch in array order. So every
   commit reaches `propagate_island_marks()` in the same sequence that
   `show_commit()` would have seen it, and the descendant-first chain
   that the algorithm relies on is intact.

   Skip island propagation for excluded commits to match the regular
   traversal, whose `show_commit()` callback is only invoked for
   interesting commits. Boundary commits may still be present in
   path-walk's callback so they can serve as thin-pack bases, but they
   should not contribute island marks.

 - For each tree batch, record the tree's depth from the path. Use the
   `record_tree_depth()` helper from the previous commit so both
   callbacks behave identically, including the max-depth-wins behavior
   when a tree is reached via more than one path. The helper accepts
   both the `show_object()` path shape ("foo", "foo/bar") and the
   path-walk shape with a trailing slash ("foo/", "foo/bar/"), so depths
   recorded from either traversal mode are directly comparable.

   This is implicit in the implementation sketch from Peff above.
   `resolve_tree_islands()` sorts trees by `oe->tree_depth` in
   increasing-depth order before propagating marks down, so that a
   parent tree's marks are finalized before its children inherit them.
   Without recording the depth at path-walk time, every
   path-walk-discovered tree would land at depth 0 in `to_pack`, the
   sort would lose its ordering, and children could inherit marks from
   parents whose own contributions had not yet been merged in.

With those two pieces in place, `resolve_tree_islands()` receives the same island inputs from path-walk as it would from the regular traversal, so the existing island checks can be reused unchanged.

Drop the documented incompatibility between `--path-walk` and `--delta-islands`, and add t5320 coverage for path-walk island repacks with and without bitmap writing, as well as the same-island case where a delta remains allowed.

[1]: https://lore.kernel.org/git/9aa2471b-0850-4707-9733-d3b33609f5f2@gmail.com/ [2]: https://lore.kernel.org/git/20240911063203.GA1538586@coredump.intra.peff.net/

Signed-off-by: Taylor Blau <me@ttaylorr.com>
---
 Documentation/git-pack-objects.adoc | 14 +++++++-------
 builtin/pack-objects.c              | 22 ++++++++++++++++++----
 t/t5320-delta-islands.sh            | 29 +++++++++++++++++++++++++++++
 3 files changed, 54 insertions(+), 11 deletions(-)

On 5/27/26 7:18 PM, Taylor Blau wrote:

I've applied these patches locally and confirmed that each one passes the test suite with GIT_TEST_PACK_PATH_WALK=1, which helps to confirm that the changes are correct (all existing bitmap tests create and use the bitmaps with --path-walk unless explicitly disabled).

Should we add GIT_TEST_PACK_PATH_WALK=1 to the test-var CI build, now that this is going to be more commonly used?

Do you have any end-to-end performance data to demonstrate that these changes are effective at scale? Are we still producing packfiles with the pack-file compression and now with .bitmap files? How does this impact the performance of a clone or fetch when using a bitmap index at read time?

With that in mind, should we update any t/perf/ test to cover some of these scenarios? I'm running a few with GIT_TEST_PACK_PATH_WALK=1 on my laptop as a test, but it's taking a while. If you have stats ready from your local testing, then that would be interesting.

Thanks, -Stolee

On 5/28/26 11:28 AM, Derrick Stolee wrote:

Here's my attempt to use our existing performance tests to analyze the impact of this series.

Running p5311 against the base of this topic and this topic with GIT_TEST_PACK_PATH_WALK=1, I get this output:

Test HEAD~3 HEAD ----------------------------------------------------------------- 5311.4: server (1 days) (lookup=true) 0.02 0.03 +50.0% 5311.5: size (1 days) 6.8K 124.9K +1730.9% 5311.6: client (1 days) (lookup=true) 0.02 0.01 -50.0% 5311.8: server (2 days) (lookup=true) 0.02 0.03 +50.0% 5311.9: size (2 days) 6.8K 124.9K +1730.9% 5311.10: client (2 days) (lookup=true) 0.02 0.01 -50.0% 5311.12: server (4 days) (lookup=true) 0.02 0.03 +50.0% 5311.13: size (4 days) 6.8K 124.9K +1730.9% 5311.14: client (4 days) (lookup=true) 0.02 0.01 -50.0% 5311.16: server (8 days) (lookup=true) 0.03 0.03 +0.0% 5311.17: size (8 days) 37.3K 186.0K +398.2% 5311.18: client (8 days) (lookup=true) 0.03 0.02 -33.3% 5311.20: server (16 days) (lookup=true) 0.02 0.03 +50.0% 5311.21: size (16 days) 37.3K 186.0K +398.2% 5311.22: client (16 days) (lookup=true) 0.03 0.02 -33.3% 5311.24: server (32 days) (lookup=true) 0.03 0.03 +0.0% 5311.25: size (32 days) 46.5K 197.2K +324.3% 5311.26: client (32 days) (lookup=true) 0.03 0.02 -33.3% 5311.28: server (64 days) (lookup=true) 0.24 0.16 -33.3% 5311.29: size (64 days) 1.5M 5.1M +239.8% 5311.30: client (64 days) (lookup=true) 0.42 0.35 -16.7% 5311.32: server (128 days) (lookup=true) 0.49 0.29 -40.8% 5311.33: size (128 days) 4.1M 9.8M +139.5% 5311.34: client (128 days) (lookup=true) 0.86 0.65 -24.4% 5311.38: server (1 days) (lookup=false) 0.02 0.03 +50.0% 5311.39: size (1 days) 6.8K 124.9K +1730.9% 5311.40: client (1 days) (lookup=false) 0.02 0.02 +0.0% 5311.42: server (2 days) (lookup=false) 0.02 0.03 +50.0% 5311.43: size (2 days) 6.8K 124.9K +1730.9% 5311.44: client (2 days) (lookup=false) 0.02 0.02 +0.0% 5311.46: server (4 days) (lookup=false) 0.02 0.03 +50.0% 5311.47: size (4 days) 6.8K 124.9K +1730.9% 5311.48: client (4 days) (lookup=false) 0.02 0.02 +0.0% 5311.50: server (8 days) (lookup=false) 0.02 0.03 +50.0% 5311.51: size (8 days) 37.3K 186.0K +398.2% 5311.52: client (8 days) (lookup=false) 0.03 0.02 -33.3% 5311.54: server (16 days) (lookup=false) 0.02 0.03 +50.0% 5311.55: size (16 days) 37.3K 186.0K +398.2% 5311.56: client (16 days) (lookup=false) 0.03 0.02 -33.3% 5311.58: server (32 days) (lookup=false) 0.03 0.03 +0.0% 5311.59: size (32 days) 46.5K 197.2K +324.3% 5311.60: client (32 days) (lookup=false) 0.03 0.02 -33.3% 5311.62: server (64 days) (lookup=false) 0.25 0.17 -32.0% 5311.63: size (64 days) 1.5M 5.1M +239.8% 5311.64: client (64 days) (lookup=false) 0.43 0.37 -14.0% 5311.66: server (128 days) (lookup=false) 0.50 0.29 -42.0% 5311.67: size (128 days) 4.1M 9.8M +138.6% 5311.68: client (128 days) (lookup=false) 0.87 0.67 -23.0%

It's important to realize that even with the test variable, the path-walk logic is overriding the bitmap logic in the HEAD~3 case.

What's happening is that the path-walk mode (without bitmaps) is computing a smaller packfile for all of these cases. Some are significantly smaller, but only when it's a very small pack anyway. The bitmap case is faster only for larger fetches.

I did the same test without the path-walk feature and both columns looked the same (as expected, no change due to this series) and the data matched the path-walk test's HEAD column pretty closely. So this shows that adding path-walk to bitmap-focused efforts is not a regression on any of these dimensions.

This test was for my local copy of the Git repository, including all the forks I fetch. I hoped the results would be different for repositories that have data shapes that struggle with name-hash collisions, but microsoft/fluentui is an example that I've used for path-walk repacks before and it had similar data.

Do you have a good feeling for why the path-walk feature doesn't make a huge change in these test scenarios?

Thanks, -Stolee

On Fri, May 29, 2026 at 01:26:33PM -0400, Derrick Stolee wrote:

Yikes. That's not great, but see below for what I think is going on.

(As an aside, we can focus in on either lookup=true or lookup=false, since these are just controlling whether or not the bitmap lookup table is written. On a repository as small as git.git, this shouldn't make a huge difference either way. I have a separate series to make this the default and to clean up the t/perf suite accordingly, but haven't sent it to the list yet.)

I think this is either the primary reason why you're not seeing an improvement here, or at least related to it...

I think the problem is that we're relying on the TEST_ variable to tell pack-objects to generate a pack using --path-walk, but treat it as a fallback.

I suspect that since p5311 invokes repack *without* the '--path-walk' option, we end up in this case within cmd_pack_objects():

	if (path_walk < 0) {
		if (use_bitmap_index > 0 ||
		    !use_internal_rev_list)
			path_walk = 0;
		else if (the_repository->gitdir &&
			 the_repository->settings.pack_use_path_walk)
			path_walk = 1;
		else
			path_walk = git_env_bool("GIT_TEST_PACK_PATH_WALK", 0);
	}

, where `path_walk` is *not* set, but `use_bitmap_index` is since p5311 set the 'pack.writeBitmaps' configuration (as a separate aside, this should really prefer the non-deprecated 'repack.writeBitmaps' variant).

So in that case, we fall back to `path_walk = 0`, and don't even bother reading the `GIT_TEST_PACK_PATH_WALK` variable.

If I modify the perf test like so:

--- 8< ---

On 5/29/2026 4:07 PM, Taylor Blau wrote:

I see. When `--use-bitmap-index` is specified, then the test variable is ignored. So my tests aren't actually measuring the intended end state.

The sizes don't shrink, and in one case increases by a small amount. I'm happy to count those cases as noise from multi-threaded delta calculations being less deterministic.

The _time_ taken to compute the packfiles is what decreases, though, which is promising.

Can you double-check this reasoning with my read of the data? The size isn't changing, but the computation time is.

I see that these tests are extracted from test_all_... below:

Because the --use-bitmap-index and --write-bitmap-index args aren't appropriate across these different commands.

nit: the diff would be more obvious if test_repack_with_args was defined after test_all_with_args so the hunk of existing tests wouldn't appear in the diff.

So this allows us to test all of the different modes.

I'm interested to see some results of your new p5313 test to make sure that we are getting expected size changes for the repack, since the p5311 tests were more focused on the thin fetch pack (and didn't show a change in size).

For that, I'd be interested to see this test be included in a patch for future reference, too.

Thanks, -Stolee

On Fri, May 29, 2026 at 05:28:32PM -0400, Derrick Stolee wrote:

Yeah, that's right, and my apologies for being in a slight rush when sending this to you ;-).

The size staying flat makes sense, since both packs were generated with --path-walk, we're just changing the way they're served. In HEAD~3, that pack is generated on-the-fly and sent over to the client. At HEAD, we're doing verbatim reuse over an already-existing pack which we got via repacking (also generated with --path-walk).

So I think you get to the same end-result (more or less, modulo usual delta patching via pack-reuse), but the time to get there drops significantly since we don't have to (re)compute the pack.

Exactly.

Fair enough :-).

Will do.

Thanks, Taylor

Note to the maintainer:

 * This series is based on 'ds/path-walk-filters' with Patrick's
   'ps/clang-w-glibc-2.43-and-_Generic' merged in. The former has since
   graduated. These are the three remaining patches from my earlier RFC
   after Stolee's series incorporated the filter-related pieces.

Here is a very small reroll of my series to make `--path-walk` work with reachability bitmaps and delta-islands.

Since the previous round, the only changes are:

 * A new commit making some adjustments to p5311 to facilitate
   performance testing bitmaps in repositories repacked with
   '--path-walk'.

 * Updates to (what is now) the second commit's message, including
   performance results based on the aforementioned changes.

Outside of the above, the series is otherwise unchanged.

Thanks in advance for your review!

Taylor Blau (4):
  t/perf: drop p5311's lookup-table permutation
  pack-objects: support reachability bitmaps with `--path-walk`
  pack-objects: extract `record_tree_depth()` helper
  pack-objects: support `--delta-islands` with `--path-walk`

 Documentation/git-pack-objects.adoc | 12 ++---
 builtin/pack-objects.c              | 68 +++++++++++++++++++++--------
 t/perf/p5311-pack-bitmaps-fetch.sh  | 20 +++++----
 t/t5310-pack-bitmaps.sh             | 36 +++++++++++++++
 t/t5320-delta-islands.sh            | 29 ++++++++++++
 5 files changed, 134 insertions(+), 31 deletions(-)

Range-diff against v1:
-:  ----------- > 1:  52d63e8910e t/perf: drop p5311's lookup-table permutation
1:  3fa8bfbfd59 ! 2:  ffad584a43e pack-objects: support reachability bitmaps with `--path-walk`
    @@ Commit message
            bitmap can answer the request, use it; otherwise fall back to
            path-walk's own enumeration.
     
    +    As a result, we can see significantly reduced pack sizes from p5311
    +    before this commit:
    +
    +        Test                                      HEAD^             HEAD
    +        ----------------------------------------------------------------------------------
    +        5311.38: server (1 days, --path-walk)     2.56(2.52+0.03)   0.01(0.01+0.00) -99.6%
    +        5311.39: size   (1 days, --path-walk)              123.9K            123.9K +0.0%
    +        5311.40: client (1 days, --path-walk)     0.00(0.01+0.00)   0.00(0.00+0.00) =
    +        5311.42: server (2 days, --path-walk)     2.57(2.52+0.05)   0.01(0.01+0.00) -99.6%
    +        5311.43: size   (2 days, --path-walk)              123.9K            123.9K +0.0%
    +        5311.44: client (2 days, --path-walk)     0.00(0.00+0.00)   0.00(0.00+0.00) =
    +        5311.46: server (4 days, --path-walk)     2.58(2.51+0.07)   0.01(0.01+0.00) -99.6%
    +        5311.47: size   (4 days, --path-walk)              123.9K            123.9K +0.0%
    +        5311.48: client (4 days, --path-walk)     0.00(0.00+0.00)   0.00(0.00+0.00) =
    +        5311.50: server (8 days, --path-walk)     2.58(2.53+0.04)   0.02(0.02+0.00) -99.2%
    +        5311.51: size   (8 days, --path-walk)              152.4K            152.4K +0.0%
    +        5311.52: client (8 days, --path-walk)     0.00(0.01+0.00)   0.00(0.01+0.00) =
    +        5311.54: server (16 days, --path-walk)    2.58(2.52+0.05)   0.03(0.02+0.00) -98.8%
    +        5311.55: size   (16 days, --path-walk)             205.3K            205.3K +0.0%
    +        5311.56: client (16 days, --path-walk)    0.01(0.01+0.00)   0.01(0.01+0.00) +0.0%
    +        5311.58: server (32 days, --path-walk)    2.59(2.53+0.06)   0.03(0.03+0.00) -98.8%
    +        5311.59: size   (32 days, --path-walk)             209.3K            209.3K +0.0%
    +        5311.60: client (32 days, --path-walk)    0.01(0.02+0.00)   0.01(0.02+0.00) +0.0%
    +        5311.62: server (64 days, --path-walk)    2.70(2.76+0.06)   0.16(0.24+0.04) -94.1%
    +        5311.63: size   (64 days, --path-walk)               4.1M              4.1M +0.0%
    +        5311.64: client (64 days, --path-walk)    0.44(0.50+0.02)   0.44(0.51+0.02) +0.0%
    +        5311.66: server (128 days, --path-walk)   2.88(3.20+0.05)   0.34(0.65+0.05) -88.2%
    +        5311.67: size   (128 days, --path-walk)              9.0M              9.0M -0.0%
    +        5311.68: client (128 days, --path-walk)   0.93(1.22+0.07)   0.93(1.20+0.08) +0.0%
    +
    +    We get the same size of output pack, but this commit allows us to do so
    +    in a significantly shorter amount of time. Intuitively, we're generating
    +    the same pack (hence the unchanged 'test_size' output from run to run),
    +    but varying how we get there. Before this commit, pack-objects prefers
    +    '--path-walk' to '--use-bitmap-index', so we generate the output pack by
    +    performing a normal '--path-walk' traversal. With this commit, we are
    +    operating over a *repacked* state (that itself was done with a
    +    '--path-walk' traversal), but are able to perform pack-reuse on that
    +    repacked state via bitmaps.
    +
         There is one wrinkle when it comes to '--boundary', which we must not
         pass into the bitmap walk in the presence of both '--path-walk' and
         '--use-bitmap-index'. Path-walk needs boundary commits when it performs
         its own traversal, in order to discover bases for thin packs, but the
    -    bitmap traversal expects the usual non-boundary state. Work around this
    -    by setting `revs->boundary` as late as possible within
    -    `get_object_list_path_walk()`, after any bitmap attempt has either
    -    succeeded or declined to answer the request.
    +    bitmap traversal does not expect this. Work around this by setting
    +    `revs->boundary` as late as possible within the '--path-walk' traversal,
    +    after any bitmap attempt has either succeeded or declined to answer the
    +    request.
     
         Signed-off-by: Taylor Blau <me@ttaylorr.com>
     
    @@ builtin/pack-objects.c: int cmd_pack_objects(int argc,
      		use_internal_rev_list = 1;
      		strvec_push(&rp, shallow
     
    + ## t/perf/p5311-pack-bitmaps-fetch.sh ##
    +@@ t/perf/p5311-pack-bitmaps-fetch.sh: test_description='performance of fetches from bitmapped packs'
    + . ./perf-lib.sh
    + 
    + test_fetch_bitmaps () {
    ++	argv=$1
    ++	export argv
    ++
    + 	test_expect_success 'setup test directory' '
    + 		rm -fr * .git
    + 	'
    + 
    + 	test_perf_default_repo
    + 
    +-	test_expect_success 'create bitmapped server repo' '
    ++	test_expect_success "create bitmapped server repo ${argv:+($argv)}" '
    + 		git config pack.writebitmaps true &&
    +-		git repack -ad
    ++		git repack -ad $argv
    + 	'
    + 
    + 	# simulate a fetch from a repository that last fetched N days ago, for
    +@@ t/perf/p5311-pack-bitmaps-fetch.sh: test_fetch_bitmaps () {
    + 	# and assume the first entry in the chain that is N days older than the current
    + 	# HEAD is where the HEAD would have been then.
    + 	for days in 1 2 4 8 16 32 64 128; do
    +-		title=$(printf '%10s' "($days days)")
    ++		title=$(printf '%10s' "($days days${argv:+, $argv})")
    + 		test_expect_success "setup revs from $days days ago" '
    + 			now=$(git log -1 --format=%ct HEAD) &&
    + 			then=$(($now - ($days * 86400))) &&
    +@@ t/perf/p5311-pack-bitmaps-fetch.sh: test_fetch_bitmaps () {
    + 	done
    + }
    + 
    +-test_fetch_bitmaps
    ++for argv in '' --path-walk
    ++do
    ++	test_fetch_bitmaps $argv || return 1
    ++done
    + 
    + test_done
    +
      ## t/t5310-pack-bitmaps.sh ##
     @@ t/t5310-pack-bitmaps.sh: test_bitmap_cases
      
2:  bdae873eaab = 3:  069c50d3370 pack-objects: extract `record_tree_depth()` helper
3:  a642305e3c9 = 4:  ae57607b57f pack-objects: support `--delta-islands` with `--path-walk`

base-commit: 45a9ecee26839cc880fdd5e704339dd3cf4ffc26

p5311 measures the cost of serving a fetch from a bitmapped pack and indexing the resulting pack on the client. Since 761416ef91d (bitmap-lookup-table: add performance tests for lookup table, 2022-08-14), p5311 effectively runs itself twice: once with the bitmap's lookup table extension enabled, and again with it disabled.

This comparison has served its useful purpose, as the lookup table is almost four years old, and the de-facto default in server-side Git deployments.

A following commit will want to test a different combination (repacking with and without '--path-walk' instead of the lookup table). Instead of multiplying the current test count by two again to produce four variations of `test_fetch_bitmaps()`, drop the lookup table option to reduce the number of perf tests we run. Retain `test_fetch_bitmaps()` itself, since we will use this in the future for the new parameterization.

(As an aside, a future commit outside of this series will adjust the default value of 'pack.writeBitmapLookupTable' to "true", matching the de-facto norm for deployments where the existence of bitmap lookup tables is meaningful. Punt on that to a later series and instead make the minimal change for now.)

Suggested-by: Derrick Stolee <stolee@gmail.com>
Signed-off-by: Taylor Blau <me@ttaylorr.com>
---
 t/perf/p5311-pack-bitmaps-fetch.sh | 8 +++-----
 1 file changed, 3 insertions(+), 5 deletions(-)

When 'pack-objects' is invoked with '--path-walk', it prevents us from using reachability bitmaps.

This behavior dates back to 70664d2865c (pack-objects: add --path-walk option, 2025-05-16), which included a comment in the relevant portion of the command-line arguments handling that read as follows:

    /*
     * We must disable the bitmaps because we are removing
     * the --objects / --objects-edge[-aggressive] options.
     */

In fb2c309b7d3 (pack-objects: pass --objects with --path-walk, 2026-05-02), path-walk learned to pass '--objects' again, but still kept bitmap traversal disabled. That leaves two useful cases unsupported:

 * A path-walk repack that writes bitmaps does not give the bitmap
   selector any commits, because path-walk reveals commits through
   `add_objects_by_path()` rather than through `show_commit()`, where
   `index_commit_for_bitmap()` is normally called.

 * An invocation like "git pack-objects --use-bitmap-index --path-walk"
   never tries an existing bitmap, even when one is available and could
   answer the request.

Fortunately for us, neither restriction is required.

 * On the writing side: teach the path-walk object callback to call
   `index_commit_for_bitmap()` for commits that it adds to the pack.
   That gives the bitmap selector the commit candidates it would have
   seen from the regular traversal.

 * For bitmap reading, keep passing '--objects' to the internal rev_list
   machinery, but stop clearing `use_bitmap_index`. If an existing
   bitmap can answer the request, use it; otherwise fall back to
   path-walk's own enumeration.

As a result, we can see significantly reduced pack sizes from p5311 before this commit:

    Test                                      HEAD^             HEAD
    ----------------------------------------------------------------------------------
    5311.38: server (1 days, --path-walk)     2.56(2.52+0.03)   0.01(0.01+0.00) -99.6%
    5311.39: size   (1 days, --path-walk)              123.9K            123.9K +0.0%
    5311.40: client (1 days, --path-walk)     0.00(0.01+0.00)   0.00(0.00+0.00) =
    5311.42: server (2 days, --path-walk)     2.57(2.52+0.05)   0.01(0.01+0.00) -99.6%
    5311.43: size   (2 days, --path-walk)              123.9K            123.9K +0.0%
    5311.44: client (2 days, --path-walk)     0.00(0.00+0.00)   0.00(0.00+0.00) =
    5311.46: server (4 days, --path-walk)     2.58(2.51+0.07)   0.01(0.01+0.00) -99.6%
    5311.47: size   (4 days, --path-walk)              123.9K            123.9K +0.0%
    5311.48: client (4 days, --path-walk)     0.00(0.00+0.00)   0.00(0.00+0.00) =
    5311.50: server (8 days, --path-walk)     2.58(2.53+0.04)   0.02(0.02+0.00) -99.2%
    5311.51: size   (8 days, --path-walk)              152.4K            152.4K +0.0%
    5311.52: client (8 days, --path-walk)     0.00(0.01+0.00)   0.00(0.01+0.00) =
    5311.54: server (16 days, --path-walk)    2.58(2.52+0.05)   0.03(0.02+0.00) -98.8%
    5311.55: size   (16 days, --path-walk)             205.3K            205.3K +0.0%
    5311.56: client (16 days, --path-walk)    0.01(0.01+0.00)   0.01(0.01+0.00) +0.0%
    5311.58: server (32 days, --path-walk)    2.59(2.53+0.06)   0.03(0.03+0.00) -98.8%
    5311.59: size   (32 days, --path-walk)             209.3K            209.3K +0.0%
    5311.60: client (32 days, --path-walk)    0.01(0.02+0.00)   0.01(0.02+0.00) +0.0%
    5311.62: server (64 days, --path-walk)    2.70(2.76+0.06)   0.16(0.24+0.04) -94.1%
    5311.63: size   (64 days, --path-walk)               4.1M              4.1M +0.0%
    5311.64: client (64 days, --path-walk)    0.44(0.50+0.02)   0.44(0.51+0.02) +0.0%
    5311.66: server (128 days, --path-walk)   2.88(3.20+0.05)   0.34(0.65+0.05) -88.2%
    5311.67: size   (128 days, --path-walk)              9.0M              9.0M -0.0%
    5311.68: client (128 days, --path-walk)   0.93(1.22+0.07)   0.93(1.20+0.08) +0.0%

We get the same size of output pack, but this commit allows us to do so in a significantly shorter amount of time. Intuitively, we're generating the same pack (hence the unchanged 'test_size' output from run to run), but varying how we get there. Before this commit, pack-objects prefers '--path-walk' to '--use-bitmap-index', so we generate the output pack by performing a normal '--path-walk' traversal. With this commit, we are operating over a *repacked* state (that itself was done with a '--path-walk' traversal), but are able to perform pack-reuse on that repacked state via bitmaps.

There is one wrinkle when it comes to '--boundary', which we must not pass into the bitmap walk in the presence of both '--path-walk' and '--use-bitmap-index'. Path-walk needs boundary commits when it performs its own traversal, in order to discover bases for thin packs, but the bitmap traversal does not expect this. Work around this by setting `revs->boundary` as late as possible within the '--path-walk' traversal, after any bitmap attempt has either succeeded or declined to answer the request.

Signed-off-by: Taylor Blau <me@ttaylorr.com>
---
 Documentation/git-pack-objects.adoc |  6 +++--
 builtin/pack-objects.c              | 18 +++++++++++++--
 t/perf/p5311-pack-bitmaps-fetch.sh  | 14 +++++++----
 t/t5310-pack-bitmaps.sh             | 36 +++++++++++++++++++++++++++++
 4 files changed, 66 insertions(+), 8 deletions(-)

Prepare for a subsequent change that needs to record tree depths from a second call site by factoring the delta-islands tree-depth bookkeeping out of `show_object()` and into a helper, `record_tree_depth()`.

The helper looks up the object in `to_pack`, returns early when the object was not added there, computes the depth from the slash count in the supplied name, and preserves the existing max-depth-wins behavior when a tree is reached by more than one path.

Signed-off-by: Taylor Blau <me@ttaylorr.com>
---
 builtin/pack-objects.c | 32 ++++++++++++++++++--------------
 1 file changed, 18 insertions(+), 14 deletions(-)

Since the inception of `--path-walk`, this option has had a documented incompatibility with `--delta-islands`.

When discussing those original patches on the list, a message from Stolee in [1] noted the following:

    this could be remedied by [...] doing a separate walk to identify
    islands using the normal method

In a related portion of the thread, Peff explains[2]:

    The delta islands code already does its own tree walk to propagate
    the bits down (it does rely on the base walk's show_commit() to
    propagate through the commits).

    Once each object has its island bitmaps, I think however you
    choose to come up with delta candidates [...] you should be able
    to use it. It's fundamentally just answering the question of "am
    I allowed to delta between these two objects".

That is similar to what this patch does, and it turns out the cheaper option is sufficient: perform the same island side effects from the path-walk callback rather than doing a second walk.

Recall how delta-islands are computed during a normal repack:

 - `show_commit()` calls `propagate_island_marks()` for each commit,
   which merges the commit's island bitset onto its root tree object and
   onto each of its parent commits.

 - `show_object()` for a tree records the tree's depth derived from the
   slash-separated pathname. Subsequent `resolve_tree_islands()` uses
   that depth to walk trees in increasing-depth order, propagating each
   tree's marks to its children.

 - At delta-search time, `in_same_island()` enforces that a delta
   target's island bitmap is a subset of its base's: every island that
   reaches the target must also reach the base.

Path-walk's enumeration callback is `add_objects_by_path()`. It already adds objects to `to_pack`, but until now did not perform the island-related side effects. Two things are needed:

 - For each commit batch, call `propagate_island_marks()` on commits,
   exactly as `show_commit()` does.

   We have to be careful about the order in which we call this function,
   and we must see a commit before its parents in order to have
   island marks to propagate.

   The path-walk batch preserves that order. Path-walk appends commits
   to its `OBJ_COMMIT` batch as they come back from the same
   `get_revision()` loop the regular traversal uses, and
   `add_objects_by_path()` iterates the batch in array order. So every
   commit reaches `propagate_island_marks()` in the same sequence that
   `show_commit()` would have seen it, and the descendant-first chain
   that the algorithm relies on is intact.

   Skip island propagation for excluded commits to match the regular
   traversal, whose `show_commit()` callback is only invoked for
   interesting commits. Boundary commits may still be present in
   path-walk's callback so they can serve as thin-pack bases, but they
   should not contribute island marks.

 - For each tree batch, record the tree's depth from the path. Use the
   `record_tree_depth()` helper from the previous commit so both
   callbacks behave identically, including the max-depth-wins behavior
   when a tree is reached via more than one path. The helper accepts
   both the `show_object()` path shape ("foo", "foo/bar") and the
   path-walk shape with a trailing slash ("foo/", "foo/bar/"), so depths
   recorded from either traversal mode are directly comparable.

   This is implicit in the implementation sketch from Peff above.
   `resolve_tree_islands()` sorts trees by `oe->tree_depth` in
   increasing-depth order before propagating marks down, so that a
   parent tree's marks are finalized before its children inherit them.
   Without recording the depth at path-walk time, every
   path-walk-discovered tree would land at depth 0 in `to_pack`, the
   sort would lose its ordering, and children could inherit marks from
   parents whose own contributions had not yet been merged in.

With those two pieces in place, `resolve_tree_islands()` receives the same island inputs from path-walk as it would from the regular traversal, so the existing island checks can be reused unchanged.

Drop the documented incompatibility between `--path-walk` and `--delta-islands`, and add t5320 coverage for path-walk island repacks with and without bitmap writing, as well as the same-island case where a delta remains allowed.

[1]: https://lore.kernel.org/git/9aa2471b-0850-4707-9733-d3b33609f5f2@gmail.com/ [2]: https://lore.kernel.org/git/20240911063203.GA1538586@coredump.intra.peff.net/

Signed-off-by: Taylor Blau <me@ttaylorr.com>
---
 Documentation/git-pack-objects.adoc | 14 +++++++-------
 builtin/pack-objects.c              | 22 ++++++++++++++++++----
 t/t5320-delta-islands.sh            | 29 +++++++++++++++++++++++++++++
 3 files changed, 54 insertions(+), 11 deletions(-)

On 6/2/2026 6:21 PM, Taylor Blau wrote:

I mentioned this before, but the pack _sizes_ aren't changing in this example. We are computing them more quickly, though.

Since we are testing --path-walk on both sides, the change across this commit is that we are using the bitmaps for the "counting objects" phase and then potentially using the --path-walk algorithm to construct the packfile.

The fact that the packfile sizes are _identical_ is suspicious to me. I'd expect some amount of difference here due to the change in algorithm. It's possible that this could be explained by the repository shape not getting any benefit from --path-walk because there are no name-hash collisions to worry about.

The one thing that might be hinting towards _some_ difference is that the relative sizes are showing as both "+0.0%" and "-0.0%", so perhaps the exact sizes do have differences that are hidden behind the human-readable sizes: 4.1M -> 4.1M is +0.0% but 9.0M -> 9.0M is -0.0%.

Ok, you have the correct interpretation here, just a lingering typo in the earlier sentence before the table.

And I wonder if the test setup creates a situation where we are always reusing deltas from the underlying packfile, so the --path-walk algorithm isn't doing anything to help with delta compression at this point and the difference in this patch is that we are replacing the object reachability calculation entirely with bitmaps.

I suppose what I'm really worried about is that I'm hoping to see some evidence from a large-scale test that demonstrates that the two algorithms are working in tandem in a non-trivial way. I haven't seen it yet, but I also don't have evidence that they _aren't_ working together.

Thanks, -Stolee

On 6/2/2026 6:21 PM, Taylor Blau wrote:

My earlier response focused on the _use_ of bitmaps when creating a packfile, but your patch also enables _writing_ bitmaps with the --path-walk option, which is significant and potentially more interesting from my perspective: we have evidence that --path-walk can produce significantly smaller packfiles than the standard algorithm, and once those packfiles are created we can benefit from that size in later packfile creation steps by reusing those deltas.

In this sense, I think the _writing_ is more important during a repack scenario. The fetch/clone scenarios can benefit directly even without integrating --path-walk with --use-bitmap-indexes.

...

My earlier reply to this patch was focused on the performance results when using the "reading bitmaps" case, and I expressed suspicion about the "exact" sizes of the packfiles.

Even more important here is that we have demonstrated examples of repos that change their packfile size when using the --path-walk method. We should demonstrate that the size continues to shrink with --path-walk even when producing a matching .bitmap file with --write-bitmap-index.

The other thing that I notice here is that the bitmaps will need to compute their reachable object set independently from the path-walk algorithm. But I suppose that already happens separately from the revision-walk approach that normally produces the packfile contents.

Note: A lot of my thoughts around asking for more evidence here is
that this patch seems suspiciously simple for integrating two
complicated features. The test suite (especially with
GIT_TEST_PACK_PATH_WALK=1) helps to guarantee that the result is
_correct_, but with performance features like this it's not enough to
"just" be correct. I want to see that we're having the intended
results.

From my perspective, the point of integrating these two things are:

1. Reachability bitmaps make it much faster to discover the reachable
   set and reuse bits of existing packfiles. (Your performance table
   demonstrates this is true.)

2. The --path-walk option can shrink packfile sizes by grouping
   trees and blobs by path before those paths collide in the name-hash
   sort. (I haven't seen evidence that this is happening.)

With evidence of (1) and not (2), it's not clear from the data that these features are integrating completely. Without looking at the code, those numbers would be the same if we had instead swapped the preference of "the --path-walk option disables bitmaps" to "bitmaps disable --path-walk".

Finally, I'll just note that I don't expect the _bitmaps_ to change size dramatically. The --path-walk option does change the order of the objects for its first pass of delta compression, but then uses the (name-hash, size) sort to finalize the object ordering, so the final object ordering _should_ be the same (unless I'm mistaken, in which case the bitmaps could change size due to bitmap compression concerns).

Thanks, -Stolee

Taylor Blau <me@ttaylorr.com> writes:

This gets flagged by updated test linter X-<. Use test_grep to pacify it.

On Mon, Jun 15, 2026 at 01:57:28PM -0700, Junio C Hamano wrote:

Oops, thanks for spotting.

Thanks, Taylor

On Fri, Jun 12, 2026 at 09:03:41AM -0400, Derrick Stolee wrote:

Thanks for pointing this out. The paragraph following the perf output below correctly explains the results ("We get the same size of output pack, but [...]"), but this one is obviously wrong.

I'm not sure I agree here. Because we are using bitmaps, we're relying on pack-reuse to construct the output pack, not --path-walk. I mentioned in git-pack-objects(1), but the combination of seeing "--path-walk" and "--use-bitmap-index" together only means that we will use a path-walk traversal as fallback if we can't get an answer by relying on bitmaps.

Your thinking is correct here that the test setup intentionally creates a situation where we are reusing objects/deltas verbatim from the bitmapped pack.

I'm not sure what "working in tandem" means here. At read time, the two options mutually exclude one another, meaning we'll use bitmaps if we have them, or do a path-walk traversal otherwise (or if the bitmaps we have are somehow insufficient to perform the traversal).

The goal of this patch is not to demonstrate that the two work together at the same time, but rather that we can write a pack using --path-walk, and generate reachability bitmaps simultaneously.

Let me know if you have more thoughts on what "working together in a non-trivial" way would look like here. If there are ways to improve the compatibility of these two features in a way that yields better performance via either smaller packs, faster generation, or both, I'm all ears :-).

Thanks, Taylor

On Fri, Jun 12, 2026 at 09:24:32AM -0400, Derrick Stolee wrote:

I am perhaps splitting hairs here, but I would frame the use of bitmaps when reading with "--path-walk" as "either/or" not "both/and". The main goal of this patch is to enable us to still generate bitmaps when *writing* a pack with "--path-walk".

That's fair. One way to do this would be to:

--- 8< ---

On 6/19/2026 10:16 AM, Taylor Blau wrote:

I guess my thought was that we'd construct bitmaps when they are available, but how do we walk objects to get the objects for commits that are not represented by bitmaps?

But you make a good point: we don't need to do that for functional use: the bitmap code does an object walk to produce a bitmap, and it's all in a layer "below" the pack-objects code.

So essentially, this _isn't_ a combined approach: it's "use bitmaps if we can, and fall back to --path-walk if we can't" which is changing from our previous behavior of "--path-walk means we don't try to use bitmaps".

Thanks, -Stolee

On 6/19/2026 10:28 AM, Taylor Blau wrote:

Yes. I was confused but your response to the earlier thread made this more clear. I'm no longer confused.

This sort of thing does help to show that we're getting different behavior when repacking with and without --path-walk. And this test is showing the slightest change for git.git, but is likely more impactful for the other repos I've used to demonstrate the benefits.

So this is the kind of data I'm hoping to see, but also with data from other repos whose data shapes benefit from --path-walk more than git.git and repos where name-hash v1 is sufficient to give a similar result.

I'd also like to see if the repack _time_ changes with this, but these direct size comparisons are the biggest indicator I'd like to see.

Yes, the perf test modification and data reporting is the only missing thing at this point. You've helped me better understand the "integration" between the features during fetches and clones.

Thanks, -Stolee

On Fri, Jun 19, 2026 at 10:36:54AM -0400, Derrick Stolee wrote:

Good question, and we use the existing bitmap traversal (or the boundary-based one, if enabled). In that case we really want something that is topological and not path-based, so we can terminate the walk as soon as we run into an existing set bit, or something on the negated side of the query.

Exactly!

Thanks, Taylor

On Fri, Jun 19, 2026 at 10:40:51AM -0400, Derrick Stolee wrote:

I'm glad this is the sort of data you're looking for. I'm happy to run this on other repositories.

Unfortunately a timing comparison is kind of a pain here. We'd have to use test_perf, which will perform the same repack multiple times. We could do that, though it's wasteful, and changes like bf4a60874af (p5326: generate pack bitmaps before writing the MIDX bitmap, 2021-09-17) move us in the opposite direction.

I'm not opposed to changing this to test_perf if you feel strongly about it.

Thanks, Taylor

On 6/19/2026 10:52 AM, Taylor Blau wrote:

Repacking is expensive and time-consuming. I care a bit about it, but not as much as I care about the size difference. Feel free to skip the time performance impact for now.

Thanks, -Stolee

Note to the maintainer:

 * This series is still based on 'ds/path-walk-filters' with Patrick's
   'ps/clang-w-glibc-2.43-and-_Generic' merged in.

Here is another small reroll of my series to make `--path-walk` work with reachability bitmaps and delta-islands.

This round addresses Stolee's request to demonstrate the repack-size side of the integration between `--path-walk` and bitmap writing, and fixes an errant "grep" in the test suite.

Changes since v2 include:

 * p5311 now forces a fresh repack with '-F' when building its bitmapped
   test repository. This avoids reusing deltas from a non-'--path-walk'
   pack when we are trying to measure a pack produced by `--path-walk`.

 * p5311 now records the size of the bitmapped pack, both with and
   without `--path-walk`, to show that writing bitmaps during a
   `--path-walk` repack does not lose the pack-size improvement that
   `--path-walk` provides in repositories where it helps.

 * The second patch's commit message has updated p5311 numbers from a
   recent fluentui clone, fixing the "pack sizes" typo and documenting
   the new bitmapped-pack-size comparison.

 * The t5310 grep assertion now uses `test_grep`, as suggested by Junio.

Outside of the above, the series is functionally unchanged.

Thanks in advance for another look.

Taylor Blau (4):
  t/perf: drop p5311's lookup-table permutation
  pack-objects: support reachability bitmaps with `--path-walk`
  pack-objects: extract `record_tree_depth()` helper
  pack-objects: support `--delta-islands` with `--path-walk`

 Documentation/git-pack-objects.adoc | 12 ++---
 builtin/pack-objects.c              | 68 +++++++++++++++++++++--------
 t/perf/p5311-pack-bitmaps-fetch.sh  | 24 ++++++----
 t/t5310-pack-bitmaps.sh             | 36 +++++++++++++++
 t/t5320-delta-islands.sh            | 29 ++++++++++++
 5 files changed, 138 insertions(+), 31 deletions(-)

Range-diff against v2:
1:  52d63e8910e = 1:  b1dbf30ddbe t/perf: drop p5311's lookup-table permutation
2:  ffad584a43e ! 2:  1884f495809 pack-objects: support reachability bitmaps with `--path-walk`
    @@ Commit message
            bitmap can answer the request, use it; otherwise fall back to
            path-walk's own enumeration.
     
    -    As a result, we can see significantly reduced pack sizes from p5311
    -    before this commit:
    +    As a result, we can see significantly reduced pack generation times from
    +    p5311 (with our `GIT_PERF_REPO` set to a recent clone of the fluentui
    +    repository) before this commit:
     
    -        Test                                      HEAD^             HEAD
    -        ----------------------------------------------------------------------------------
    -        5311.38: server (1 days, --path-walk)     2.56(2.52+0.03)   0.01(0.01+0.00) -99.6%
    -        5311.39: size   (1 days, --path-walk)              123.9K            123.9K +0.0%
    -        5311.40: client (1 days, --path-walk)     0.00(0.01+0.00)   0.00(0.00+0.00) =
    -        5311.42: server (2 days, --path-walk)     2.57(2.52+0.05)   0.01(0.01+0.00) -99.6%
    -        5311.43: size   (2 days, --path-walk)              123.9K            123.9K +0.0%
    -        5311.44: client (2 days, --path-walk)     0.00(0.00+0.00)   0.00(0.00+0.00) =
    -        5311.46: server (4 days, --path-walk)     2.58(2.51+0.07)   0.01(0.01+0.00) -99.6%
    -        5311.47: size   (4 days, --path-walk)              123.9K            123.9K +0.0%
    -        5311.48: client (4 days, --path-walk)     0.00(0.00+0.00)   0.00(0.00+0.00) =
    -        5311.50: server (8 days, --path-walk)     2.58(2.53+0.04)   0.02(0.02+0.00) -99.2%
    -        5311.51: size   (8 days, --path-walk)              152.4K            152.4K +0.0%
    -        5311.52: client (8 days, --path-walk)     0.00(0.01+0.00)   0.00(0.01+0.00) =
    -        5311.54: server (16 days, --path-walk)    2.58(2.52+0.05)   0.03(0.02+0.00) -98.8%
    -        5311.55: size   (16 days, --path-walk)             205.3K            205.3K +0.0%
    -        5311.56: client (16 days, --path-walk)    0.01(0.01+0.00)   0.01(0.01+0.00) +0.0%
    -        5311.58: server (32 days, --path-walk)    2.59(2.53+0.06)   0.03(0.03+0.00) -98.8%
    -        5311.59: size   (32 days, --path-walk)             209.3K            209.3K +0.0%
    -        5311.60: client (32 days, --path-walk)    0.01(0.02+0.00)   0.01(0.02+0.00) +0.0%
    -        5311.62: server (64 days, --path-walk)    2.70(2.76+0.06)   0.16(0.24+0.04) -94.1%
    -        5311.63: size   (64 days, --path-walk)               4.1M              4.1M +0.0%
    -        5311.64: client (64 days, --path-walk)    0.44(0.50+0.02)   0.44(0.51+0.02) +0.0%
    -        5311.66: server (128 days, --path-walk)   2.88(3.20+0.05)   0.34(0.65+0.05) -88.2%
    -        5311.67: size   (128 days, --path-walk)              9.0M              9.0M -0.0%
    -        5311.68: client (128 days, --path-walk)   0.93(1.22+0.07)   0.93(1.20+0.08) +0.0%
    +        Test                                            HEAD^             HEAD
    +        ----------------------------------------------------------------------------------------
    +        5311.40: server (1 days, --path-walk)           1.43(1.39+0.04)   0.01(0.01+0.00) -99.3%
    +        5311.41: size   (1 days, --path-walk)                    139.6K            139.7K +0.0%
    +        5311.42: client (1 days, --path-walk)           0.02(0.02+0.00)   0.02(0.02+0.00) +0.0%
    +        5311.44: server (2 days, --path-walk)           1.43(1.39+0.04)   0.01(0.00+0.00) -99.3%
    +        5311.45: size   (2 days, --path-walk)                    139.6K            139.7K +0.0%
    +        5311.46: client (2 days, --path-walk)           0.02(0.02+0.00)   0.02(0.02+0.00) +0.0%
    +        5311.48: server (4 days, --path-walk)           1.44(1.39+0.04)   0.01(0.01+0.00) -99.3%
    +        5311.49: size   (4 days, --path-walk)                    238.1K            238.1K +0.0%
    +        5311.50: client (4 days, --path-walk)           0.03(0.03+0.00)   0.03(0.03+0.00) +0.0%
    +        5311.52: server (8 days, --path-walk)           1.43(1.39+0.03)   0.01(0.00+0.00) -99.3%
    +        5311.53: size   (8 days, --path-walk)                    344.9K            344.9K +0.0%
    +        5311.54: client (8 days, --path-walk)           0.07(0.07+0.00)   0.07(0.08+0.00) +0.0%
    +        5311.56: server (16 days, --path-walk)          1.47(1.44+0.03)   0.10(0.08+0.01) -93.2%
    +        5311.57: size   (16 days, --path-walk)                   844.0K            844.0K +0.0%
    +        5311.58: client (16 days, --path-walk)          0.09(0.09+0.00)   0.09(0.09+0.00) +0.0%
    +        5311.60: server (32 days, --path-walk)          1.52(1.50+0.05)   0.14(0.15+0.02) -90.8%
    +        5311.61: size   (32 days, --path-walk)                     4.2M              4.2M +0.1%
    +        5311.62: client (32 days, --path-walk)          0.34(0.48+0.02)   0.34(0.45+0.05) +0.0%
    +        5311.64: server (64 days, --path-walk)          1.55(1.52+0.06)   0.15(0.15+0.04) -90.3%
    +        5311.65: size   (64 days, --path-walk)                     6.4M              6.4M -0.0%
    +        5311.66: client (64 days, --path-walk)          0.51(0.79+0.05)   0.51(0.80+0.06) +0.0%
    +        5311.68: server (128 days, --path-walk)         1.59(1.57+0.06)   0.16(0.21+0.01) -89.9%
    +        5311.69: size   (128 days, --path-walk)                    8.4M              8.4M -0.0%
    +        5311.70: client (128 days, --path-walk)         0.72(1.44+0.08)   0.71(1.47+0.09) -1.4%
     
         We get the same size of output pack, but this commit allows us to do so
         in a significantly shorter amount of time. Intuitively, we're generating
    @@ Commit message
         '--path-walk' traversal), but are able to perform pack-reuse on that
         repacked state via bitmaps.
     
    +    When comparing the size of the repacked pack with/without '--path-walk'
    +    on the previous commit versus this one, we see that (a) the repacked size
    +    improves significantly with '--path-walk', and that (b) writing bitmaps
    +    during repacking does not regress this improvement:
    +
    +        Test                                            HEAD^             HEAD
    +        ----------------------------------------------------------------------------------------
    +        5311.3: size of bitmapped pack                           558.4M            558.5M +0.0%
    +        5311.38: size of bitmapped pack (--path-walk)            164.4M            164.4M +0.0%
    +
    +    (Note that to observe an improvement here, we must repack with '-F' in
    +    order to avoid reusing non-'--path-walk' deltas, which would otherwise
    +    skew our results.)
    +
         There is one wrinkle when it comes to '--boundary', which we must not
         pass into the bitmap walk in the presence of both '--path-walk' and
         '--use-bitmap-index'. Path-walk needs boundary commits when it performs
    @@ t/perf/p5311-pack-bitmaps-fetch.sh: test_description='performance of fetches fro
     +	test_expect_success "create bitmapped server repo ${argv:+($argv)}" '
      		git config pack.writebitmaps true &&
     -		git repack -ad
    -+		git repack -ad $argv
    ++		git repack -adF $argv
    ++	'
    ++
    ++	test_size "size of bitmapped pack ${argv:+($argv)}" '
    ++		test_file_size .git/objects/pack/pack-*.pack
      	'
      
      	# simulate a fetch from a repository that last fetched N days ago, for
    @@ t/t5310-pack-bitmaps.sh: test_bitmap_cases
     +			git -c pack.allowPackReuse=$reuse pack-objects \
     +				--stdout --revs --path-walk --use-bitmap-index \
     +				<in >out.pack &&
    -+			grep "\"category\":\"bitmap\",\"key\":\"bitmap/hits\"" trace.txt &&
    ++			test_grep "\"category\":\"bitmap\",\"key\":\"bitmap/hits\"" trace.txt &&
     +
     +			git index-pack out.pack &&
     +
3:  069c50d3370 = 3:  315ee0b1988 pack-objects: extract `record_tree_depth()` helper
4:  ae57607b57f = 4:  371fc4317ad pack-objects: support `--delta-islands` with `--path-walk`

base-commit: 45a9ecee26839cc880fdd5e704339dd3cf4ffc26

p5311 measures the cost of serving a fetch from a bitmapped pack and indexing the resulting pack on the client. Since 761416ef91d (bitmap-lookup-table: add performance tests for lookup table, 2022-08-14), p5311 effectively runs itself twice: once with the bitmap's lookup table extension enabled, and again with it disabled.

This comparison has served its useful purpose, as the lookup table is almost four years old, and the de-facto default in server-side Git deployments.

A following commit will want to test a different combination (repacking with and without '--path-walk' instead of the lookup table). Instead of multiplying the current test count by two again to produce four variations of `test_fetch_bitmaps()`, drop the lookup table option to reduce the number of perf tests we run. Retain `test_fetch_bitmaps()` itself, since we will use this in the future for the new parameterization.

(As an aside, a future commit outside of this series will adjust the default value of 'pack.writeBitmapLookupTable' to "true", matching the de-facto norm for deployments where the existence of bitmap lookup tables is meaningful. Punt on that to a later series and instead make the minimal change for now.)

Suggested-by: Derrick Stolee <stolee@gmail.com>
Signed-off-by: Taylor Blau <me@ttaylorr.com>
---
 t/perf/p5311-pack-bitmaps-fetch.sh | 8 +++-----
 1 file changed, 3 insertions(+), 5 deletions(-)

When 'pack-objects' is invoked with '--path-walk', it prevents us from using reachability bitmaps.

This behavior dates back to 70664d2865c (pack-objects: add --path-walk option, 2025-05-16), which included a comment in the relevant portion of the command-line arguments handling that read as follows:

    /*
     * We must disable the bitmaps because we are removing
     * the --objects / --objects-edge[-aggressive] options.
     */

In fb2c309b7d3 (pack-objects: pass --objects with --path-walk, 2026-05-02), path-walk learned to pass '--objects' again, but still kept bitmap traversal disabled. That leaves two useful cases unsupported:

 * A path-walk repack that writes bitmaps does not give the bitmap
   selector any commits, because path-walk reveals commits through
   `add_objects_by_path()` rather than through `show_commit()`, where
   `index_commit_for_bitmap()` is normally called.

 * An invocation like "git pack-objects --use-bitmap-index --path-walk"
   never tries an existing bitmap, even when one is available and could
   answer the request.

Fortunately for us, neither restriction is required.

 * On the writing side: teach the path-walk object callback to call
   `index_commit_for_bitmap()` for commits that it adds to the pack.
   That gives the bitmap selector the commit candidates it would have
   seen from the regular traversal.

 * For bitmap reading, keep passing '--objects' to the internal rev_list
   machinery, but stop clearing `use_bitmap_index`. If an existing
   bitmap can answer the request, use it; otherwise fall back to
   path-walk's own enumeration.

As a result, we can see significantly reduced pack generation times from p5311 (with our `GIT_PERF_REPO` set to a recent clone of the fluentui repository) before this commit:

    Test                                            HEAD^             HEAD
    ----------------------------------------------------------------------------------------
    5311.40: server (1 days, --path-walk)           1.43(1.39+0.04)   0.01(0.01+0.00) -99.3%
    5311.41: size   (1 days, --path-walk)                    139.6K            139.7K +0.0%
    5311.42: client (1 days, --path-walk)           0.02(0.02+0.00)   0.02(0.02+0.00) +0.0%
    5311.44: server (2 days, --path-walk)           1.43(1.39+0.04)   0.01(0.00+0.00) -99.3%
    5311.45: size   (2 days, --path-walk)                    139.6K            139.7K +0.0%
    5311.46: client (2 days, --path-walk)           0.02(0.02+0.00)   0.02(0.02+0.00) +0.0%
    5311.48: server (4 days, --path-walk)           1.44(1.39+0.04)   0.01(0.01+0.00) -99.3%
    5311.49: size   (4 days, --path-walk)                    238.1K            238.1K +0.0%
    5311.50: client (4 days, --path-walk)           0.03(0.03+0.00)   0.03(0.03+0.00) +0.0%
    5311.52: server (8 days, --path-walk)           1.43(1.39+0.03)   0.01(0.00+0.00) -99.3%
    5311.53: size   (8 days, --path-walk)                    344.9K            344.9K +0.0%
    5311.54: client (8 days, --path-walk)           0.07(0.07+0.00)   0.07(0.08+0.00) +0.0%
    5311.56: server (16 days, --path-walk)          1.47(1.44+0.03)   0.10(0.08+0.01) -93.2%
    5311.57: size   (16 days, --path-walk)                   844.0K            844.0K +0.0%
    5311.58: client (16 days, --path-walk)          0.09(0.09+0.00)   0.09(0.09+0.00) +0.0%
    5311.60: server (32 days, --path-walk)          1.52(1.50+0.05)   0.14(0.15+0.02) -90.8%
    5311.61: size   (32 days, --path-walk)                     4.2M              4.2M +0.1%
    5311.62: client (32 days, --path-walk)          0.34(0.48+0.02)   0.34(0.45+0.05) +0.0%
    5311.64: server (64 days, --path-walk)          1.55(1.52+0.06)   0.15(0.15+0.04) -90.3%
    5311.65: size   (64 days, --path-walk)                     6.4M              6.4M -0.0%
    5311.66: client (64 days, --path-walk)          0.51(0.79+0.05)   0.51(0.80+0.06) +0.0%
    5311.68: server (128 days, --path-walk)         1.59(1.57+0.06)   0.16(0.21+0.01) -89.9%
    5311.69: size   (128 days, --path-walk)                    8.4M              8.4M -0.0%
    5311.70: client (128 days, --path-walk)         0.72(1.44+0.08)   0.71(1.47+0.09) -1.4%

We get the same size of output pack, but this commit allows us to do so in a significantly shorter amount of time. Intuitively, we're generating the same pack (hence the unchanged 'test_size' output from run to run), but varying how we get there. Before this commit, pack-objects prefers '--path-walk' to '--use-bitmap-index', so we generate the output pack by performing a normal '--path-walk' traversal. With this commit, we are operating over a *repacked* state (that itself was done with a '--path-walk' traversal), but are able to perform pack-reuse on that repacked state via bitmaps.

When comparing the size of the repacked pack with/without '--path-walk' on the previous commit versus this one, we see that (a) the repacked size improves significantly with '--path-walk', and that (b) writing bitmaps during repacking does not regress this improvement:

    Test                                            HEAD^             HEAD
    ----------------------------------------------------------------------------------------
    5311.3: size of bitmapped pack                           558.4M            558.5M +0.0%
    5311.38: size of bitmapped pack (--path-walk)            164.4M            164.4M +0.0%

(Note that to observe an improvement here, we must repack with '-F' in order to avoid reusing non-'--path-walk' deltas, which would otherwise skew our results.)

There is one wrinkle when it comes to '--boundary', which we must not pass into the bitmap walk in the presence of both '--path-walk' and '--use-bitmap-index'. Path-walk needs boundary commits when it performs its own traversal, in order to discover bases for thin packs, but the bitmap traversal does not expect this. Work around this by setting `revs->boundary` as late as possible within the '--path-walk' traversal, after any bitmap attempt has either succeeded or declined to answer the request.

Signed-off-by: Taylor Blau <me@ttaylorr.com>
---
 Documentation/git-pack-objects.adoc |  6 +++--
 builtin/pack-objects.c              | 18 +++++++++++++--
 t/perf/p5311-pack-bitmaps-fetch.sh  | 18 +++++++++++----
 t/t5310-pack-bitmaps.sh             | 36 +++++++++++++++++++++++++++++
 4 files changed, 70 insertions(+), 8 deletions(-)

Prepare for a subsequent change that needs to record tree depths from a second call site by factoring the delta-islands tree-depth bookkeeping out of `show_object()` and into a helper, `record_tree_depth()`.

The helper looks up the object in `to_pack`, returns early when the object was not added there, computes the depth from the slash count in the supplied name, and preserves the existing max-depth-wins behavior when a tree is reached by more than one path.

Signed-off-by: Taylor Blau <me@ttaylorr.com>
---
 builtin/pack-objects.c | 32 ++++++++++++++++++--------------
 1 file changed, 18 insertions(+), 14 deletions(-)

Since the inception of `--path-walk`, this option has had a documented incompatibility with `--delta-islands`.

When discussing those original patches on the list, a message from Stolee in [1] noted the following:

    this could be remedied by [...] doing a separate walk to identify
    islands using the normal method

In a related portion of the thread, Peff explains[2]:

    The delta islands code already does its own tree walk to propagate
    the bits down (it does rely on the base walk's show_commit() to
    propagate through the commits).

    Once each object has its island bitmaps, I think however you
    choose to come up with delta candidates [...] you should be able
    to use it. It's fundamentally just answering the question of "am
    I allowed to delta between these two objects".

That is similar to what this patch does, and it turns out the cheaper option is sufficient: perform the same island side effects from the path-walk callback rather than doing a second walk.

Recall how delta-islands are computed during a normal repack:

 - `show_commit()` calls `propagate_island_marks()` for each commit,
   which merges the commit's island bitset onto its root tree object and
   onto each of its parent commits.

 - `show_object()` for a tree records the tree's depth derived from the
   slash-separated pathname. Subsequent `resolve_tree_islands()` uses
   that depth to walk trees in increasing-depth order, propagating each
   tree's marks to its children.

 - At delta-search time, `in_same_island()` enforces that a delta
   target's island bitmap is a subset of its base's: every island that
   reaches the target must also reach the base.

Path-walk's enumeration callback is `add_objects_by_path()`. It already adds objects to `to_pack`, but until now did not perform the island-related side effects. Two things are needed:

 - For each commit batch, call `propagate_island_marks()` on commits,
   exactly as `show_commit()` does.

   We have to be careful about the order in which we call this function,
   and we must see a commit before its parents in order to have
   island marks to propagate.

   The path-walk batch preserves that order. Path-walk appends commits
   to its `OBJ_COMMIT` batch as they come back from the same
   `get_revision()` loop the regular traversal uses, and
   `add_objects_by_path()` iterates the batch in array order. So every
   commit reaches `propagate_island_marks()` in the same sequence that
   `show_commit()` would have seen it, and the descendant-first chain
   that the algorithm relies on is intact.

   Skip island propagation for excluded commits to match the regular
   traversal, whose `show_commit()` callback is only invoked for
   interesting commits. Boundary commits may still be present in
   path-walk's callback so they can serve as thin-pack bases, but they
   should not contribute island marks.

 - For each tree batch, record the tree's depth from the path. Use the
   `record_tree_depth()` helper from the previous commit so both
   callbacks behave identically, including the max-depth-wins behavior
   when a tree is reached via more than one path. The helper accepts
   both the `show_object()` path shape ("foo", "foo/bar") and the
   path-walk shape with a trailing slash ("foo/", "foo/bar/"), so depths
   recorded from either traversal mode are directly comparable.

   This is implicit in the implementation sketch from Peff above.
   `resolve_tree_islands()` sorts trees by `oe->tree_depth` in
   increasing-depth order before propagating marks down, so that a
   parent tree's marks are finalized before its children inherit them.
   Without recording the depth at path-walk time, every
   path-walk-discovered tree would land at depth 0 in `to_pack`, the
   sort would lose its ordering, and children could inherit marks from
   parents whose own contributions had not yet been merged in.

With those two pieces in place, `resolve_tree_islands()` receives the same island inputs from path-walk as it would from the regular traversal, so the existing island checks can be reused unchanged.

Drop the documented incompatibility between `--path-walk` and `--delta-islands`, and add t5320 coverage for path-walk island repacks with and without bitmap writing, as well as the same-island case where a delta remains allowed.

[1]: https://lore.kernel.org/git/9aa2471b-0850-4707-9733-d3b33609f5f2@gmail.com/ [2]: https://lore.kernel.org/git/20240911063203.GA1538586@coredump.intra.peff.net/

Signed-off-by: Taylor Blau <me@ttaylorr.com>
---
 Documentation/git-pack-objects.adoc | 14 +++++++-------
 builtin/pack-objects.c              | 22 ++++++++++++++++++----
 t/t5320-delta-islands.sh            | 29 +++++++++++++++++++++++++++++
 3 files changed, 54 insertions(+), 11 deletions(-)

Taylor Blau <me@ttaylorr.com> writes:

Very cleanly implemented. I am not confident that I have followed the detailed logic around delta islands in the last step but the earlier three patches looked trivially good.

Thanks.  Will replace.

On 6/22/2026 3:35 AM, Junio C Hamano wrote:

I've been happy with the code, subject to the new data that is presented with this version confirming the expected performance benefits. I also lack confidence in the delta islands features, but based on my weak understanding it looks correct. I believe that Taylor has the right expertise here to make up for my lack of context.

Thanks, -Stolee

Derrick Stolee <stolee@gmail.com> writes:

Thanks.  Let me mark the topic for 'next' then.