From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 115310 invoked by alias); 3 Dec 2019 21:26:28 -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 115299 invoked by uid 89); 3 Dec 2019 21:26:27 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-29.5 required=5.0 tests=AWL,BAYES_00,ENV_AND_HDR_SPF_MATCH,GIT_PATCH_0,GIT_PATCH_1,GIT_PATCH_2,GIT_PATCH_3,KAM_ASCII_DIVIDERS,RCVD_IN_DNSWL_NONE,SPF_PASS,USER_IN_DEF_SPF_WL autolearn=ham version=3.3.1 spammy= X-HELO: mail-ot1-f65.google.com Received: from mail-ot1-f65.google.com (HELO mail-ot1-f65.google.com) (209.85.210.65) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Tue, 03 Dec 2019 21:26:26 +0000 Received: by mail-ot1-f65.google.com with SMTP id k14so4361996otn.4 for ; Tue, 03 Dec 2019 13:26:26 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20161025; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=v70MVhzCEBRRi1VL4dT7T1Ce8aun85HWPIoC+qpyNmA=; b=fbLCFN6W2Ijru0VtTo0wJY11lRkUlRH9CBvvwZfEnttkuZG50T4SFP/8BxHnTM6bqh uuTUO49/948Pnrj7RGZJ66ap4mPnuhGCMn+n9IRzWJCvPIfSMbjQo0J06RHyFtvdvIpE Z/o0VCiqLtZbHFbhx/Go029aRvJB1puip8OWHgWRtBVkRKTU37eqFFsn9FspiSll4f+y TyPZ/txc/NA6eooNJTjJ+fo87+AtOJm4AvoFW2lQBnSLpKa/9UwLZcEqPu/6XkLxPqq3 KeG7s5nFf477hF0s0vdNGwULiyEp7pPpQ7ePmwheKAfU/cS7pK9px7p2VqlAsIShEsOo NDNg== MIME-Version: 1.0 References: <20191203010207.63155-1-cbiesinger@google.com> <4a3b10ab-4105-8d41-0f6b-e138571d5dff@simark.ca> In-Reply-To: <4a3b10ab-4105-8d41-0f6b-e138571d5dff@simark.ca> From: "Christian Biesinger via gdb-patches" Reply-To: Christian Biesinger Date: Tue, 03 Dec 2019 21:26:00 -0000 Message-ID: Subject: Re: [PATCH] Replace hash function from bcache with fast_hash To: Simon Marchi Cc: gdb-patches Content-Type: text/plain; charset="UTF-8" X-IsSubscribed: yes X-SW-Source: 2019-12/txt/msg00105.txt.bz2 On Tue, Dec 3, 2019 at 2:36 PM Simon Marchi wrote: > > 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. Done. > > + return fast_hash (ptr, length, 0); > > + } > > Can this method be private, just like `compare` is? Done. > > + > > /* 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. Done. > > 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 Done, thanks. Will push now with those fixes. Christian