From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 129764 invoked by alias); 3 Dec 2019 20:36:38 -0000 Mailing-List: contact gdb-patches-help@sourceware.org; run by ezmlm Precedence: bulk List-Id: List-Subscribe: List-Archive: List-Post: List-Help: , Sender: gdb-patches-owner@sourceware.org Received: (qmail 129737 invoked by uid 89); 3 Dec 2019 20:36:37 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-17.9 required=5.0 tests=AWL,BAYES_00,GIT_PATCH_0,GIT_PATCH_1,GIT_PATCH_2,GIT_PATCH_3,KAM_ASCII_DIVIDERS,SPF_HELO_PASS,SPF_PASS autolearn=ham version=3.3.1 spammy=pm X-HELO: simark.ca Received: from simark.ca (HELO simark.ca) (158.69.221.121) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Tue, 03 Dec 2019 20:36:35 +0000 Received: from [172.16.0.95] (192-222-181-218.qc.cable.ebox.net [192.222.181.218]) (using TLSv1.3 with cipher TLS_AES_128_GCM_SHA256 (128/128 bits) key-exchange X25519 server-signature RSA-PSS (2048 bits) server-digest SHA256) (No client certificate requested) by simark.ca (Postfix) with ESMTPSA id 299E61E092; Tue, 3 Dec 2019 15:36:34 -0500 (EST) Subject: Re: [PATCH] Replace hash function from bcache with fast_hash To: Christian Biesinger , gdb-patches@sourceware.org References: <20191203010207.63155-1-cbiesinger@google.com> From: Simon Marchi Message-ID: <4a3b10ab-4105-8d41-0f6b-e138571d5dff@simark.ca> Date: Tue, 03 Dec 2019 20:36:00 -0000 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:68.0) Gecko/20100101 Thunderbird/68.2.1 MIME-Version: 1.0 In-Reply-To: <20191203010207.63155-1-cbiesinger@google.com> Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 7bit X-SW-Source: 2019-12/txt/msg00101.txt.bz2 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 > > * bcache.c (hash): Remove. > (hash_continue): Remove. > * bcache.h (hash): Remove. > (hash_continue): Remove. > (struct bcache) : 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