Re: [PATCH v5 01/11] commit-graph: fix regression when computing Bloom filters

[Abhishek Kumar <abhishekkumar8222@gmail.com>]

On Tue, Jan 05, 2021 at 10:45:35AM +0100, SZEDER Gábor wrote:
> On Mon, Dec 28, 2020 at 11:15:58AM +0000, Abhishek Kumar via GitGitGadget wrote:
> > Before computing Bloom fitlers, the commit-graph machinery uses
> > commit_gen_cmp to sort commits by generation order for improved diff
> > performance. 3d11275505 (commit-graph: examine commits by generation
> > number, 2020-03-30) claims that this sort can reduce the time spent to
> > compute Bloom filters by nearly half.
> 
> That's true, though there are repositories where it has basically no
> effect.  Alas we can't directly test it, because in 3d11275505 there
> is no '--changed-paths' option yet... one has to revert 3d11275505 on
> top of d38e07b8c4 (commit-graph: add --changed-paths option to write
> subcommand, 2020-04-06) to make any runtime comparisons ('git
> commit-graph write --reachable --changed-paths', best of five):
> 
>                    Sorting by
>                pack    | generation
>              position  |
>     -------------------+------------
>     gcc      114.821s  |    38.963s 
>     git        8.896s  |     5.620s
>     linux    209.984s  |   104.900s
>     webkit    35.193s  |    35.482s
> 
> Note the almost 3x speedup in the gcc repository, and the basically
> negligible slowdown in the webkit repo.
> 
> > But since c49c82aa4c (commit: move members graph_pos, generation to a
> > slab, 2020-06-17), this optimization is broken, since asking for a
> > 'commit_graph_generation()' directly returns GENERATION_NUMBER_INFINITY
> > while writing.
> 
> I wouldn't say that c49c82aa4c broke this optimisation, because:
> 
> did not break that optimization.  Though, sadly, it's not
> mentioned in 3d11275505's commit message, when commit_gen_cmp()
> compares two commits with identical generation numbers, then it
> doesn't leave them unsorted, but falls back to use their committer
> date as a tie-braker.  This means that after c49c82aa4c the commits
> are sorted by committer date, which appears to be so good a heuristic
> for Bloom filter computation that there is barely any slowdown
> compared to sorting by generation numbers:
> 
> > Not all hope is lost, though: 'commit_graph_generation()' falls back to
> 
> You mean commit_gen_cmp() here.
> 

Yes, fixed.

> > comparing commits by their date when they have equal generation number,
> > and so since c49c82aa4c is purely a date comparision function. This
> > heuristic is good enough that we don't seem to loose appreciable
> > performance while computing Bloom filters.
> 
> Indeed, c49c82aa4c barely caused any runtime difference in the
> repositories I usually use to test modified path Bloom filter
> performance:
> 
>                  c49c82aa4c^  c49c82aa4c
>   ---------------------------------------------
>   android-base     43.057s     43.091s   0.07%
>   cmssw            21.781s     21.856s   0.34%
>   cpython           9.626s      9.724s   1.01%
>   elasticsearch    18.049s     18.224s   0.96%
>   gcc              40.312s     40.255s  -0.14%
>   gecko-dev       104.515s    104.740s   0.21%
>   git               5.559s      5.570s   0.19%
>   glibc             4.455s      4.468s   0.29%
>   go                4.009s      4.016s   0.17%
>   homebrew-cask    30.759s     30.523s  -0.76%
>   homebrew-core    57.122s     56.553s  -0.99%
>   jdk              18.297s     18.364s   0.36%
>   linux           104.499s    105.302s   0.76%
>   llvm-project     34.074s     34.446s   1.09%
>   rails             6.472s      6.486s   0.21%
>   rust             14.943s     14.947s   0.02%
>   tensorflow       13.362s     13.477s   0.86%
>   webkit           34.583s     34.601s   0.05%
> 
> > Applying this patch (compared
> > with v2.29.1) speeds up computing Bloom filters by around ~4
> > seconds.
> 
> Without a baseline and knowing which repo, this "~4 seconds" is
> meaningless.
> 
> Here are my results comparing this fix to v2.30.0, best of five:
> 
>                               v2.30.0 +
>                    v2.30.0    this fix
>   ---------------------------------------------
>   android-base     42.786s     42.933s   0.34%
>   cmssw            20.229s     20.160s  -0.34%
>   cpython           9.616s      9.647s   0.32%
>   elasticsearch    16.859s     16.936s   0.45%
>   gcc              38.909s     36.889s  -5.19%
>   gecko-dev        99.417s     98.558s  -0.86%
>   git               5.620s      5.509s  -1.97%
>   glibc             4.307s      4.301s  -0.13%
>   go                3.971s      3.938s  -0.83%
>   homebrew-cask    31.262s     30.283s  -3.13%
>   homebrew-core    57.842s     55.663s  -3.76%
>   jdk              12.557s     12.251s  -2.43%
>   linux            94.335s     94.760s   0.45%
>   llvm-project     34.432s     33.988s  -1.28%
>   rails             6.481s      6.454s  -0.41%
>   rust             14.772s     14.601s  -1.15%
>   tensorflow       11.759s     11.711s  -0.40%
>   webkit           33.917s     33.759s  -0.46%
>

Thank you for the detailed performance benchmarking.

> 
> > So, avoid the useless 'commit_graph_generation()' while writing by
> > instead accessing the slab directly. This returns the newly-computed
> > generation numbers, and allows us to avoid the heuristic by directly
> > comparing generation numbers.
> > 
> > Signed-off-by: Abhishek Kumar <abhishekkumar8222@gmail.com>
> > ---
> >  commit-graph.c | 4 ++--
> >  1 file changed, 2 insertions(+), 2 deletions(-)
> > 
> > diff --git a/commit-graph.c b/commit-graph.c
> > index 06f8dc1d896..caf823295f4 100644
> > --- a/commit-graph.c
> > +++ b/commit-graph.c
> > @@ -144,8 +144,8 @@ static int commit_gen_cmp(const void *va, const void *vb)
> >  	const struct commit *a = *(const struct commit **)va;
> >  	const struct commit *b = *(const struct commit **)vb;
> >  
> > -	uint32_t generation_a = commit_graph_generation(a);
> > -	uint32_t generation_b = commit_graph_generation(b);
> > +	uint32_t generation_a = commit_graph_data_at(a)->generation;
> > +	uint32_t generation_b = commit_graph_data_at(b)->generation;
> >  	/* lower generation commits first */
> >  	if (generation_a < generation_b)
> >  		return -1;
> > -- 
> > gitgitgadget
> > 

Thanks
- Abhishek