From: Ævar Arnfjörð Bjarmason <avarab@gmail.com>
To: git@vger.kernel.org
Cc: Junio C Hamano <gitster@pobox.com>, Jeff King <peff@peff.net>,
Ævar Arnfjörð Bjarmason <avarab@gmail.com>
Subject: [PATCH 1/4] tag: speed up --contains calculation
Date: Sat, 11 Jun 2011 19:04:08 +0000
Message-ID: <1307819051-25748-2-git-send-email-avarab@gmail.com> (raw)
In-Reply-To: <1307819051-25748-1-git-send-email-avarab@gmail.com>
From: Jeff King <peff@peff.net>
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 <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
Signed-off-by: Ævar Arnfjörð Bjarmason <avarab@gmail.com>
---
builtin/tag.c | 46 +++++++++++++++++++++++++++++++++++++++++++++-
1 files changed, 45 insertions(+), 1 deletions(-)
diff --git a/builtin/tag.c b/builtin/tag.c
index ec926fc..575a03c 100644
--- a/builtin/tag.c
+++ b/builtin/tag.c
@@ -12,6 +12,8 @@
#include "tag.h"
#include "run-command.h"
#include "parse-options.h"
+#include "diff.h"
+#include "revision.h"
static const char * const git_tag_usage[] = {
"git tag [-a|-s|-u <key-id>] [-f] [-m <msg>|-F <file>] <tagname> [<head>]",
@@ -29,6 +31,48 @@ struct tag_filter {
struct commit_list *with_commit;
};
+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);
+}
+
static int show_reference(const char *refname, const unsigned char *sha1,
int flag, void *cb_data)
{
@@ -47,7 +91,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;
}
--
1.7.5.3
next prev parent reply index
Thread overview: 28+ messages / expand[flat|nested] mbox.gz Atom feed top
2011-06-11 19:04 [PATCH 0/4] Speed up git tag --contains Ævar Arnfjörð Bjarmason
2011-06-11 19:04 ` Ævar Arnfjörð Bjarmason [this message]
2011-06-11 19:04 ` [PATCH 2/4] limit "contains" traversals based on commit timestamp Ævar Arnfjörð Bjarmason
2011-06-11 19:04 ` [PATCH 3/4] default core.clockskew variable to one day Ævar Arnfjörð Bjarmason
2011-06-11 19:04 ` [PATCH 4/4] Why is "git tag --contains" so slow? Ævar Arnfjörð Bjarmason
2011-07-06 6:40 ` [PATCH 0/4] Speed up git tag --contains Jeff King
2011-07-06 6:54 ` Jeff King
2011-07-06 19:06 ` Clemens Buchacher
2011-07-06 6:56 ` Jonathan Nieder
2011-07-06 7:03 ` Jeff King
2011-07-06 14:26 ` generation numbers (was: [PATCH 0/4] Speed up git tag --contains) Jakub Narebski
2011-07-06 15:01 ` Ted Ts'o
2011-07-06 18:12 ` Jeff King
2011-07-06 18:46 ` Jakub Narebski
2011-07-07 18:59 ` Jeff King
2011-07-07 19:34 ` generation numbers Junio C Hamano
2011-07-07 20:31 ` Jakub Narebski
2011-07-07 20:52 ` A Large Angry SCM
2011-07-08 0:29 ` Junio C Hamano
2011-07-08 22:57 ` Jeff King
2011-07-06 23:22 ` Junio C Hamano
2011-07-07 19:08 ` Jeff King
2011-07-07 20:10 ` Jakub Narebski
2018-01-12 18:56 ` [PATCH 0/4] Speed up git tag --contains csilvers
2018-03-03 5:15 ` Jeff King
2018-03-08 23:05 ` csilvers
2018-03-12 13:45 ` Derrick Stolee
2018-03-12 23:59 ` Jeff King
Reply instructions:
You may reply publically to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
List information: http://vger.kernel.org/majordomo-info.html
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=1307819051-25748-2-git-send-email-avarab@gmail.com \
--to=avarab@gmail.com \
--cc=git@vger.kernel.org \
--cc=gitster@pobox.com \
--cc=peff@peff.net \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
git@vger.kernel.org mailing list mirror (one of many)
Archives are clonable:
git clone --mirror https://public-inbox.org/git
git clone --mirror http://ou63pmih66umazou.onion/git
git clone --mirror http://czquwvybam4bgbro.onion/git
git clone --mirror http://hjrcffqmbrq6wope.onion/git
Newsgroups are available over NNTP:
nntp://news.public-inbox.org/inbox.comp.version-control.git
nntp://ou63pmih66umazou.onion/inbox.comp.version-control.git
nntp://czquwvybam4bgbro.onion/inbox.comp.version-control.git
nntp://hjrcffqmbrq6wope.onion/inbox.comp.version-control.git
nntp://news.gmane.org/gmane.comp.version-control.git
note: .onion URLs require Tor: https://www.torproject.org/
or Tor2web: https://www.tor2web.org/
AGPL code for this site: git clone https://public-inbox.org/ public-inbox