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

From: Taylor Blau <me@ttaylorr.com>
Date: Jun 29, 2021, 22:44 UTC
Message-ID: <YNuiM8TR5evSeNsN@nand.local>
In-Reply-To: <YNovuzAsaEb2uIaa@nand.local>

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