This is the mail archive of the libc-alpha@sourceware.org mailing list for the glibc project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: DT_GNU_HASH: ~ 50% dynamic linking improvement


On Tue, Jul 04, 2006 at 10:50:50PM +0000, djamel anonymous wrote:
> first thank you, for your reply. i am sending this mail to explain further 
> my idea.My suggestion
> was made primarily because of 2 assumptions:

I think you can implement the same while still not increasing the number of
used cache lines in the successful case.

Just put the bitmask along the chain offsets in the buckets array, then
(assuming .gnu.hash is always >= 8B aligned, which we can cheaply ensure),
the bitmask word will always be in the same cache line as the offset
into the chain array.  In this case, for successful lookup or unsuccessful
one where the bit is not set in the bitmask we need just one cache line
access, otherwise it uses 2 (or more) as it used before.  The shorter the
chain, the higher probability the bitmask saves the extra cache line read.
For extremely long chains, it wouldn't help at all (chain length >= 32
assuming all hash values in the chain have different topmost 5 bits),
but chains with length >= 7 are really rare and even for chain length
7 the probability the bitmask helps is ~ 78%.

The disadvantage of course is the increase in the .gnu.hash section
size, which grows from current
(2 + nbuckets + nsyms) * 4
to
(2 + 2 * nbuckets + nsyms) * 4.

I'll try to benchmark both of these variants and see if it is really worth
it.

Here is the interdiff on how would the glibc side of changes for
this look like (and I'm attaching also Uli's 2006-07-03 patch, which
hasn't been posted yet).

--- libc/elf/dl-lookup.c.jj	2006-07-05 08:59:01.000000000 +0200
+++ libc/elf/dl-lookup.c	2006-07-05 09:01:53.000000000 +0200
@@ -380,8 +380,8 @@ _dl_setup_hash (struct link_map *map)
 				      + DT_EXTRANUM + DT_VALNUM]);
       map->l_nbuckets = *hash32++;
       map->l_gnu_symbias = *hash32++;
-      map->l_gnu_buckets = hash32;
-      hash32 += map->l_nbuckets;
+      map->l_gnu_buckets = (void *) hash32;
+      hash32 += 2 * map->l_nbuckets;
       map->l_gnu_hashbase = hash32;
       return;
     }
--- libc/elf/do-lookup.h.jj	2006-07-05 08:59:01.000000000 +0200
+++ libc/elf/do-lookup.h	2006-07-05 09:07:22.000000000 +0200
@@ -169,10 +169,15 @@ do_lookup_x (const char *undef_name, uin
       if (__builtin_expect (map->l_gnu_buckets != NULL, 1))
 	{
 	  /* Use the new GNU-style hash table.  */
-	  size_t chainoff = map->l_gnu_buckets[new_hash % map->l_nbuckets];
+	  Elf32_Word bitmask
+	    = map->l_gnu_buckets[new_hash % map->l_nbuckets].bitmask;
 
-	  if (chainoff != 0xffffffff)
+	  /* Bitmask has bit N set iff any of the hash values in
+	     hasharr chain has (hash >> 27) == N.  */
+	  if (bitmask & (1 << (new_hash >> 27)))
 	    {
+	      size_t chainoff
+		= map->l_gnu_buckets[new_hash % map->l_nbuckets].chainoff;
 	      const Elf32_Word *hasharr = &map->l_gnu_hashbase[chainoff];
 	      Elf32_Word new_hash_masked = new_hash & ~1u;
 
--- libc/include/link.h.jj	2006-07-05 08:59:01.000000000 +0200
+++ libc/include/link.h	2006-07-05 09:00:41.000000000 +0200
@@ -141,7 +141,11 @@ struct link_map
 
     /* Symbol hash table.  */
     Elf_Symndx l_nbuckets;
-    const Elf32_Word *l_gnu_buckets;
+    const struct
+    {
+      Elf32_Word chainoff;
+      Elf32_Word bitmask;
+    } *l_gnu_buckets;
     union
     {
       const Elf32_Word *l_gnu_hashbase;

	Jakub

Attachment: glibc-gnu-hash.patch
Description: Text document


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]