Re: [PATCH v2 3/3] connected: implement connectivity check using bitmaps

[Taylor Blau <me@ttaylorr.com>]

On Mon, Jun 28, 2021 at 04:23:23PM -0400, Taylor Blau wrote:
> I'll try this out myself and see if it's worth it. (As an aside, I'll be
> offline next week, so it may take me a little while to post something to
> the list).

I gave implementing this a shot and it seems to have produced some good
improvements, although there are definitely some areas where it does
better than others.

Here are some results running on linux.git with a cold cache, counting
objects for commit 2ab38c17aa, which I picked deliberately since I know
it has a bitmap:

    $ hyperfine \
      'GIT_READ_COMMIT_TABLE=0 git.compile rev-list --count --objects --use-bitmap-index 2ab38c17aac10bf55ab3efde4c4db3893d8691d2' \
      'GIT_READ_COMMIT_TABLE=1 git.compile rev-list --count --objects --use-bitmap-index 2ab38c17aac10bf55ab3efde4c4db3893d8691d2' \
      --prepare='sync; echo 3 | sudo tee /proc/sys/vm/drop_caches'

		Benchmark #1: GIT_READ_COMMIT_TABLE=0 git.compile rev-list --count --objects --use-bitmap-index 2ab38c17aac10bf55ab3efde4c4db3893d8691d2
			Time (mean ± σ):     141.1 ms ±   2.5 ms    [User: 13.0 ms, System: 64.3 ms]
			Range (min … max):   136.2 ms … 143.4 ms    10 runs

		Benchmark #2: GIT_READ_COMMIT_TABLE=1 git.compile rev-list --count --objects --use-bitmap-index 2ab38c17aac10bf55ab3efde4c4db3893d8691d2
			Time (mean ± σ):      28.7 ms ±   3.2 ms    [User: 6.5 ms, System: 10.0 ms]
			Range (min … max):    22.0 ms …  31.0 ms    21 runs

		Summary
			'GIT_READ_COMMIT_TABLE=1 git.compile rev-list --count --objects --use-bitmap-index 2ab38c17aac10bf55ab3efde4c4db3893d8691d2' ran
				4.91 ± 0.55 times faster than 'GIT_READ_COMMIT_TABLE=0 git.compile rev-list --count --objects --use-bitmap-index 2ab38c17aac10bf55ab3efde4c4db3893d8691d2'

That's sort of a best-case scenario, because we're not doing any
traversal between the bitmapped commits and the traversal tips. But even
if we do have some traversal, the results are still pretty good.
Swapping out 2ab38c17aa for `--branches` yields a 5.02x improvement from
141.0ms down to 28.1ms.

Adding in `--tags` basically negates any improvement (having the commit
table extension eeks out a 1.03x improvement from 645.7ms down to
626.0ms. `perf record` shows that 30% of time is spent outside of the
bitmap code.

If you want to give this a try yourself, I highly recommend generating
your bitmap while packing with `-c pack.writeReverseIndex`. Building a
reverse index on-the-fly also seems to negate any performance
improvements here, so having an on-disk reverse index is more or less a
prerequisite to testing this out.

Extremely gross and inscrutable code can be found on the
'tb/bitmap-commit-table' branch of my fork [1].

Thanks,
Taylor

[1]: https://github.com/git/git/compare/master...ttaylorr:tb/bitmap-commit-table