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

Re: [PATCH v2 2/4] pack-objects: support reachability bitmaps with `--path-walk`

From
Taylor Blau <me@ttaylorr.com>
Date
Jun 19, 2026, 14:28 UTC
Message-ID
<ajVSHvL+On9AEV+g@nand.local>
In-Reply-To
<849c659f-efa8-430a-bfac-0c26a3ed1aaa@gmail.com>
On Fri, Jun 12, 2026 at 09:24:32AM -0400, Derrick Stolee wrote:
Show 11 quoted lines
> On 6/2/2026 6:21 PM, Taylor Blau wrote:
> > When 'pack-objects' is invoked with '--path-walk', it prevents us from
> > using reachability bitmaps.
>
> My earlier response focused on the _use_ of bitmaps when creating a
> packfile, but your patch also enables _writing_ bitmaps with the
> --path-walk option, which is significant and potentially more
> interesting from my perspective: we have evidence that --path-walk
> can produce significantly smaller packfiles than the standard
> algorithm, and once those packfiles are created we can benefit from
> that size in later packfile creation steps by reusing those deltas.

I am perhaps splitting hairs here, but I would frame the use of bitmaps when reading with "--path-walk" as "either/or" not "both/and". The main goal of this patch is to enable us to still generate bitmaps when *writing* a pack with "--path-walk".

> Even more important here is that we have demonstrated examples of repos
> that change their packfile size when using the --path-walk method. We
> should demonstrate that the size continues to shrink with --path-walk
> even when producing a matching .bitmap file with --write-bitmap-index.
That's fair. One way to do this would be to:
--- 8< ---
diff --git a/t/perf/p5311-pack-bitmaps-fetch.sh b/t/perf/p5311-pack-bitmaps-fetch.sh
index 1b115d921a1..c1aed3e2aef 100755
--- a/t/perf/p5311-pack-bitmaps-fetch.sh
+++ b/t/perf/p5311-pack-bitmaps-fetch.sh
@@ -18,6 +18,10 @@ test_fetch_bitmaps () {
 		git repack -ad $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
 	# various values of N. We do so by following the first-parent chain,
 	# and assume the first entry in the chain that is N days older than the current
--- >8 ---

, which gives us:

    Test                                            HEAD^             HEAD
    ----------------------------------------------------------------------------------------
    5311.3: size of bitmapped pack                           278.8M            278.8M -0.0%
    5311.38: size of bitmapped pack (--path-walk)            278.7M            278.7M +0.0%

(eliding other tests). I considered whether there are other interesting
tests, but I think "repack" is the right layer to run perf tests, since
you're always writing a closed pack. We could try different subsets of
the repository's objects (which would also have to be closed), but I
don't think this is that interesting.

> The other thing that I notice here is that the bitmaps will need to
> compute their reachable object set independently from the path-walk
> algorithm. But I suppose that already happens separately from the
> revision-walk approach that normally produces the packfile contents.

Right. The only wrinkle here is how we handle the internal traversal's
"--boundary" option, but see the last paragraph in the commit message
for details on why the proposed approach is OK.

> >From my perspective, the point of integrating these two things are:
>
> 1. Reachability bitmaps make it much faster to discover the reachable
>    set and reuse bits of existing packfiles. (Your performance table
>    demonstrates this is true.)
>
> 2. The --path-walk option can shrink packfile sizes by grouping
>    trees and blobs by path before those paths collide in the name-hash
>    sort. (I haven't seen evidence that this is happening.)
>
> With evidence of (1) and not (2), it's not clear from the data that
> these features are integrating completely. Without looking at the
> code, those numbers would be the same if we had instead swapped the
> preference of "the --path-walk option disables bitmaps" to "bitmaps
> disable --path-walk".

Let me know if modifying the perf test as above (and including the
relevant results in the commit message) would be sufficient in
addressing your concern.

Thanks,
Taylor
Previous: Derrick StoleeNext: Derrick Stolee
Message 18 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.