From: Derrick Stolee Date: Fri, 12 Jun 2026 13:03:41 GMT Subject: Re: [PATCH v2 2/4] pack-objects: support reachability bitmaps with `--path-walk` Message-ID: <6e4a8764-3c56-42c8-a87e-40a94c6c34e9@gmail.com> In-Reply-To: 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. > 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. > 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