Re: [PATCH] describe: Don’t look up commits with --exact-match

From: Jonathan Nieder <jrnieder@gmail.com>
Date: Dec 3, 2010, 08:43 UTC
Message-ID: <20101203084348.GD18202@burratino>
In-Reply-To: <alpine.DEB.2.02.1011171830050.14285@dr-wily.mit.edu>

(+cc: completion people, who might test; Thomas, who knows this code well)

Anders Kaseorg wrote:

> This makes ‘git describe --exact-match HEAD’ about 15 times faster on
> a cold cache (2.3s instead of 35s) in a linux-2.6 repository with many
> packed tags.  That’s a huge win for the interactivity of the __git_ps1
> shell prompt helper.

Nice.

Show 8 quoted lines

> --- a/builtin/describe.c
> +++ b/builtin/describe.c
> @@ -22,7 +22,7 @@ static int tags;	/* Allow lightweight tags */
>  static int longformat;
>  static int abbrev = DEFAULT_ABBREV;
>  static int max_candidates = 10;
> -static int found_names;
> +struct commit_name *names = NULL;

Nits:
 - static?
 - the convention in git is to leave off the zero-initializers
   for bss-allocated vars (static and globals).

Show 9 quoted lines

> @@ -34,6 +34,8 @@ static const char *diff_index_args[] = {
>  
>  
>  struct commit_name {
> +	struct commit_name *next;
> +	unsigned char peeled[20];
>  	struct tag *tag;
>  	unsigned prio:2; /* annotated tag = 2, tag = 1, head = 0 */
>  	unsigned name_checked:1;

Hm, so the tags read so far will be stored in the "names" list.

Show 8 quoted lines

> @@ -240,7 +231,12 @@ static void describe(const char *arg, int last_one)
>  	if (!cmit)
>  		die("%s is not a valid '%s' object", arg, commit_type);
>  
> -	n = cmit->util;
> +	n = NULL;
> +	for (e = names; e; e = e->next) {
> +		if (hashcmp(e->peeled, cmit->object.sha1) == 0 &&

The usual convention is to use !hashcmp(...) to match the !strcmp(...) idiom.

> +		    replace_name(n, e->prio, e->sha1, &e->tag))
> +			n = e;
> +	}

Instead of looking up the commit to be matched exactly in the commits hash table, this makes a linear search.

No change to the assymptotic running time, but would this make things much slower in the case of many tags? How many before it's a problem (if ever)? (If it's a problem in ordinary cases, I think the optimization could be limited to --exact-match pretty easily.)

Show 9 quoted lines

> @@ -259,6 +255,12 @@ static void describe(const char *arg, int last_one)
>  	if (debug)
>  		fprintf(stderr, "searching to describe %s\n", arg);
>  
> +	for (e = names; e; e = e->next) {
> +		struct commit *c = lookup_commit_reference_gently(e->peeled, 1);
> +		if (c && replace_name(c->util, e->prio, e->sha1, &e->tag))
> +			c->util = e;
> +	}

Filling the commits table in preparation for object traversal. Now the world's back to normal.

Show 6 quoted lines

> @@ -418,8 +420,8 @@ int cmd_describe(int argc, const char **argv, const char *prefix)
>  		return cmd_name_rev(i + argc, args, prefix);
>  	}
>  
> -	for_each_ref(get_name, NULL);
> +	for_each_rawref(get_name, NULL);

Orthogonal change snuck in?

> -	if (!found_names && !always)
> +	if (!names && !always)

Everything else looks good and very readable.