pack-objects: support bitmaps and delta-islands with `--path-walk`

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

2.54.0.23.g371fc4317ad