Re: [PATCH v2] dwarf_loader: use a better hashing function

[Arnaldo Carvalho de Melo <acme@kernel.org>]

Em Fri, Feb 12, 2021 at 12:01:04AM -0800, Bill Wendling escreveu:
> This hashing function[1] produces better hash table bucket
> distributions. The original hashing function always produced zeros in
> the three least significant bits. The new hashing function gives a
> modest performance boost:

Some tidbits:

You forgot to CC Andrii and also to add this, which I'm doing now:

Suggested-by: Andrii Nakryiko <andrii@kernel.org>

:-)

- Arnaldo
 
>   Original: 0:11.373s
>   New:      0:11.110s
> 
> for a performance improvement of ~2%.
> 
> [1] From the hash function used in libbpf.
> 
> Signed-off-by: Bill Wendling <morbo@google.com>
> ---
>  hash.h | 20 +-------------------
>  1 file changed, 1 insertion(+), 19 deletions(-)
> 
> diff --git a/hash.h b/hash.h
> index d3aa416..6f952c7 100644
> --- a/hash.h
> +++ b/hash.h
> @@ -33,25 +33,7 @@
>  
>  static inline uint64_t hash_64(const uint64_t val, const unsigned int bits)
>  {
> -	uint64_t hash = val;
> -
> -	/*  Sigh, gcc can't optimise this alone like it does for 32 bits. */
> -	uint64_t n = hash;
> -	n <<= 18;
> -	hash -= n;
> -	n <<= 33;
> -	hash -= n;
> -	n <<= 3;
> -	hash += n;
> -	n <<= 3;
> -	hash -= n;
> -	n <<= 4;
> -	hash += n;
> -	n <<= 2;
> -	hash += n;
> -
> -	/* High bits are more random, so use them. */
> -	return hash >> (64 - bits);
> +	return (val * 11400714819323198485LLU) >> (64 - bits);
>  }
>  
>  static inline uint32_t hash_32(uint32_t val, unsigned int bits)
> -- 
> 2.30.0.478.g8a0d178c01-goog
> 

-- 

- Arnaldo