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

Re: [PATCH 6/8] pack-bitmap: sort bitmaps before XORing

From
Jeff King <peff@peff.net>
Date
May 29, 2026, 08:26 UTC
Message-ID
<20260529082622.GB1106035@coredump.intra.peff.net>
In-Reply-To
<ahciIDuESxNa9Fzn@nand.local>
On Wed, May 27, 2026 at 12:56:00PM -0400, Taylor Blau wrote:
Show 9 quoted lines
> > If you have some spare CPU cycles to burn, I would be interested in a
> > comparison of the bitmap size of your test repo using v2.30.0, v2.31.1,
> > and this patch.
> 
> I started running this experiment, but I don't think I actually have
> enough CPU cycles to let it finish ;-). Pre-v2.31 bitmap generation is
> *really* slow[^1], and after multiple hours (forcing the same selection
> of bitmaps by back-porting and adjusting 'test-tool bitmap') I couldn't
> seem to make any meaningful progress.
Oof. I forgot just how slow it could be. Thanks for trying.
> I'm sure that you could get some plausible numbers out of benchmarking
> this on a smaller repository. In case you're interested, here's the
> patch I wrote on top of v2.30.0:

I tried it myself on linux.git, which is the biggest repo I usually have on hand. But it seemed to generate the same size back then, and now, and after your xor-sorting patch. I'm not sure what's different between that and your super-big test case. Maybe just the number of bitmaps? Maybe graph structure causing weird order of selection?

I grabbed chromium.git (63GB!) and tried that, too. Its bitmap size shrinks a tiny bit with this patch (143MB to 140MB). So some improvement, but not enough of an effect for me to slog through a v2.30 bitmap build just to see if things changed back then.

Regardless of whether the issue was introduced there, or was always lurking, I think the sort order introduced by this patch is the right thing to do.

Show 9 quoted lines
> > Certainly good numbers. The obvious follow-up question is: how does the
> > reading side fare? I'd expect it to be a little better, if only because
> > there are fewer bytes to consider when XOR-ing. But if there's some
> > hidden assumption we're missing, then it could get wildly worse. It
> > would be good to confirm that that didn't happen. ;)
> 
> It doesn't make a huge difference. Prior to this patch, the timings on
> my test repository for 'git rev-list --count --all --objects
> --use-bitmap-index' go from:

OK, good. I wasn't expecting great things, but just wanted to double check that bad things did not appear.

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