From: Ingo Molnar <mingo@elte.hu>
Date: Thu, 28 Apr 2011 09:33:07 GMT
Subject: Re: [PATCH] git gc: Speed it up by 18% via faster hash comparisons
Message-ID: <20110428093307.GA15349@elte.hu>
In-Reply-To: <BANLkTik_2sHZ0OTgQeHpRnpmNsAmT=sAcA@mail.gmail.com>


* Erik Faye-Lund <kusmabite@gmail.com> wrote:

> 2011/4/28 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;
> >> > +           }
> 
> Why not just:
> 
> if (*sha1 != *sha2)
>         return *sha2 - *sha1;

You mean "*sha1 - *sha2", right?

> memcmp isn't guaranteed to return onlt the values -1, 0, +1, it can
> return any value, just as long as it's sign of a non-zero return
> express the relationship between the first mis-matching byte.

Yeah, agreed, updated patch below. Seems to work fine here.

	Ingo

Signed-off-by: Ingo Molnar <mingo@elte.hu>

diff --git a/cache.h b/cache.h
index 2674f4c..574c948 100644
--- a/cache.h
+++ b/cache.h
@@ -675,14 +675,30 @@ 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)
+			return *sha1 - *sha2;
+	}
+
+	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 long long *sha1_64 = (void *)sha1;
+	const unsigned int *sha1_32 = (void *)sha1;
+
+	if (sha1_64[0] || sha1_64[1] || 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);