This is the mail archive of the
libc-alpha@sourceware.org
mailing list for the glibc project.
Re: DT_GNU_HASH: reducing working set ...
- From: Michael Meeks <michael dot meeks at novell dot com>
- To: Jakub Jelinek <jakub at redhat dot com>
- Cc: binutils at sources dot redhat dot com, libc-alpha at sources dot redhat dot com, Ulrich Drepper <drepper at redhat dot com>
- Date: Mon, 03 Jul 2006 19:21:22 +0100
- Subject: Re: DT_GNU_HASH: reducing working set ...
- References: <20060628170900.GX3823@sunsite.mff.cuni.cz> <1151605626.20187.72.camel@t60p.site> <20060629193926.GZ3823@sunsite.mff.cuni.cz> <1151939720.17892.98.camel@t60p.site> <20060703155925.GE3823@sunsite.mff.cuni.cz>
- Reply-to: michael dot meeks at novell dot com
On Mon, 2006-07-03 at 17:59 +0200, Jakub Jelinek wrote:
> Ok, good we are on the same page ;)
:-)
> Djamel privately mentioned to me today that indeed if we require
> nbuckets > 1 for valid .gnu.hash sections, we can get the chain
> termination bit for free, i.e. not causing any extra collisions.
> That's because if nbuckets > 1, then (hash+1) % nbuckets != hash % nbuckets,
> so the bottom-most bit is effectively encoded in the bucket.
Ah - that's a neat trick: nice [ not that it isn't worth the single bit
anyway of course, as per convoluted calculations ;-]
> We have 2 options, either we create a 1:1 correspondence between the chain
> position and .dynsym index (and perhaps sort the UNDEF symbols high, so that
> we can trim the end of the .gnu.hash section), or we can store some addend
> into the second word of .gnu.hash (before the buckets array).
The addend sounds nice.
Of course - it depends on how hard to calculate the hash function is:
we could of course use a rather stronger / slower hash: and simply store
the value for all symbols [ regardless of def/undef etc. ] in the .chain
- and instead of calculating, look them up. [ Of course to calculate the
string hash we have to take a .dynstr cache miss in the 1st place so -
perhaps it's worthwhile ? ].
Of course, if we do that, then it does in fact make sense to have the
-Bdirect indexes next to the undef symbols, so - OTOH - perhaps that
sort of thing does belong in another section;
> ELF requires that the STB_LOCAL symbols are at the beginning, not end of
> the .dynsym section.
Yep - I fell over that :-)
> The UNDEF symbols can of course be anywhere (after
> the STB_LOCAL symbols). On most of the arches there are only a few
> STB_LOCAL symbols (< ~20), but on e.g. ia64 there are really many
> (e.g. ia64 glibc has ~ 420 such symbols, all caused by relocations).
> So, perhaps using the addend would be best.
That's interesting; I have an architecturally blinkered view.
> I will rework the patch now.
Thanks,
Michael.
--
michael.meeks@novell.com <><, Pseudo Engineer, itinerant idiot