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