[PATCH v3 0/4] pack-objects: support bitmaps and delta-islands with `--path-walk`

[Taylor Blau <me@ttaylorr.com>]

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