This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [PATCH 3/9] Use murmurhash3 for pointer map hashing
- From: Andi Kleen <andi at firstfloor dot org>
- To: Richard Biener <richard dot guenther at gmail dot com>
- Cc: gcc-patches at gcc dot gnu dot org, hubicka at ucw dot cz
- Date: Tue, 23 Apr 2013 07:28:59 -0700
- Subject: Re: [PATCH 3/9] Use murmurhash3 for pointer map hashing
- References: <1366407117-18462-1-git-send-email-andi at firstfloor dot org> <1366407117-18462-4-git-send-email-andi at firstfloor dot org> <CAFiYyc3btjf-4X2ozSw+9pAEtuzOyoaPejzoJQ-Myvf27e2S=A at mail dot gmail dot com> <20130422154241 dot GW22166 at tassilo dot jf dot intel dot com> <CAFiYyc3kCpVDBJUx2963e+PV22H+Seq5X4zX+RYApEJfWcgCpQ at mail dot gmail dot com> <20130423140858 dot GA22166 at tassilo dot jf dot intel dot com> <CAFiYyc2755_7o9RYWVWN264Fx2dz+FSvFnBHEjBhgaqDLOqXxQ at mail dot gmail dot com>
Richard Biener <richard.guenther@gmail.com> writes:
>>
>> One of the reasons I did it explicitely is that the murmur3 reference code is C++
>> (well really only the mixed code/declarations I think) and libiberty seems to be
>> C only. I suppose can port it to C and put it into libiberty though, and make
>> hashtab.c always use it.
>>
>> My understanding is that murmur is generally stronger than evahash.
>
> It would be nice to back this with some numbers on the collision rate
> for GCC hashtables,
I tested it for the preprocessor symbol hash at some point, but had some
second thoughts because it could potentially be called with unaligned
arguments (ok on x86 with murmur, but may not be elsewhere). Don't
remember the exact numbers, but I think it was a bit better.
For WPA types at least murmur3 got me from 70% collisions with the
eva ptrhash to 64%. The original was much worse.
Good point about the new hash table. Right now nothing using it is
on my performance radar though.
-Andi
--
ak@linux.intel.com -- Speaking for myself only