Re: [PATCH] dwarf_loader: use a better hashing function

From: Andrii Nakryiko <andrii.nakryiko@gmail.com>
To: Bill Wendling <morbo@google.com>
Cc: dwarves@vger.kernel.org, bpf <bpf@vger.kernel.org>,
	Arnaldo Carvalho de Melo <arnaldo.melo@gmail.com>
Subject: Re: [PATCH] dwarf_loader: use a better hashing function
Date: Wed, 10 Feb 2021 17:31:48 -0800	[thread overview]
Message-ID: <CAEf4Bzap_SYhtQdLF8bMwVeag=8CGqpcnRFb=MtZX7CB7FwSYQ@mail.gmail.com> (raw)
In-Reply-To: <CAGG=3QW0zuXUcpkcZqnaZS77EABEshhPtUCTr71dDDMuL1oMZQ@mail.gmail.com>

On Wed, Feb 10, 2021 at 5:24 PM Bill Wendling <morbo@google.com> wrote:
>
> On Wed, Feb 10, 2021 at 4:00 PM Andrii Nakryiko
> <andrii.nakryiko@gmail.com> wrote:
> >
> > On Wed, Feb 10, 2021 at 3:25 PM Bill Wendling <morbo@google.com> wrote:
> > >
> > > 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 funciton gives a modest performance boost.
> > >
> > >       Original      New
> > >        0:11.41       0:11.38
> > >        0:11.36       0:11.34
> > >        0:11.35       0:11.26
> > >       -----------------------
> > >   Avg: 0:11.373      0:11.327
> > >
> > > for a performance improvement of 0.4%.
> > >
> > > [1] From Numerical Recipes, 3rd Ed. 7.1.4 Random Hashes and Random Bytes
> > >
> >
> > Can you please also test with the one libbpf uses internally:
> >
> > return (val * 11400714819323198485llu) >> (64 - bits);
> >
> > ?
> >
> > Thanks!
> >
> It's giving me a running time of ~11.11s, which is even better. Would
> you like me to submit a patch?

faster is better, so yeah, why not? :)

>
> -bw