From 896f7e3199b7ef2863b3f47a7bc96068e25d5440 Mon Sep 17 00:00:00 2001 From: Jeff King Date: Mon, 5 Jul 2010 08:33:36 -0400 Subject: [PATCH] tag: speed up --contains calculation When we want to know if commit A contains commit B (or any one of a set of commits, B through Z), we generally calculate the merge bases and see if B is a merge base of A (or for a set, if any of the commits B through Z have that property). When we are going to check a series of commits A1 through An to see whether each contains B (e.g., because we are deciding which tags to show with "git tag --contains"), we do a series of merge base calculations. This can be very expensive, as we repeat a lot of traversal work. Instead, let's leverage the fact that we are going to use the same --contains list for each tag, and mark areas of the commit graph is definitely containing those commits, or definitely not containing those commits. Later tags can then stop traversing as soon as they see a previously calculated answer. This sped up "git tag --contains HEAD~200" in the linux-2.6 repository from: real 0m15.417s user 0m15.197s sys 0m0.220s to: real 0m5.329s user 0m5.144s sys 0m0.184s Signed-off-by: Jeff King Signed-off-by: Junio C Hamano --- builtin/tag.c | 2 +- commit.c | 42 ++++++++++++++++++++++++++++++++++++++++++ commit.h | 2 ++ 3 files changed, 45 insertions(+), 1 deletion(-) diff --git a/builtin/tag.c b/builtin/tag.c index d311491e4..c200e1e1a 100644 --- a/builtin/tag.c +++ b/builtin/tag.c @@ -49,7 +49,7 @@ static int show_reference(const char *refname, const unsigned char *sha1, commit = lookup_commit_reference_gently(sha1, 1); if (!commit) return 0; - if (!is_descendant_of(commit, filter->with_commit)) + if (!contains(commit, filter->with_commit)) return 0; } diff --git a/commit.c b/commit.c index e9b075096..20354c6f1 100644 --- a/commit.c +++ b/commit.c @@ -845,3 +845,45 @@ int commit_tree(const char *msg, unsigned char *tree, strbuf_release(&buffer); return result; } + +static int in_commit_list(const struct commit_list *want, struct commit *c) +{ + for (; want; want = want->next) + if (!hashcmp(want->item->object.sha1, c->object.sha1)) + return 1; + return 0; +} + +static int contains_recurse(struct commit *candidate, + const struct commit_list *want) +{ + struct commit_list *p; + + /* was it previously marked as containing a want commit? */ + if (candidate->object.flags & TMP_MARK) + return 1; + /* or marked as not possibly containing a want commit? */ + if (candidate->object.flags & UNINTERESTING) + return 0; + /* or are we it? */ + if (in_commit_list(want, candidate)) + return 1; + + if (parse_commit(candidate) < 0) + return 0; + + /* Otherwise recurse and mark ourselves for future traversals. */ + for (p = candidate->parents; p; p = p->next) { + if (contains_recurse(p->item, want)) { + candidate->object.flags |= TMP_MARK; + return 1; + } + } + candidate->object.flags |= UNINTERESTING; + return 0; +} + +int contains(struct commit *candidate, const struct commit_list *want) +{ + return contains_recurse(candidate, want); +} diff --git a/commit.h b/commit.h index eb2b8ac3c..1a7299ef8 100644 --- a/commit.h +++ b/commit.h @@ -153,6 +153,8 @@ extern struct commit_list *get_shallow_commits(struct object_array *heads, int is_descendant_of(struct commit *, struct commit_list *); int in_merge_bases(struct commit *, struct commit **, int); +int contains(struct commit *, const struct commit_list *); + extern int interactive_add(int argc, const char **argv, const char *prefix); extern int run_add_interactive(const char *revision, const char *patch_mode, const char **pathspec); -- 2.30.2