diff mbox series

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

Message ID c4e817abf7dbcd6c99da404507ea940305c521b6.1609154168.git.gitgitgadget@gmail.com (mailing list archive)
State New, archived
Headers show
Series Implement Corrected Commit Date | expand

Commit Message

Abhishek Kumar Dec. 28, 2020, 11:15 a.m. UTC 
From: Abhishek Kumar <abhishekkumar8222@gmail.com>

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.

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.

Not all hope is lost, though: 'commit_graph_generation()' falls back to
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. Applying this patch (compared
with v2.29.1) speeds up computing Bloom filters by around ~4
seconds.

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

Comments

Derrick Stolee Dec. 30, 2020, 1:35 a.m. UTC | #1 
On 12/28/2020 6:15 AM, Abhishek Kumar via GitGitGadget wrote:
> From: Abhishek Kumar <abhishekkumar8222@gmail.com>
> 
> Before computing Bloom fitlers, the commit-graph machinery uses

s/fitlers/filters/

> 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.
> 
> 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.
> 
> Not all hope is lost, though: 'commit_graph_generation()' falls back to
> comparing commits by their date when they have equal generation number,
> and so since c49c82aa4c is purely a date comparision function. This

s/comparision/comparison/

> heuristic is good enough that we don't seem to loose appreciable
> performance while computing Bloom filters. Applying this patch (compared
> with v2.29.1) speeds up computing Bloom filters by around ~4
> seconds.

Using "~4 seconds" here is odd since there is no baseline. Which
repository did you use?

Previous discussion used relative terms. Something like "speeds up by
a factor of 1.25" or something might be interesting.

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

This introduces some timing restrictions to the ability for this
comparison function. It would be dangerous if someone extracted
the method for another purpose. A comment above these lines could
warn future developers from making that mistake, but they would
probably use the comparison functions in commit.c instead.

> 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;
>
SZEDER Gábor Jan. 5, 2021, 9:45 a.m. UTC | #2 
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
>
SZEDER Gábor Jan. 5, 2021, 9:47 a.m. UTC | #3 
On Tue, Jan 05, 2021 at 10:45:35AM +0100, SZEDER Gábor wrote:
> > 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:

Gaah, scratch this paragraph; I first misunderstood what you wrote in
the paragraph below, but then forgot to remove it.

> > 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.
Abhishek Kumar Jan. 8, 2021, 5:45 a.m. UTC | #4 
On Tue, Dec 29, 2020 at 08:35:56PM -0500, Derrick Stolee wrote:
> On 12/28/2020 6:15 AM, Abhishek Kumar via GitGitGadget wrote:
> > From: Abhishek Kumar <abhishekkumar8222@gmail.com>
> > 
> > Before computing Bloom fitlers, the commit-graph machinery uses
> 
> s/fitlers/filters/
> 
> > 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.
> > 
> > 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.
> > 
> > Not all hope is lost, though: 'commit_graph_generation()' falls back to
> > comparing commits by their date when they have equal generation number,
> > and so since c49c82aa4c is purely a date comparision function. This
> 
> s/comparision/comparison/
> 
> > heuristic is good enough that we don't seem to loose appreciable
> > performance while computing Bloom filters. Applying this patch (compared
> > with v2.29.1) speeds up computing Bloom filters by around ~4
> > seconds.
> 
> Using "~4 seconds" here is odd since there is no baseline. Which
> repository did you use?
> 

I used the linux repository, will mention that.

> Previous discussion used relative terms. Something like "speeds up by
> a factor of 1.25" or something might be interesting.
> 

As SZEDER Gábor found, the improvements are rather minor - ranging from
0.40% to 5.19% [1]. I want to make sure this is the correct way to word
in the commit message:

Applying this patch (compared with v2.30.0) speeds up computing Bloom
filters by factors ranging from 0.40% to 5.19% on various
repositories. 

https://lore.kernel.org/git/20210105094535.GN8396@szeder.dev/

> > 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.
> 
> This introduces some timing restrictions to the ability for this
> comparison function. It would be dangerous if someone extracted
> the method for another purpose. A comment above these lines could
> warn future developers from making that mistake, but they would
> probably use the comparison functions in commit.c instead.
> 

Sure, will add a comment above.

> > 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;
> > 
>
Abhishek Kumar Jan. 8, 2021, 5:51 a.m. UTC | #5 
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
diff mbox series

Patch

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;