This is the mail archive of the
gdb-patches@sourceware.org
mailing list for the GDB project.
Re: [PATCH] Replace hash function from bcache with fast_hash
- From: Simon Marchi <simark at simark dot ca>
- To: Christian Biesinger <cbiesinger at google dot com>, gdb-patches at sourceware dot org
- Date: Tue, 3 Dec 2019 15:36:32 -0500
- Subject: Re: [PATCH] Replace hash function from bcache with fast_hash
- References: <20191203010207.63155-1-cbiesinger@google.com>
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