Subject: Re: [PATCH] git gc: Speed it up by 18% via faster hash comparisons

From: Ingo Molnar <[email-masked]>
Date: Thu, 28 Apr 2011 15:37:08 +0200

* Jonathan Nieder <[email-masked]> wrote:

> Hi,
> 
> A side note for amusement.
> 
> Erik Faye-Lund wrote:
> 
> > --- a/cache.h
> > +++ b/cache.h
> > @@ -681,13 +681,17 @@ extern char *sha1_pack_name(const unsigned char *sha1);
> >  extern char *sha1_pack_index_name(const unsigned char *sha1);
> >  extern const char *find_unique_abbrev(const unsigned char *sha1, int);
> >  extern const unsigned char null_sha1[20];
> > -static inline int is_null_sha1(const unsigned char *sha1)
> > +static inline int hashcmp(const unsigned char *sha1, const unsigned char *sha2)
> >  {
> > -	return !memcmp(sha1, null_sha1, 20);
> > +	/* early out for fast mis-match */
> > +	if (*sha1 != *sha2)
> > +		return *sha1 - *sha2;
> > +
> > +	return memcmp(sha1 + 1, sha2 + 1, 19);
> >  }
> 
> On the off-chance that sha1 and sha2 are nicely aligned, a more
> redundant
> 
> 	if (*sha1 != *sha2)
> 		return *sha1 - *sha2;
> 
> 	return memcmp(sha1, sha2, 20);
> 
> would take advantage of that (yes, this is just superstition, but it
> somehow seems comforting anyway).

Your variant also makes the code slightly more compact as the sha1+1 and sha2+1 
addresses do not have to be computed. I'll re-test and resend this variant.

Thanks,

	Ingo