From: Jeff King Date: Fri, 29 May 2026 08:26:22 GMT Subject: Re: [PATCH 6/8] pack-bitmap: sort bitmaps before XORing Message-ID: <20260529082622.GB1106035@coredump.intra.peff.net> In-Reply-To: On Wed, May 27, 2026 at 12:56:00PM -0400, Taylor Blau wrote: > > 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. > > 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