Re: [PATCH 1/4] hashmap: introduce memhash_feed to access the internals of FNV-1 hash

From: René Scharfe <l.s.r@web.de>
Date: Oct 24, 2017, 20:23 UTC
Message-ID: <06c950e8-92c6-4926-ccac-2827d480f373@web.de>
In-Reply-To: <20171024185917.20515-2-sbeller@google.com>

Am 24.10.2017 um 20:59 schrieb Stefan Beller:

Show 17 quoted lines

> This will be useful shortly.
> 
> Signed-off-by: Stefan Beller <sbeller@google.com>
> ---
>   hashmap.c | 7 ++++++-
>   hashmap.h | 3 +++
>   2 files changed, 9 insertions(+), 1 deletion(-)
> 
> diff --git a/hashmap.c b/hashmap.c
> index d42f01ff5a..d103eb1fd2 100644
> --- a/hashmap.c
> +++ b/hashmap.c
> @@ -26,13 +26,18 @@ unsigned int strihash(const char *str)
>   	return hash;
>   }
>   
> +unsigned int memhash_feed(unsigned int hash_seed, const unsigned char next)

Why is the second parameter const and the first one isn't? (We tend not to bother with const for value types.)

Show 12 quoted lines

> +{
> +	return (hash_seed * FNV32_PRIME) ^ next;
> +}
> +
>   unsigned int memhash(const void *buf, size_t len)
>   {
>   	unsigned int hash = FNV32_BASE;
>   	unsigned char *ucbuf = (unsigned char *) buf;
>   	while (len--) {
>   		unsigned int c = *ucbuf++;
> -		hash = (hash * FNV32_PRIME) ^ c;
> +		hash = memhash_feed(hash, c);

I guess compilers inline a copy of the function here with -O2. My knee-jerk reaction, however, is horror in the face of adding a function call to the inner loop of a hash function. Do you have performance test results, ideally also with -O0? And why not make memhash_feed() an inline function or macro to sidestep that issue?

Show 22 quoted lines

>   	}
>   	return hash;
>   }
> diff --git a/hashmap.h b/hashmap.h
> index 7cb29a6aed..c2464385ed 100644
> --- a/hashmap.h
> +++ b/hashmap.h
> @@ -105,10 +105,13 @@
>    * `strihash` and `memihash` are case insensitive versions.
>    * `memihash_cont` is a variant of `memihash` that allows a computation to be
>    * continued with another chunk of data.
> + * `memhash_feed` takes just one character and returns the hash based off
> + * a previous hash.
>    */
>   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 memhash_feed(unsigned int hash_seed, const unsigned char next);
>   extern unsigned int memihash(const void *buf, size_t len);
>   extern unsigned int memihash_cont(unsigned int hash_seed, const void *buf, size_t len);
>   
>