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

Re: [PATCH 8/8] pack-bitmap: build pseudo-merge bitmaps after regular bitmaps

From
Jeff King <peff@peff.net>
Date
May 29, 2026, 08:33 UTC
Message-ID
<20260529083337.GC1106035@coredump.intra.peff.net>
In-Reply-To
<ahdE+Je5YK9JoE7B@nand.local>
On Wed, May 27, 2026 at 03:24:40PM -0400, Taylor Blau wrote:
Show 27 quoted lines
> Below are some numbers that give you a sense of how the runtime scales
> with the number of pseudo-merges. I'm relying exclusively on "stable"
> pseudo-merges here since they have more predictable bucketing behavior,
> though note that there isn't an exact way to dial in the number of these
> so-called "stable" pseudo-merge groups. We can only control their *size*
> (in terms of number of parents), so I ran the harness which produced the
> above code with powers of 10 between [10^3, 10^6].
> 
> Results are as follows:
> 
>     +------------+-------+----------+
>     | stableSize | count | time (s) |
>     +------------+-------+----------+
>     |    1000000 |     1 |   34.963 |
>     |     100000 |     3 |   36.954 |
>     |      10000 |    26 |  221.963 |
>     |       1000 |   252 | 2779.373 |
>     +------------+-------+----------+
> 
> Which scales roughly like O(x^1.165) (the best fit function I could find
> was t(n) = 25.18 + 4.386 * n^1.165, where 'n' is the number of
> pseudo-merges, and t(n) is the time it took to generate them).
> 
> So it does grow faster than linearly, but it's not too bad. The jump
> from 26 to 252 pseudo-merges is pretty significant, though, but having
> that many pseudo-merges is probably not something that we would want to
> do in practice.

OK, that matches my intuition. 1.165 is close enough that I can squint and call it linear. ;) I agree that probably you'd want to target a dozen or fewer pseudo-merges. In the long run we might be able to auto-tune this a bit, or at the very least document the tradeoffs and expectations. But think that can only come after getting some more real-world experience. For all we know the feature might not help at all in the real world, since any grouping strategy will be highly dependent on heuristics about how refs are updated, what queries look like, and so on.

Not that I'm not optimistic, just that I think it is too soon to try writing this stuff up.

-Peff
Previous: Taylor BlauNext: Jeff King
Message 27 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.