[glibc/fw/dl-bind-performance] elf: Optimize symbol binding by pre-computing divisions

[Florian Weimer <fw@sourceware.org>]

https://sourceware.org/git/gitweb.cgi?p=glibc.git;h=0fa7402cbb4c88ab230eb4447f3fc2a182b17ae7

commit 0fa7402cbb4c88ab230eb4447f3fc2a182b17ae7
Author: Florian Weimer <fweimer@redhat.com>
Date:   Mon Nov 4 18:08:50 2019 +0100

    elf: Optimize symbol binding by pre-computing divisions
    
    The division for the hash table lookup shows up in profiles.  We can
    use a standard compiler optimization technique to speed up the hash
    table lookup.  The speedup is most pronounced when a symbol lookup
    succeeds early in the scope array, otherwise the bitmap check
    dominates the profiles.
    
    Change-Id: I898b7c711979447d4756b3f7b567c49a8d33187b

Diff:
---
 elf/dl-lookup.c | 20 ++++++++++++++++++--
 include/link.h  |  2 ++
 2 files changed, 20 insertions(+), 2 deletions(-)

diff --git a/elf/dl-lookup.c b/elf/dl-lookup.c
index fd44cd4101..205d043717 100644
--- a/elf/dl-lookup.c
+++ b/elf/dl-lookup.c
@@ -28,6 +28,7 @@
 #include <libc-lock.h>
 #include <tls.h>
 #include <atomic.h>
+#include <divopt.h>
 
 #include <assert.h>
 
@@ -394,8 +395,18 @@ do_lookup_x (const char *undef_name, uint_fast32_t new_hash,
 	  if (__glibc_unlikely ((bitmask_word >> hashbit1)
 				& (bitmask_word >> hashbit2) & 1))
 	    {
-	      Elf32_Word bucket = map->l_gnu_buckets[new_hash
-						     % map->l_nbuckets];
+	      Elf32_Word bucket;
+	      if (map->l_nbuckets > 1)
+		{
+		  uint32_t quotient
+		    = divopt_32 (new_hash, map->l_nbuckets_multiplier,
+				 map->l_nbuckets_multiplier_shift);
+		  uint32_t remainder = new_hash - map->l_nbuckets * quotient;
+		  bucket = map->l_gnu_buckets[remainder];
+		}
+	      else
+		bucket = map->l_gnu_buckets[0];
+
 	      if (bucket != 0)
 		{
 		  const Elf32_Word *hasharr = &map->l_gnu_chain_zero[bucket];
@@ -931,6 +942,11 @@ _dl_setup_hash (struct link_map *map)
       /* Initialize MIPS xhash translation table.  */
       ELF_MACHINE_XHASH_SETUP (hash32, symbias, map);
 
+      if (map->l_nbuckets >= 2)
+	map->l_nbuckets_multiplier_shift
+	  = precompute_divopt_32 (map->l_nbuckets,
+				  &map->l_nbuckets_multiplier);
+
       return;
     }
 
diff --git a/include/link.h b/include/link.h
index 1184201f91..b09aa81bb4 100644
--- a/include/link.h
+++ b/include/link.h
@@ -153,6 +153,8 @@ struct link_map
 
     /* Symbol hash table.  */
     Elf_Symndx l_nbuckets;
+    uint32_t l_nbuckets_multiplier;
+    int l_nbuckets_multiplier_shift;
     Elf32_Word l_gnu_bitmask_idxbits;
     Elf32_Word l_gnu_shift;
     const ElfW(Addr) *l_gnu_bitmask;