| Message ID | 6a6d88fa512ba344543f5f0df33d5a61e406f3db.1716318089.git.me@ttaylorr.com (mailing list archive) |
|---|---|
| State | Superseded |
| Headers | show |
| Series | pack-bitmap: pseudo-merge reachability bitmaps | expand |
On Tue, May 21, 2024 at 03:03:17PM -0400, Taylor Blau wrote: > Implement a straightforward performance test demonstrating the benefit > of pseudo-merge bitmaps by measuring how long it takes to count > reachable objects in a few different scenarios: > > - without bitmaps, to demonstrate a reasonable baseline > - with bitmaps, but without pseudo-merges > - with bitmaps and pseudo-merges > > Results from running this test on git.git are as follows: > > Test this tree > ----------------------------------------------------------------------------------- > 5333.2: git rev-list --count --all --objects (no bitmaps) 3.46(3.37+0.09) > 5333.3: git rev-list --count --all --objects (no pseudo-merges) 0.13(0.11+0.01) > 5333.4: git rev-list --count --all --objects (with pseudo-merges) 0.12(0.11+0.01) That's not a very exciting result. I have a feeling that your git.git is not a very interesting test case. We'd want a lot of refs, and ones that are old and have bushy history that is not included in the more recent branches. So something like a bunch of old unmerged pull request heads, for example. ;) Do you have more interesting numbers for something like that? -Peff
On Thu, May 23, 2024 at 06:54:22AM -0400, Jeff King wrote: > On Tue, May 21, 2024 at 03:03:17PM -0400, Taylor Blau wrote: > > > Implement a straightforward performance test demonstrating the benefit > > of pseudo-merge bitmaps by measuring how long it takes to count > > reachable objects in a few different scenarios: > > > > - without bitmaps, to demonstrate a reasonable baseline > > - with bitmaps, but without pseudo-merges > > - with bitmaps and pseudo-merges > > > > Results from running this test on git.git are as follows: > > > > Test this tree > > ----------------------------------------------------------------------------------- > > 5333.2: git rev-list --count --all --objects (no bitmaps) 3.46(3.37+0.09) > > 5333.3: git rev-list --count --all --objects (no pseudo-merges) 0.13(0.11+0.01) > > 5333.4: git rev-list --count --all --objects (with pseudo-merges) 0.12(0.11+0.01) > > That's not a very exciting result. I suspect some of it might have to do with: --- 8< --- diff --git a/t/perf/p5333-pseudo-merge-bitmaps.sh b/t/perf/p5333-pseudo-merge-bitmaps.sh index 4bec409d10..2e8b1d2635 100755 --- a/t/perf/p5333-pseudo-merge-bitmaps.sh +++ b/t/perf/p5333-pseudo-merge-bitmaps.sh @@ -20,12 +20,12 @@ test_perf 'git rev-list --count --all --objects (no bitmaps)' ' ' test_perf 'git rev-list --count --all --objects (no pseudo-merges)' ' - GIT_TEST_USE_PSEDUO_MERGES=0 \ + GIT_TEST_USE_PSEUDO_MERGES=0 \ git rev-list --objects --all --use-bitmap-index ' test_perf 'git rev-list --count --all --objects (with pseudo-merges)' ' - GIT_TEST_USE_PSEDUO_MERGES=1 \ + GIT_TEST_USE_PSEUDO_MERGES=1 \ git rev-list --objects --all --use-bitmap-index ' --- > 8--- Sure enough, that shows us a little gap between the "no pseudo-merges" and "with pseudo-merges" case: ``` Test this tree ----------------------------------------------------------------------------------- 5333.2: git rev-list --count --all --objects (no bitmaps) 3.54(3.45+0.08) 5333.3: git rev-list --count --all --objects (no pseudo-merges) 0.43(0.40+0.03) 5333.4: git rev-list --count --all --objects (with pseudo-merges) 0.12(0.11+0.01) ``` > I have a feeling that your git.git is not a very interesting test > case. We'd want a lot of refs, and ones that are old and have bushy > history that is not included in the more recent branches. So something > like a bunch of old unmerged pull request heads, for example. ;) Do > you have more interesting numbers for something like that? Indeed, here's one for a private repository which meets that criteria: ``` Test this tree --------------------------------------------------------------------------------------- 5333.1: git rev-list --count --all --objects (no bitmaps) 122.29(121.31+0.97) 5333.2: git rev-list --count --all --objects (no pseudo-merges) 21.88(21.30+0.58) 5333.3: git rev-list --count --all --objects (with pseudo-merges) 5.05(4.77+0.28) ``` Thanks, Taylor
On Thu, May 23, 2024 at 03:53:08PM -0400, Taylor Blau wrote: > - GIT_TEST_USE_PSEDUO_MERGES=0 \ > + GIT_TEST_USE_PSEUDO_MERGES=0 \ Whoops. > Sure enough, that shows us a little gap between the "no pseudo-merges" > and "with pseudo-merges" case: > > ``` > Test this tree > ----------------------------------------------------------------------------------- > 5333.2: git rev-list --count --all --objects (no bitmaps) 3.54(3.45+0.08) > 5333.3: git rev-list --count --all --objects (no pseudo-merges) 0.43(0.40+0.03) > 5333.4: git rev-list --count --all --objects (with pseudo-merges) 0.12(0.11+0.01) > ``` OK, that seems more like it. 300ms is nice, but there's just not that much improvement to make here. This one is much more exciting: > ``` > Test this tree > --------------------------------------------------------------------------------------- > 5333.1: git rev-list --count --all --objects (no bitmaps) 122.29(121.31+0.97) > 5333.2: git rev-list --count --all --objects (no pseudo-merges) 21.88(21.30+0.58) > 5333.3: git rev-list --count --all --objects (with pseudo-merges) 5.05(4.77+0.28) > ``` Very nice improvement. I wonder what we spend the final 5s on. Maybe just book-keeping to assemble all the tips (and maybe even parse tip commits? I can't remember if we ever optimized that out). Anyway, that's all out of scope for your series. Getting rid of the expensive traversal would let us focus on those final bits. ;) -Peff
diff --git a/t/perf/p5333-pseudo-merge-bitmaps.sh b/t/perf/p5333-pseudo-merge-bitmaps.sh new file mode 100755 index 00000000000..4bec409d10e --- /dev/null +++ b/t/perf/p5333-pseudo-merge-bitmaps.sh @@ -0,0 +1,32 @@ +#!/bin/sh + +test_description='pseudo-merge bitmaps' +. ./perf-lib.sh + +test_perf_large_repo + +test_expect_success 'setup' ' + git \ + -c bitmapPseudoMerge.all.pattern="refs/" \ + -c bitmapPseudoMerge.all.threshold=now \ + -c bitmapPseudoMerge.all.stableThreshold=never \ + -c bitmapPseudoMerge.all.maxMerges=64 \ + -c pack.writeBitmapLookupTable=true \ + repack -adb +' + +test_perf 'git rev-list --count --all --objects (no bitmaps)' ' + git rev-list --objects --all +' + +test_perf 'git rev-list --count --all --objects (no pseudo-merges)' ' + GIT_TEST_USE_PSEDUO_MERGES=0 \ + git rev-list --objects --all --use-bitmap-index +' + +test_perf 'git rev-list --count --all --objects (with pseudo-merges)' ' + GIT_TEST_USE_PSEDUO_MERGES=1 \ + git rev-list --objects --all --use-bitmap-index +' + +test_done
Implement a straightforward performance test demonstrating the benefit of pseudo-merge bitmaps by measuring how long it takes to count reachable objects in a few different scenarios: - without bitmaps, to demonstrate a reasonable baseline - with bitmaps, but without pseudo-merges - with bitmaps and pseudo-merges Results from running this test on git.git are as follows: Test this tree ----------------------------------------------------------------------------------- 5333.2: git rev-list --count --all --objects (no bitmaps) 3.46(3.37+0.09) 5333.3: git rev-list --count --all --objects (no pseudo-merges) 0.13(0.11+0.01) 5333.4: git rev-list --count --all --objects (with pseudo-merges) 0.12(0.11+0.01) Signed-off-by: Taylor Blau <me@ttaylorr.com> --- t/perf/p5333-pseudo-merge-bitmaps.sh | 32 ++++++++++++++++++++++++++++ 1 file changed, 32 insertions(+) create mode 100755 t/perf/p5333-pseudo-merge-bitmaps.sh