This is the mail archive of the
libc-alpha@sourceware.org
mailing list for the glibc project.
Re: [PATCH] DT_GNU_HASH: ~ 50% dynamic linking improvement
- From: Roland McGrath <roland at redhat dot com>
- To: Paul Eggert <eggert at CS dot UCLA dot EDU>
- Cc: Jakub Jelinek <jakub at redhat dot com>, binutils at sources dot redhat dot com, libc-alpha at sources dot redhat dot com, Michael Meeks <michael dot meeks at novell dot com>
- Date: Wed, 28 Jun 2006 12:10:51 -0700 (PDT)
- Subject: Re: [PATCH] DT_GNU_HASH: ~ 50% dynamic linking improvement
> Bernstein now prefers XOR, i.e.,
> "h = h * 33 ^ c;" instead of
> "h = h * 33 + c;". Did you try that as well?
> Several sources indicate it's a bit better, e.g.,
> <http://eternallyconfuzzled.com/tuts/hashing.html#djb2>.
We have not tried that function.
> > We have tested a bunch of different hash functions
>
> Which hash functions did you try? One-at-a-time? FNV? You'll
> probably get hassled by hash triviists (like me :-) no matter which
> function you choose, but you can forstall that to some extent by
> mentioning which functions you tested.
We tried the original ELF hash, the htab_hash_string function from
libiberty, and the full_name_hash function from Linux's <linux/dcache.h>.
We compared them using a real-world representative sample of symbol name
strings (collected from the dynamic symbols in a GNU/Linux installation).
We looked at the number of hash values shared by two symbols, the number
shared by three symbols (none were shared by more than three in our sample
set using any function we tried), and the length of common prefixes shared
by colliding symbols.
Thanks,
Roland