Re: [PATCH 2/5] hashmap: allow memihash computation to be continued

From: Johannes Schindelin <johannes.schindelin@gmx.de>
Date: Feb 20, 2017, 12:43 UTC
Message-ID: <alpine.DEB.2.20.1702201342020.3496@virtualbox>
In-Reply-To: <xmqq7f4onjrs.fsf@gitster.mtv.corp.google.com>

Hi Junio,

On Fri, 17 Feb 2017, Junio C Hamano wrote:

Show 34 quoted lines

> Johannes Schindelin <johannes.schindelin@gmx.de> writes:
> 
> > diff --git a/hashmap.c b/hashmap.c
> > index b10b642229c..061b7d61da6 100644
> > --- a/hashmap.c
> > +++ b/hashmap.c
> > @@ -50,6 +50,20 @@ unsigned int memihash(const void *buf, size_t len)
> >  	return hash;
> >  }
> >  
> > +/* Incoporate another chunk of data into a memihash computation. */
> > +unsigned int memihash_continue(unsigned int hash,
> > +			       const void *buf, size_t len)
> > +{
> > +	const unsigned char *p = buf;
> > +	while (len--) {
> > +		unsigned int c = *p++;
> > +		if (c >= 'a' && c <= 'z')
> > +			c -= 'a' - 'A';
> > +		hash = (hash * FNV32_PRIME) ^ c;
> > +	}
> > +	return hash;
> > +}
> 
> This makes me wonder if we want to reduce the duplication (primarily
> to avoid risking the loop body to go out of sync) by doing:
> 
> 	unsigned int memihash(const void *buf, size_t len)
> 	{
> 		return memihash_continue(buf, len, FNV32_BASE);
> 	}                
> 
> If an extra call level really matters, its "inline" equivalent in
> the header would probably be good.

Well, the hashing is supposed to be as fast as possible, so I would like to avoid that extra call level. However, the end result is not so pretty because FNV32_BASE needs to be made public (OTOH it removes more lines than it adds):

-- snipsnap --

diff --git a/hashmap.c b/hashmap.c
index 061b7d61da6..470a0832688 100644
--- a/hashmap.c
+++ b/hashmap.c
@@ -4,7 +4,6 @@
 #include "cache.h"
 #include "hashmap.h"
 
-#define FNV32_BASE ((unsigned int) 0x811c9dc5)
 #define FNV32_PRIME ((unsigned int) 0x01000193)
 
 unsigned int strhash(const char *str)
@@ -37,19 +36,6 @@ unsigned int memhash(const void *buf, size_t len)
 	return hash;
 }
 
-unsigned int memihash(const void *buf, size_t len)
-{
-	unsigned int hash = FNV32_BASE;
-	unsigned char *ucbuf = (unsigned char *) buf;
-	while (len--) {
-		unsigned int c = *ucbuf++;
-		if (c >= 'a' && c <= 'z')
-			c -= 'a' - 'A';
-		hash = (hash * FNV32_PRIME) ^ c;
-	}
-	return hash;
-}
-
 /* Incoporate another chunk of data into a memihash computation. */
 unsigned int memihash_continue(unsigned int hash,
 			       const void *buf, size_t len)
diff --git a/hashmap.h b/hashmap.h
index 78e14dfde71..a1a8fd7dc54 100644
--- a/hashmap.h
+++ b/hashmap.h
@@ -8,12 +8,17 @@
 
 /* FNV-1 functions */
 
+#define FNV32_BASE ((unsigned int) 0x811c9dc5)
+
 extern unsigned int strhash(const char *buf);
 extern unsigned int strihash(const char *buf);
 extern unsigned int memhash(const void *buf, size_t len);
-extern unsigned int memihash(const void *buf, size_t len);
 extern unsigned int memihash_continue(unsigned int hash_seed,
 				      const void *buf, size_t len);
+static inline unsigned int memihash(const void *buf, size_t len)
+{
+	return memihash_continue(FNV32_BASE, buf, len);
+}
 
 static inline unsigned int sha1hash(const unsigned char *sha1)
 {