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

From: Anders Kaseorg <andersk@ksplice.com>
Date: Dec 6, 2010, 07:19 UTC
Message-ID: <alpine.DEB.2.02.1012060149550.23348@dr-wily.mit.edu>
In-Reply-To: <20101203084348.GD18202@burratino>

On Fri, 3 Dec 2010, Jonathan Nieder wrote:

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

Will fix.

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

Will fix (I hate that idiom, but yeah, match existing style).

Show 12 quoted lines

> > +	for (e = names; e; e = e->next) {
> > +		if (!hashcmp(e->peeled, cmit->object.sha1) &&
> > +		    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)?

I don’t think it’s ever a problem: in my repository with 1800 tags on a warm cache, that loop accounts for about 0.1% of even the fastest non-exact-match query (a commit right after a tag).

> (If it's a problem in ordinary cases, I think the optimization could be 
> limited to --exact-match pretty easily.)

Then you’d lose the speedup in the case where --exact-match wasn’t specified but a tag happens to match exactly (which isn’t critical, but seemed nice).

> > -	for_each_ref(get_name, NULL);
> > +	for_each_rawref(get_name, NULL);
> 
> Orthogonal change snuck in?

This does fall under the category of “Don’t lookup commits,” and is necessary to get the speedup (otherwise for_each_ref has already looked up the commits that the rest of the patch is trying to avoid looking up). But I could split it out if you want.

Anders