From: Jeff King Date: Fri, 29 May 2026 08:33:37 GMT Subject: Re: [PATCH 8/8] pack-bitmap: build pseudo-merge bitmaps after regular bitmaps Message-ID: <20260529083337.GC1106035@coredump.intra.peff.net> In-Reply-To: On Wed, May 27, 2026 at 03:24:40PM -0400, Taylor Blau wrote: > 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