From: Taylor Blau Date: Sun, 21 Jun 2026 23:02:55 GMT Subject: [PATCH v3 0/4] pack-objects: support bitmaps and delta-islands with `--path-walk` Message-ID: In-Reply-To: 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 \ + 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 -- 2.54.0.23.g371fc4317ad