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

Re: [PATCH 3/8] pack-bitmap: reuse stored selected bitmaps

From
Jeff King <peff@peff.net>
Date
May 29, 2026, 06:00 UTC
Message-ID
<20260529060042.GA1106035@coredump.intra.peff.net>
In-Reply-To
<ahcCX+xAKFOL8HcW@nand.local>
On Wed, May 27, 2026 at 10:40:31AM -0400, Taylor Blau wrote:
Show 17 quoted lines
> > > Teach `fill_bitmap_commit()` to notice that case. For non-root commits in
> > > the walk, look for a stored selected bitmap and OR it into the bitmap
> > > being built. If one exists, skip the commit, its tree, and its parents.
> >
> > I feel like this _shouldn't_ be necessary, because the idea of the
> > current writing code is to go from the roots up, following inverted
> > parent pointers, and passing the bitmap up as we go. So whenever we
> > visit a commit we should in theory have all of the ancestor's bits set
> > in that bitmap. But I remember that the simple-and-stupid approach ended
> > up being too memory hungry, so we pick some focal points in the graph
> > and then fill them independently.
> 
> It's sharing within the non-first parent history that is killing us
> here. I think what you said is true in a completely linear repository
> with no merges. But since we only pass commit masks from commits to
> their first parents, we don't reuse any already-generated bitmaps for
> common points in history not shared between commits' first parents.

Ah, that makes sense. I had forgotten exactly how the maximal-commit selection worked, and what we compromised versus the original naive "build from the bottom up" strategy.

Show 6 quoted lines
> Yeah, these were for my own curiosity as much as anything. I had written
> them as a temporary measure in order to write the "[...] there are 1,261
> commits selected for bitmap coverage, and 1,382 maximal commits induced
> [...]" portion of the commit message above.
> 
> Once I had written it, I found the result useful enough to keep around.

Makes sense. It might help us (or even some very clueful user) debug or fine-tune parameters down the road.

-Peff
Previous: Taylor BlauNext: Taylor Blau
Message 11 of 38 in “pack-bitmap-write: speed up bitmap generation”
  1. 0/8 pack-bitmap-write: speed up bitmap generationTaylor Blau, May 19, 2026
  2. 1/8 pack-bitmap: pass object position to `fill_bitmap_tree()`Taylor Blau, May 19, 2026
  3. Jeff KingMay 27, 2026
  4. Taylor BlauMay 27, 2026
  5. 2/8 pack-bitmap: check subtree bits before recursingTaylor Blau, May 19, 2026
  6. Jeff KingMay 27, 2026
  7. Taylor BlauMay 27, 2026
  8. 3/8 pack-bitmap: reuse stored selected bitmapsTaylor Blau, May 19, 2026
  9. Jeff KingMay 27, 2026
  10. Taylor BlauMay 27, 2026
  11. Jeff KingMay 29, 2026
  12. 4/8 pack-bitmap: consolidate `find_object_pos()` success pathTaylor Blau, May 19, 2026
  13. SZEDER GáborMay 20, 2026
  14. Taylor BlauMay 20, 2026
  15. Jeff KingMay 27, 2026
  16. 5/8 pack-bitmap: cache object positions during fillTaylor Blau, May 19, 2026
  17. Jeff KingMay 27, 2026
  18. Taylor BlauMay 27, 2026
  19. 6/8 pack-bitmap: sort bitmaps before XORingTaylor Blau, May 19, 2026
  20. Jeff KingMay 27, 2026
  21. Taylor BlauMay 27, 2026
  22. Jeff KingMay 29, 2026
  23. 7/8 pack-bitmap: remember pseudo-merge parentsTaylor Blau, May 19, 2026
  24. 8/8 pack-bitmap: build pseudo-merge bitmaps after regular bitmapsTaylor Blau, May 19, 2026
  25. Jeff KingMay 27, 2026
  26. Taylor BlauMay 27, 2026
  27. Jeff KingMay 29, 2026
  28. Jeff KingMay 27, 2026
  29. 0/8 pack-bitmap-write: speed up bitmap generationTaylor Blau, May 27, 2026
  30. 1/8 pack-bitmap: pass object position to `fill_bitmap_tree()`Taylor Blau, May 27, 2026
  31. 2/8 pack-bitmap: check subtree bits before recursingTaylor Blau, May 27, 2026
  32. 3/8 pack-bitmap: reuse stored selected bitmapsTaylor Blau, May 27, 2026
  33. 4/8 pack-bitmap: consolidate `find_object_pos()` success pathTaylor Blau, May 27, 2026
  34. 5/8 pack-bitmap: cache object positions during fillTaylor Blau, May 27, 2026
  35. 6/8 pack-bitmap: sort bitmaps before XORingTaylor Blau, May 27, 2026
  36. 7/8 pack-bitmap: remember pseudo-merge parentsTaylor Blau, May 27, 2026
  37. 8/8 pack-bitmap: build pseudo-merge bitmaps after regular bitmapsTaylor Blau, May 27, 2026
  38. Jeff KingMay 29, 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.