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

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

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

[snip]

quoted

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