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

[Jeff King <peff@peff.net>]

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