Re: [PATCH] Replace hash function from bcache with fast_hash

[Simon Marchi <simark@simark.ca>]

On 2019-12-02 8:02 p.m., Christian Biesinger via gdb-patches wrote:
> This function is not just slower than xxhash, it is slower than
> even libiberty's iterative_hash, so there does not seem to be
> a reason for it to exist.
> 
> ------------------------------------------------------------
> Benchmark                     Time           CPU Iterations
> ------------------------------------------------------------
> BM_xxh3                      11 ns         11 ns   66127192
> BM_xxh32                     19 ns         19 ns   36792609
> BM_xxh64                     16 ns         16 ns   42941328
> BM_city32                    26 ns         26 ns   27028370
> BM_city64                    17 ns         17 ns   40472793
> BM_iterative_hash            77 ns         77 ns    9088854
> BM_bcache_hash              125 ns        125 ns    5599232
> 
> gdb/ChangeLog:
> 
> 2019-12-02  Christian Biesinger  <cbiesinger@google.com>
> 
> 	* bcache.c (hash): Remove.
> 	(hash_continue): Remove.
> 	* bcache.h (hash): Remove.
> 	(hash_continue): Remove.
> 	(struct bcache) <ctor>: Update.
> 	* psymtab.c (psymbol_hash): Update.
> 	* stabsread.c (hashname): Update.
> 	* utils.h (fast_hash): Add an argument for a start value,
> 	defaulting to zero.

LGTM, with the nits below fixed.

> diff --git a/gdb/bcache.h b/gdb/bcache.h
> index 15dcc63440..96f6d6813f 100644
> --- a/gdb/bcache.h
> +++ b/gdb/bcache.h
> @@ -138,13 +138,12 @@
>  
>  struct bstring;
>  
> -/* The hash functions */
> -extern unsigned long hash (const void *addr, int length);
> -extern unsigned long hash_continue (const void *addr, int length,
> -                                    unsigned long h);
> -
>  struct bcache
>  {
> +  static unsigned long default_hash (const void *ptr, int length) {

Brace on the next line.

> +    return fast_hash (ptr, length, 0);
> +  }

Can this method be private, just like `compare` is?

> +
>    /* Allocate a bcache.  HASH_FN and COMPARE_FN can be used to pass in
>       custom hash, and compare functions to be used by this bcache.  If
>       HASH_FUNCTION is NULL hash() is used and if COMPARE_FUNCTION is

This line of documentation should be updated, probably hash -> fast_hash.

> diff --git a/gdb/utils.h b/gdb/utils.h
> index 79c8a6fc8d..68376dac83 100644
> --- a/gdb/utils.h
> +++ b/gdb/utils.h
> @@ -571,17 +571,18 @@ extern void copy_bitwise (gdb_byte *dest, ULONGEST dest_offset,
>  			  const gdb_byte *source, ULONGEST source_offset,
>  			  ULONGEST nbits, int bits_big_endian);
>  
> -/* A fast hashing function.  This can be used to hash strings in a fast way
> +/* A fast hashing function.  This can be used to hash data in a fast way
>     when the length is known.  If no fast hashing library is available, falls
> -   back to iterative_hash from libiberty.  */
> +   back to iterative_hash from libiberty.  START_VALUE can be set to
> +   continue hashing from a previous value.  */
>  
>  static inline unsigned int
> -fast_hash (const char* str, size_t len)
> +fast_hash (const void* ptr, size_t len, unsigned int start_value = 0)

- const void* ptr
+ const void *ptr

Simon