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@xxxxxxxxxx>
:-)
- 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@xxxxxxxxxx>
> ---
> 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
