On 4/4/2018 11:45 AM, Derrick Stolee wrote:
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@xxxxxxxx>
Signed-off-by: Derrick Stolee <dstolee@xxxxxxxxxxxxx>
---
commit.c | 9 ++++++++-
1 file changed, 8 insertions(+), 1 deletion(-)
diff --git a/commit.c b/commit.c
index 858f4fdbc9..2566cba79f 100644
--- a/commit.c
+++ b/commit.c
@@ -1059,12 +1059,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_UNDEF;
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)
This patch may suffice to speed up 'git branch --contains' instead of
needing to always use the 'git tag --contains' algorithm as considered
in [1].
Thanks,
-Stolee
[1]
https://public-inbox.org/git/20180303051516.GE27689@xxxxxxxxxxxxxxxxxxxxx/
Re: [PATCH 0/4] Speed up git tag --contains
