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

[Taylor Blau <me@ttaylorr.com>]

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
-- 
2.54.0.23.gae57607b57f