Re: What's cooking in git.git (topics)

[Junio C Hamano <junkio@cox.net>]

"Shawn O. Pearce" <spearce@spearce.org> writes:

> Only on tags which are considered possible matches.  What we do
> now is we walk back along the commit history until we find a commit
> which has a tag pointing at it.  As soon as we find that commit we
> enqueue its corresponding tag into a list and completely ignore its
> parents, aborting listing any further back.  So we really only pay
> the bare minimum price here.

This actually is QUITE bad.

With the tip of linux-2.6 repository, v1.4.4 series takes 0.03s
while v1.5.0-rc1 takes about 3.6s.  That is 100x fold, not just
4x.

It turns out that to describe 0404f87f (tip of linux-2.6) the
new one picks up 61 tags in the posible-tag loop.

Since this loop uses the usual date-order, we can limit the
number of candidate tags without losing too much precision.
When limiting the candidates to only 6 (attached patch), the
time drops to 0.25s.

--- 
diff --git a/builtin-describe.c b/builtin-describe.c
index a8c98ce..a1ecec2 100644
--- a/builtin-describe.c
+++ b/builtin-describe.c
@@ -12,6 +12,7 @@ static const char describe_usage[] =
 
 static int all;	/* Default to annotated tags only */
 static int tags;	/* But allow any tags if --tags is specified */
+static int debug;
 
 static int abbrev = DEFAULT_ABBREV;
 
@@ -113,6 +114,7 @@ static void describe(const char *arg, int last_one)
 	static int initialized = 0;
 	struct commit_name *n;
 	struct possible_tag *all_matches, *min_match, *cur_match;
+	int cnt;
 
 	if (get_sha1(arg, sha1))
 		die("Not a valid object name %s", arg);
@@ -136,6 +138,7 @@ static void describe(const char *arg, int last_one)
 	all_matches = NULL;
 	cur_match = NULL;
 	commit_list_insert(cmit, &list);
+	cnt = 6;
 	while (list) {
 		struct commit *c = pop_commit(&list);
 		n = match(c);
@@ -148,6 +151,8 @@ static void describe(const char *arg, int last_one)
 			else
 				all_matches = p;
 			cur_match = p;
+			if (--cnt <= 0)
+				break;
 		} else {
 			struct commit_list *parents = c->parents;
 			while (parents) {
@@ -161,6 +166,18 @@ static void describe(const char *arg, int last_one)
 			}
 		}
 	}
+	if (list)
+		free_commit_list(list);
+
+	if (debug) {
+		int cnt = 0;
+		for (cur_match = all_matches;
+		     cur_match;
+		     cur_match = cur_match->next)
+			cnt++;
+		fprintf(stderr, "%d candidates for %s\n", cnt,
+			sha1_to_hex(cmit->object.sha1));
+	}
 
 	if (!all_matches)
 		die("cannot describe '%s'", sha1_to_hex(cmit->object.sha1));
@@ -210,6 +227,8 @@ int cmd_describe(int argc, const char **argv, const char *prefix)
 			all = 1;
 		else if (!strcmp(arg, "--tags"))
 			tags = 1;
+		else if (!strcmp(arg, "--debug"))
+			debug = 1;
 		else if (!strncmp(arg, "--abbrev=", 9)) {
 			abbrev = strtoul(arg + 9, NULL, 10);
 			if (abbrev < MINIMUM_ABBREV || 40 < abbrev)