Re: [PATCH v3 6/9] commit: use generation numbers for in_merge_bases()

[Derrick Stolee]

On 4/18/2018 6:15 PM, Jakub Narebski wrote:

Derrick Stolee  writes:


The containment algorithm for 'git branch --contains' is different
from that for 'git tag --contains' in that it uses is_descendant_of()
instead of contains_tag_algo(). The expensive portion of the branch
algorithm is computing merge bases.

When a commit-graph file exists with generation numbers computed,
we can avoid this merge-base calculation when the target commit has
a larger generation number than the target commits.

You have "target" twice in above paragraph; one of those should probably
be something else.


Thanks. Second "target" should be "initial".


[...]

+
+   if (commit->generation > min_generation)
+   return 0;

Why not use "return ret;" instead of "return 0;", like the rest of the
code [cryptically] does, that is:

   +if (commit->generation > min_generation)
   +return ret;


Sure.

Thanks,
-Stolee

Re: [PATCH v3 6/9] commit: use generation numbers for in_merge_bases()

[Jakub Narebski]

Derrick Stolee  writes:

> The containment algorithm for 'git branch --contains' is different
> from that for 'git tag --contains' in that it uses is_descendant_of()
> instead of contains_tag_algo(). The expensive portion of the branch
> algorithm is computing merge bases.
>
> When a commit-graph file exists with generation numbers computed,
> we can avoid this merge-base calculation when the target commit has
> a larger generation number than the target commits.

You have "target" twice in above paragraph; one of those should probably
be something else.

>
> Performance tests were run on a copy of the Linux repository where
> HEAD is contained in v4.13 but no earlier tag. Also, all tags were
> copied to branches and 'git branch --contains' was tested:
>
> Before: 60.0s
> After:   0.4s
> Rel %: -99.3%

Nice...

>
> Reported-by: Jeff King 
> Signed-off-by: Derrick Stolee 
> ---
>  commit.c | 9 -
>  1 file changed, 8 insertions(+), 1 deletion(-)

...especially for so small changes.

>
> diff --git a/commit.c b/commit.c
> index a44899c733..bceb79c419 100644
> --- a/commit.c
> +++ b/commit.c
> @@ -1053,12 +1053,19 @@ int in_merge_bases_many(struct commit *commit, int 
> nr_reference, struct commit *
>  {
>   struct commit_list *bases;
>   int ret = 0, i;
> + uint32_t min_generation = GENERATION_NUMBER_INFINITY;
>  
>   if (parse_commit(commit))
>   return ret;
> - for (i = 0; i < nr_reference; i++)
> + for (i = 0; i < nr_reference; i++) {
>   if (parse_commit(reference[i]))
>   return ret;
> + if (min_generation > reference[i]->generation)
> + min_generation = reference[i]->generation;
> + }
> +
> + if (commit->generation > min_generation)
> + return 0;

Why not use "return ret;" instead of "return 0;", like the rest of the
code [cryptically] does, that is:

  + if (commit->generation > min_generation)
  + return ret;

>  
>   bases = paint_down_to_common(commit, nr_reference, reference);
>   if (commit->object.flags & PARENT2)

Otherwise, it looks good to me.

[PATCH v3 6/9] commit: use generation numbers for in_merge_bases()

[Derrick Stolee]

The containment algorithm for 'git branch --contains' is different
from that for 'git tag --contains' in that it uses is_descendant_of()
instead of contains_tag_algo(). The expensive portion of the branch
algorithm is computing merge bases.

When a commit-graph file exists with generation numbers computed,
we can avoid this merge-base calculation when the target commit has
a larger generation number than the target commits.

Performance tests were run on a copy of the Linux repository where
HEAD is contained in v4.13 but no earlier tag. Also, all tags were
copied to branches and 'git branch --contains' was tested:

Before: 60.0s
After:   0.4s
Rel %: -99.3%

Reported-by: Jeff King 
Signed-off-by: Derrick Stolee 
---
 commit.c | 9 -
 1 file changed, 8 insertions(+), 1 deletion(-)

diff --git a/commit.c b/commit.c
index a44899c733..bceb79c419 100644
--- a/commit.c
+++ b/commit.c
@@ -1053,12 +1053,19 @@ int in_merge_bases_many(struct commit *commit, int 
nr_reference, struct commit *
 {
struct commit_list *bases;
int ret = 0, i;
+   uint32_t min_generation = GENERATION_NUMBER_INFINITY;
 
if (parse_commit(commit))
return ret;
-   for (i = 0; i < nr_reference; i++)
+   for (i = 0; i < nr_reference; i++) {
if (parse_commit(reference[i]))
return ret;
+   if (min_generation > reference[i]->generation)
+   min_generation = reference[i]->generation;
+   }
+
+   if (commit->generation > min_generation)
+   return 0;
 
bases = paint_down_to_common(commit, nr_reference, reference);
if (commit->object.flags & PARENT2)
-- 
2.17.0.39.g685157f7fb