Re: DT_GNU_HASH latest patches

[Michael Meeks <michael.meeks@novell.com>]

Hi Jakub,

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[0] & 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)
		      goto found_it;
		  }

	[ 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)
+	continue;

	I guess now the common case in this loop is hitting buckets[0] &
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 :-)

	Thanks,

		Michael.

-- 
 michael.meeks@novell.com  <><, Pseudo Engineer, itinerant idiot