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

[Ingo Molnar <mingo@elte.hu>]

* Junio C Hamano <gitster@pobox.com> wrote:

> Ingo Molnar <mingo@elte.hu> writes:
> 
> > +static inline int hashcmp(const unsigned char *sha1, const unsigned char *sha2)
> >  {
> > -	return !memcmp(sha1, null_sha1, 20);
> > +	int i;
> > +
> > +	for (i = 0; i < 20; i++, sha1++, sha2++) {
> > +		if (*sha1 != *sha2) {
> > +			if (*sha1 < *sha2)
> > +				return -1;
> > +			return +1;
> > +		}
> > +	}
> > +
> > +	return 0;
> 
> This is very unfortunate, as it is so trivially correct and we shouldn't
> have to do it.  If the compiler does not use a good inlined memcmp(), this
> patch may fly, but I fear it may hurt other compilers, no?

Well, i used a very fresh GCC version:

  gcc version 4.6.0 20110419 (Red Hat 4.6.0-5) (GCC)

And used a relatively fresh CPU as well. So given how compiler and CPU versions 
trickle down to users and how long they live there Git will live with this 
combination for years to come.

Secondly, the combined speedup of the cached case with my two patches appears 
to be more than 30% on my testbox so it's a very nifty win from two relatively 
simple changes.

Should a compiler ever turn this into suboptimal code again we can revisit the 
issue once more - it's not like we *can* keep the compiler from messing up the 
assembly output! :-) ...

> > +static inline int is_null_sha1(const unsigned char *sha1)
> >  {
> > -	return memcmp(sha1, sha2, 20);
> > +	const unsigned long long *sha1_64 = (void *)sha1;
> > +	const unsigned int *sha1_32 = (void *)sha1;
> 
> Can everybody do unaligned accesses just fine?

I have added some quick debug code and none of the sha1 pointers (in my 
admittedly very limited) testing showed misaligned pointers on 64-bit systems.

On 32-bit systems the pointer might be 32-bit aligned only - the patch below 
implements the function 32-bit comparisons.

But is_null_sha1() is not called that often in the tests i've done so we could 
keep it untouched as well.

Thanks,

	Ingo

diff --git a/cache.h b/cache.h
index 2674f4c..427ad5a 100644
--- a/cache.h
+++ b/cache.h
@@ -675,14 +675,32 @@ 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);
+	int i;
+
+	for (i = 0; i < 20; i++, sha1++, sha2++) {
+		if (*sha1 != *sha2) {
+			if (*sha1 < *sha2)
+				return -1;
+			return +1;
+		}
+	}
+
+	return 0;
 }
-static inline int hashcmp(const unsigned char *sha1, const unsigned char *sha2)
+
+static inline int is_null_sha1(const unsigned char *sha1)
 {
-	return memcmp(sha1, sha2, 20);
+	const unsigned int *sha1_32 = (void *)sha1;
+
+	if (sha1_32[0] || sha1_32[1] || sha1_32[2] || sha1_32[3] || sha1_32[4])
+		return 0;
+
+	return 1;
 }
+
 static inline void hashcpy(unsigned char *sha_dst, const unsigned char *sha_src)
 {
 	memcpy(sha_dst, sha_src, 20);