This is the mail archive of the
mailing list for the glibc project.
Re: DT_GNU_HASH latest patches
On Thu, 2006-07-06 at 20:21 +0200, Jakub Jelinek wrote:
> 1) swapped chainoff and bitmask in the buckets array pairs - bitmask
> is accessed first by ld.so, so it makes sense to put it first
So - it took a little while to understand your patch :-) from what I
see; we insert a 32bit bitmask into the buckets ( in addition to the
offset ) whose purpose is to reduce the number of L2 misses incurred by
lookups in the 'chain' by seeing if a given bit is set in that mask.
Each chain element sets a mask bit using bits 6-10 of the hash as an
integer offset / bit-mask (0-31 bits), that is then compared at lookup.
So - I guess that's an interesting new twist ;-) I'm not entirely sold
on it at 1st glance since it makes the working set larger and the access
pattern less predictable - but, if the numbers show it working nicely
that's great :-) - [ I found them slightly hard to read side-by-side ].
Some misc. other code questions:
+ if (buckets & new_hash_bit)
Since the average chain length is ~2.5 (say 3) entries; and we have 32
bits to play with here, assuming bits 6-10 are as random as we would
like, there is a P(1/10) here that this branch is taken - should we have
a __builtin_expect reflecting that ?
Similarly is it worth moving some more of the symtab/strtab
construction out of the hot path ?, but perhaps the compiler will do it:
if ((*hasharr & ~1u) == (new_hash & ~1u))
symidx = hasharr - map->l_gnu_chain_zero;
+ /* The tables for this map. */
+ const ElfW(Sym) *symtab = (const void *) D_PTR (map, l_info[DT_SYMTAB]);
+ const char *strtab = (const void *) D_PTR (map, l_info[DT_STRTAB]);
+ const ElfW(Half) *verstab = map->l_versyms;
sym = check_match (&symtab[symidx]);
if (sym != NULL)
[ and the same ? for the old style case, AFAIR - I did this in the
dynhash patch of old ]
Similarly - [ and I've no idea how these 'expect' markups really help
on various arches (as no doubt you've guessed by now ;-) ] this is
presumably a rather uncommon case:
+ /* If the hash table is empty there is nothing to do here. */
+ if (map->l_nbuckets == 0)
I guess now the common case in this loop is hitting buckets &
new_hash_bit and looping, is there anything else we can remove / defer /
annotate in that (now much hotter) loop.
Otherwise - this looks really interesting to me :-)
firstname.lastname@example.org <><, Pseudo Engineer, itinerant idiot