Re: [PATCH] bitmaps: don't recurse into trees already in the bitmap

From: Patrick Steinhardt <ps@pks.im>
Date: Jun 16, 2021, 12:31 UTC
Message-ID: <YMnvCI/jksyn2flD@tanuki>
In-Reply-To: <471cb9be-bb72-6a37-ede8-f9421d9d3ebe@gmail.com>

On Tue, Jun 15, 2021 at 10:17:04AM -0400, Derrick Stolee wrote:

> On 6/14/2021 8:05 AM, Jeff King wrote:

[snip]

Show 29 quoted lines

> > But here are numbers from some other real-world repositories (that are
> > not public). This one's tree is comparable in size to linux.git, but has
> > ~16k refs (and so less complete bitmap coverage):
> > 
> >   Test                         HEAD^               HEAD
> >   -------------------------------------------------------------------------
> >   5310.4: simulated clone      38.34(39.86+0.74)   33.95(35.53+0.76) -11.5%
> >   5310.5: simulated fetch      2.29(6.31+0.35)     2.20(5.97+0.41) -3.9%
> >   5310.7: rev-list (commits)   0.99(0.86+0.13)     0.96(0.85+0.11) -3.0%
> >   5310.8: rev-list (objects)   11.32(11.04+0.27)   6.59(6.37+0.21) -41.8%
> > 
> > And here's another with a very large tree (~340k entries), and a fairly
> > large number of refs (~10k):
> > 
> >   Test                         HEAD^               HEAD
> >   -------------------------------------------------------------------------
> >   5310.3: simulated clone      53.83(54.71+1.54)   39.77(40.76+1.50) -26.1%
> >   5310.4: simulated fetch      19.91(20.11+0.56)   19.79(19.98+0.67) -0.6%
> >   5310.6: rev-list (commits)   0.54(0.44+0.11)     0.51(0.43+0.07) -5.6%
> >   5310.7: rev-list (objects)   24.32(23.59+0.73)   9.85(9.49+0.36) -59.5%
> > 
> > This patch provides substantial improvements in these larger cases, and
> > have any drawbacks for smaller ones (the cost of the bitmap check is
> > quite small compared to an actual tree traversal).
> 
> These many-refs scenarios make sense as something that is difficult to
> verify using a single fork of an open-source project, but is common in
> many closed-source projects that do not use forking to reduce the ref
> count per repo.

Agreed. What I typically do to emulate this is to use some version of following command to create refs for "$n" commits.

    git log --all --format="tformat:create refs/commit/%h %H" |
        shuf | head -n "$n" | git update-ref --stdin

It's obviously not ideal given that resulting refs are distributed at random. But combined with a sufficiently large repo, it's still helped me at times to reproduce adverse performance at times.

Anyway, the patch does look good to me and sounds like it may help with some of the cases where I have observed adverse performance with bitmaps enabled in the past. Thanks!

Patrick