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
Derrick Stolee <stolee@gmail.com>
Date
Jun 12, 2026, 13:03 UTC
Message-ID
<6e4a8764-3c56-42c8-a87e-40a94c6c34e9@gmail.com>
In-Reply-To
<ffad584a43ebf3cb2138e8dce7daef84ab72712f.1780438896.git.me@ttaylorr.com>
On 6/2/2026 6:21 PM, Taylor Blau wrote:
> As a result, we can see significantly reduced pack sizes from p5311
> before this commit:

I mentioned this before, but the pack _sizes_ aren't changing in this example. We are computing them more quickly, though.

Show 26 quoted lines
>     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%

Since we are testing --path-walk on both sides, the change across this commit is that we are using the bitmaps for the "counting objects" phase and then potentially using the --path-walk algorithm to construct the packfile.

The fact that the packfile sizes are _identical_ is suspicious to me. I'd expect some amount of difference here due to the change in algorithm. It's possible that this could be explained by the repository shape not getting any benefit from --path-walk because there are no name-hash collisions to worry about.

The one thing that might be hinting towards _some_ difference is that the relative sizes are showing as both "+0.0%" and "-0.0%", so perhaps the exact sizes do have differences that are hidden behind the human-readable sizes: 4.1M -> 4.1M is +0.0% but 9.0M -> 9.0M is -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.

Ok, you have the correct interpretation here, just a lingering typo in the earlier sentence before the table.

Show 8 quoted lines
> 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.

And I wonder if the test setup creates a situation where we are always reusing deltas from the underlying packfile, so the --path-walk algorithm isn't doing anything to help with delta compression at this point and the difference in this patch is that we are replacing the object reachability calculation entirely with bitmaps.

I suppose what I'm really worried about is that I'm hoping to see some evidence from a large-scale test that demonstrates that the two algorithms are working in tandem in a non-trivial way. I haven't seen it yet, but I also don't have evidence that they _aren't_ working together.

Thanks, -Stolee

Previous: Taylor BlauNext: Taylor Blau
Message 13 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.