On 6/14/2021 8:05 AM, Jeff King wrote: > On Mon, Jun 14, 2021 at 03:27:04AM -0400, Jeff King wrote: ... > We can use the same optimization we do for commits here: when we are > about to open a tree, see if it's in the bitmap (either the one we are > building, or the "seen" bitmap which covers the UNINTERESTING side of > the bitmap when doing a set-difference). I was surprised that we were not already doing this. As Git can handle larger repos now than it could a few years ago, I expect this optimization to be immediately valuable, and critical in years to come. > 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. I was impressed by how little code was required for this change. LGTM. Thanks, -Stolee
