git/list[1] front-page[2] threads[3] people[4] search[5] about
 

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

From
Taylor Blau <me@ttaylorr.com>
Date
Jun 2, 2026, 22:21 UTC
Message-ID
<cover.1780438896.git.me@ttaylorr.com>
In-Reply-To
<cover.1779923907.git.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
Previous: Taylor BlauNext: Taylor Blau
Message 10 of 33 in “pack-objects: support bitmaps and delta-islands with `--path-walk`”
  1. 0/3 pack-objects: support bitmaps and delta-islands with `--path-walk`Taylor Blau, May 27, 2026
  2. 1/3 pack-objects: support reachability bitmaps with `--path-walk`Taylor Blau, May 27, 2026
  3. 2/3 pack-objects: extract `record_tree_depth()` helperTaylor Blau, May 27, 2026
  4. 3/3 pack-objects: support `--delta-islands` with `--path-walk`Taylor Blau, May 27, 2026
  5. Derrick StoleeMay 28, 2026
  6. Derrick StoleeMay 29, 2026
  7. Taylor BlauMay 29, 2026
  8. Derrick StoleeMay 29, 2026
  9. Taylor BlauMay 29, 2026
  10. 0/4 pack-objects: support bitmaps and delta-islands with `--path-walk`Taylor Blau, Jun 2, 2026
  11. 1/4 t/perf: drop p5311's lookup-table permutationTaylor Blau, Jun 2, 2026
  12. 2/4 pack-objects: support reachability bitmaps with `--path-walk`Taylor Blau, Jun 2, 2026
  13. Derrick StoleeJun 12, 2026
  14. Taylor BlauJun 19, 2026
  15. Derrick StoleeJun 19, 2026
  16. Taylor BlauJun 19, 2026
  17. Derrick StoleeJun 12, 2026
  18. Taylor BlauJun 19, 2026
  19. Derrick StoleeJun 19, 2026
  20. Taylor BlauJun 19, 2026
  21. Derrick StoleeJun 19, 2026
  22. Junio C HamanoJun 15, 2026
  23. Taylor BlauJun 19, 2026
  24. 3/4 pack-objects: extract `record_tree_depth()` helperTaylor Blau, Jun 2, 2026
  25. 4/4 pack-objects: support `--delta-islands` with `--path-walk`Taylor Blau, Jun 2, 2026
  26. 0/4 pack-objects: support bitmaps and delta-islands with `--path-walk`Taylor Blau, Jun 21, 2026
  27. 1/4 t/perf: drop p5311's lookup-table permutationTaylor Blau, Jun 21, 2026
  28. 2/4 pack-objects: support reachability bitmaps with `--path-walk`Taylor Blau, Jun 21, 2026
  29. 3/4 pack-objects: extract `record_tree_depth()` helperTaylor Blau, Jun 21, 2026
  30. 4/4 pack-objects: support `--delta-islands` with `--path-walk`Taylor Blau, Jun 21, 2026
  31. Junio C HamanoJun 22, 2026
  32. Derrick StoleeJun 22, 2026
  33. Junio C HamanoJun 22, 2026

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.