[PATCH v3 6/9] commit: use generation numbers for in_merge_bases()
- From
Derrick Stolee <dstolee@microsoft.com>
- Date
- Apr 17, 2018, 17:00 UTC
- Message-ID
- <20180417170001.138464-7-dstolee@microsoft.com>
- In-Reply-To
- <20180417170001.138464-1-dstolee@microsoft.com>
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 <peff@peff.net> Signed-off-by: Derrick Stolee <dstolee@microsoft.com> --- 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