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:46 UTC
Message-ID
<ajVWYdTThVic+O+f@nand.local>
In-Reply-To
<ec45260a-1d4e-49d1-9aa8-9ec94ecd9b23@gmail.com>
On Fri, Jun 19, 2026 at 10:36:54AM -0400, Derrick Stolee wrote:
Show 28 quoted lines
> On 6/19/2026 10:16 AM, Taylor Blau wrote:
> > On Fri, Jun 12, 2026 at 09:03:41AM -0400, Derrick Stolee wrote:
> >> 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.
> >
> > Thanks for pointing this out. The paragraph following the perf output
> > below correctly explains the results ("We get the same size of output
> > pack, but [...]"), but this one is obviously wrong.
> >
> >> 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.
> >
> > I'm not sure I agree here. Because we are using bitmaps, we're relying
> > on pack-reuse to construct the output pack, not --path-walk. I mentioned
> > in git-pack-objects(1), but the combination of seeing "--path-walk" and
> > "--use-bitmap-index" together only means that we will use a path-walk
> > traversal as fallback if we can't get an answer by relying on bitmaps.
>
> I guess my thought was that we'd construct bitmaps when they are
> available, but how do we walk objects to get the objects for commits
> that are not represented by bitmaps?

Good question, and we use the existing bitmap traversal (or the boundary-based one, if enabled). In that case we really want something that is topological and not path-based, so we can terminate the walk as soon as we run into an existing set bit, or something on the negated side of the query.

Show 8 quoted lines
> But you make a good point: we don't need to do that for functional
> use: the bitmap code does an object walk to produce a bitmap, and it's
> all in a layer "below" the pack-objects code.
>
> So essentially, this _isn't_ a combined approach: it's "use bitmaps if
> we can, and fall back to --path-walk if we can't" which is changing
> from our previous behavior of "--path-walk means we don't try to use
> bitmaps".
Exactly!

Thanks, Taylor

Previous: Derrick StoleeNext: Derrick Stolee
Message 16 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.