Re: [PATCH v3 6/9] commit: use generation numbers for in_merge_bases()
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()
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()
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