patch, 4 partsHash tags by commit SHA1 in git-describe.

diff --git a/builtin-describe.c b/builtin-describe.c
index ad672aa..582ef02 100644
--- a/builtin-describe.c
+++ b/builtin-describe.c
@@ -12,20 +12,20 @@ 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 abbrev = DEFAULT_ABBREV;
 
-static int names, allocs;
+static unsigned int names[256], allocs[256];
 static struct commit_name {
 	struct commit *commit;
 	int prio; /* annotated tag = 2, tag = 1, head = 0 */
 	char path[FLEX_ARRAY]; /* more */
-} **name_array = NULL;
+} **name_array[256];
 
 static struct commit_name *match(struct commit *cmit)
 {
-	int i = names;
-	struct commit_name **p = name_array;
+	unsigned char m = cmit->object.sha1[0];
+	unsigned int i = names[m];
+	struct commit_name **p = name_array[m];
 
 	while (i-- > 0) {
 		struct commit_name *n = *p++;
@@ -42,17 +42,19 @@ static void add_to_known_names(const char *path,
 	int idx;
 	int len = strlen(path)+1;
 	struct commit_name *name = xmalloc(sizeof(struct commit_name) + len);
+	unsigned char m = commit->object.sha1[0];
 
 	name->commit = commit;
 	name->prio = prio;
 	memcpy(name->path, path, len);
-	idx = names;
-	if (idx >= allocs) {
-		allocs = (idx + 50) * 3 / 2;
-		name_array = xrealloc(name_array, allocs*sizeof(*name_array));
+	idx = names[m];
+	if (idx >= allocs[m]) {
+		allocs[m] = (idx + 50) * 3 / 2;
+		name_array[m] = xrealloc(name_array[m],
+			allocs[m] * sizeof(*name_array));
 	}
-	name_array[idx] = name;
-	names = ++idx;
+	name_array[m][idx] = name;
+	names[m] = ++idx;
 }
 
 static int get_name(const char *path, const unsigned char *sha1, int flag, void *cb_data)
@@ -121,9 +123,12 @@ static void describe(const char *arg, int last_one)
 		die("%s is not a valid '%s' object", arg, commit_type);
 
 	if (!initialized) {
+		unsigned int m;
 		initialized = 1;
 		for_each_ref(get_name, NULL);
-		qsort(name_array, names, sizeof(*name_array), compare_names);
+		for (m = 0; m < ARRAY_SIZE(name_array); m++)
+			qsort(name_array[m], names[m],
+				sizeof(*name_array[m]), compare_names);
 	}
 
 	n = match(cmit);

diff --git a/builtin-describe.c b/builtin-describe.c
index 582ef02..5d6865b 100644
--- a/builtin-describe.c
+++ b/builtin-describe.c
@@ -23,14 +23,24 @@ static struct commit_name {
 
 static struct commit_name *match(struct commit *cmit)
 {
-	unsigned char m = cmit->object.sha1[0];
-	unsigned int i = names[m];
-	struct commit_name **p = name_array[m];
-
-	while (i-- > 0) {
-		struct commit_name *n = *p++;
-		if (n->commit == cmit)
-			return n;
+	unsigned char level0 = cmit->object.sha1[0];
+	struct commit_name **p = name_array[level0];
+	unsigned int hi = names[level0];
+	unsigned int lo = 0;
+
+	while (lo < hi) {
+		unsigned int mi = (lo + hi) / 2;
+		int cmp = hashcmp(p[mi]->commit->object.sha1,
+			cmit->object.sha1);
+		if (!cmp) {
+			while (mi && p[mi - 1]->commit == cmit)
+				mi--;
+			return p[mi];
+		}
+		if (cmp > 0)
+			hi = mi;
+		else
+			lo = mi+1;
 	}
 	return NULL;
 }
@@ -95,7 +105,10 @@ static int compare_names(const void *_a, const void *_b)
 	struct commit_name *b = *(struct commit_name **)_b;
 	unsigned long a_date = a->commit->date;
 	unsigned long b_date = b->commit->date;
+	int cmp = hashcmp(a->commit->object.sha1, b->commit->object.sha1);
 
+	if (cmp)
+		return cmp;
 	if (a->prio != b->prio)
 		return b->prio - a->prio;
 	return (a_date > b_date) ? -1 : (a_date == b_date) ? 0 : 1;

Documentation/git-describe.txt, builtin-describe.c

diff --git a/Documentation/git-describe.txt b/Documentation/git-describe.txt
index 2700f35..b87783c 100644
--- a/Documentation/git-describe.txt
+++ b/Documentation/git-describe.txt
@@ -35,6 +35,16 @@ OPTIONS
 	Instead of using the default 8 hexadecimal digits as the
 	abbreviated object name, use <n> digits.
 
+--candidates=<n>::
+	Instead of considering only the 10 most recent tags as
+	candidates to describe the input committish consider
+	up to <n> candidates.  Increasing <n> above 10 will take
+	slightly longer but may produce a more accurate result.
+
+--debug::
+	Verbosely display information about the searching strategy
+	being employed to standard error.  The tag name will still
+	be printed to standard out.
 
 EXAMPLES
 --------
@@ -63,6 +73,26 @@ the output shows the reference path as well:
 	[torvalds@g5 git]$ git describe --all HEAD^
 	heads/lt/describe-g975b
 
+SEARCH STRATEGY
+---------------
+
+For each committish supplied "git describe" will first look for
+a tag which tags exactly that commit.  Annotated tags will always
+be preferred over lightweight tags, and tags with newer dates will
+always be preferred over tags with older dates.  If an exact match
+is found, its name will be output and searching will stop.
+
+If an exact match was not found "git describe" will walk back
+through the commit history to locate an ancestor commit which
+has been tagged.  The ancestor's tag will be output along with an
+abbreviation of the input committish's SHA1.
+
+If multiple tags were found during the walk then the tag which
+has the fewest commits different from the input committish will be
+selected and output.  Here fewest commits different is defined as
+the number of commits which would be shown by "git log tag..input"
+will be the smallest number of commits possible.
+
 
 Author
 ------
diff --git a/builtin-describe.c b/builtin-describe.c
index 5d6865b..421658d 100644
--- a/builtin-describe.c
+++ b/builtin-describe.c
@@ -2,17 +2,19 @@
 #include "commit.h"
 #include "tag.h"
 #include "refs.h"
-#include "diff.h"
-#include "diffcore.h"
-#include "revision.h"
 #include "builtin.h"
 
+#define SEEN		(1u<<0)
+#define MAX_TAGS	(FLAG_BITS - 1)
+
 static const char describe_usage[] =
 "git-describe [--all] [--tags] [--abbrev=<n>] <committish>*";
 
+static int debug;	/* Display lots of verbose info */
 static int all;	/* Default to annotated tags only */
 static int tags;	/* But allow any tags if --tags is specified */
 static int abbrev = DEFAULT_ABBREV;
+static int max_candidates = 10;
 
 static unsigned int names[256], allocs[256];
 static struct commit_name {
@@ -115,19 +117,21 @@ static int compare_names(const void *_a, const void *_b)
 }
 
 struct possible_tag {
-	struct possible_tag *next;
 	struct commit_name *name;
 	unsigned long depth;
+	unsigned flag_within;
 };
 
 static void describe(const char *arg, int last_one)
 {
 	unsigned char sha1[20];
-	struct commit *cmit;
+	struct commit *cmit, *gave_up_on = NULL;
 	struct commit_list *list;
 	static int initialized = 0;
 	struct commit_name *n;
-	struct possible_tag *all_matches, *min_match, *cur_match;
+	struct possible_tag all_matches[MAX_TAGS], *min_match;
+	unsigned int match_cnt = 0, annotated_cnt = 0, cur_match;
+	unsigned long seen_commits = 0;
 
 	if (get_sha1(arg, sha1))
 		die("Not a valid object name %s", arg);
@@ -150,71 +154,85 @@ static void describe(const char *arg, int last_one)
 		return;
 	}
 
+	if (debug)
+		fprintf(stderr, "searching to describe %s\n", arg);
+
 	list = NULL;
-	all_matches = NULL;
-	cur_match = NULL;
+	cmit->object.flags = SEEN;
 	commit_list_insert(cmit, &list);
 	while (list) {
 		struct commit *c = pop_commit(&list);
 		struct commit_list *parents = c->parents;
+		seen_commits++;
 		n = match(c);
 		if (n) {
-			struct possible_tag *p = xmalloc(sizeof(*p));
-			p->name = n;
-			p->next = NULL;
-			if (cur_match)
-				cur_match->next = p;
-			else
-				all_matches = p;
-			cur_match = p;
-			if (n->prio == 2)
-				continue;
+			if (match_cnt < max_candidates) {
+				struct possible_tag *t = &all_matches[match_cnt++];
+				t->name = n;
+				t->depth = seen_commits - 1;
+				t->flag_within = 1u << match_cnt;
+				c->object.flags |= t->flag_within;
+				if (n->prio == 2)
+					annotated_cnt++;
+			}
+			else {
+				gave_up_on = c;
+				break;
+			}
+		}
+		for (cur_match = 0; cur_match < match_cnt; cur_match++) {
+			struct possible_tag *t = &all_matches[cur_match];
+			if (!(c->object.flags & t->flag_within))
+				t->depth++;
+		}
+		if (annotated_cnt && !list) {
+			if (debug)
+				fprintf(stderr, "finished search at %s\n",
+					sha1_to_hex(c->object.sha1));
+			break;
 		}
 		while (parents) {
 			struct commit *p = parents->item;
 			parse_commit(p);
-			if (!(p->object.flags & SEEN)) {
-				p->object.flags |= SEEN;
+			if (!(p->object.flags & SEEN))
 				insert_by_date(p, &list);
-			}
+			p->object.flags |= c->object.flags;
 			parents = parents->next;
 		}
 	}
+	free_commit_list(list);
 
-	if (!all_matches)
+	if (!match_cnt)
 		die("cannot describe '%s'", sha1_to_hex(cmit->object.sha1));
 
-	min_match = NULL;
-	for (cur_match = all_matches; cur_match; cur_match = cur_match->next) {
-		struct rev_info revs;
-		struct commit *tagged = cur_match->name->commit;
-
-		clear_commit_marks(cmit, -1);
-		init_revisions(&revs, NULL);
-		tagged->object.flags |= UNINTERESTING;
-		add_pending_object(&revs, &tagged->object, NULL);
-		add_pending_object(&revs, &cmit->object, NULL);
-
-		prepare_revision_walk(&revs);
-		cur_match->depth = 0;
-		while ((!min_match || cur_match->depth < min_match->depth)
-			&& get_revision(&revs))
-			cur_match->depth++;
-		if (!min_match || (cur_match->depth < min_match->depth
-			&& cur_match->name->prio >= min_match->name->prio))
-			min_match = cur_match;
-		free_commit_list(revs.commits);
+	min_match = &all_matches[0];
+	for (cur_match = 1; cur_match < match_cnt; cur_match++) {
+		struct possible_tag *t = &all_matches[cur_match];
+		if (t->depth < min_match->depth
+			&& t->name->prio >= min_match->name->prio)
+			min_match = t;
+	}
+	if (debug) {
+		for (cur_match = 0; cur_match < match_cnt; cur_match++) {
+			struct possible_tag *t = &all_matches[cur_match];
+			fprintf(stderr, " %c %8lu %s\n",
+				min_match == t ? '*' : ' ',
+				t->depth, t->name->path);
+		}
+		fprintf(stderr, "traversed %lu commits\n", seen_commits);
+		if (gave_up_on) {
+			fprintf(stderr,
+				"more than %i tags found; listed %i most recent\n"
+				"gave up search at %s\n",
+				max_candidates, max_candidates,
+				sha1_to_hex(gave_up_on->object.sha1));
+		}
 	}
 	printf("%s-g%s\n", min_match->name->path,
 		   find_unique_abbrev(cmit->object.sha1, abbrev));
 
-	if (!last_one) {
-		for (cur_match = all_matches; cur_match; cur_match = min_match) {
-			min_match = cur_match->next;
-			free(cur_match);
-		}
-		clear_commit_marks(cmit, SEEN);
-	}
+	if (!last_one)
+		clear_commit_marks(cmit, -1);
 }
 
 int cmd_describe(int argc, const char **argv, const char *prefix)
@@ -226,6 +244,8 @@ int cmd_describe(int argc, const char **argv, const char *prefix)
 
 		if (*arg != '-')
 			break;
+		else if (!strcmp(arg, "--debug"))
+			debug = 1;
 		else if (!strcmp(arg, "--all"))
 			all = 1;
 		else if (!strcmp(arg, "--tags"))
@@ -235,6 +255,13 @@ int cmd_describe(int argc, const char **argv, const char *prefix)
 			if (abbrev < MINIMUM_ABBREV || 40 < abbrev)
 				abbrev = DEFAULT_ABBREV;
 		}
+		else if (!strncmp(arg, "--candidates=", 13)) {
+			max_candidates = strtoul(arg + 13, NULL, 10);
+			if (max_candidates < 1)
+				max_candidates = 1;
+			else if (max_candidates > MAX_TAGS)
+				max_candidates = MAX_TAGS;
+		}
 		else
 			usage(describe_usage);
 	}