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

From: "SZEDER Gábor" <szeder.dev@gmail.com>
To: Abhishek Kumar via GitGitGadget <gitgitgadget@gmail.com>
Cc: git@vger.kernel.org, "Derrick Stolee" <stolee@gmail.com>,
	"Jakub Narębski" <jnareb@gmail.com>,
	"Taylor Blau" <me@ttaylor.com>,
	"Abhishek Kumar" <abhishekkumar8222@gmail.com>
Subject: Re: [PATCH v5 01/11] commit-graph: fix regression when computing Bloom filters
Date: Tue, 5 Jan 2021 10:45:35 +0100	[thread overview]
Message-ID: <20210105094535.GN8396@szeder.dev> (raw)
In-Reply-To: <c4e817abf7dbcd6c99da404507ea940305c521b6.1609154168.git.gitgitgadget@gmail.com>

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.

> 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%

> 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
> 