diff options
| author | Florian Weimer <fweimer@redhat.com> | 2019-11-04 18:08:50 +0100 |
|---|---|---|
| committer | Florian Weimer <fweimer@redhat.com> | 2019-11-11 14:18:36 +0100 |
| commit | 0fa7402cbb4c88ab230eb4447f3fc2a182b17ae7 (patch) | |
| tree | 8dcb0e9290f954d8aab8fea45a969904258a1b17 | |
| parent | 0e5a24f5a968c0f791ea5e6625ad41a27c82cce6 (diff) | |
| download | glibc-0fa7402cbb4c88ab230eb4447f3fc2a182b17ae7.tar glibc-0fa7402cbb4c88ab230eb4447f3fc2a182b17ae7.tar.gz glibc-0fa7402cbb4c88ab230eb4447f3fc2a182b17ae7.tar.bz2 glibc-0fa7402cbb4c88ab230eb4447f3fc2a182b17ae7.zip | |
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
| -rw-r--r-- | elf/dl-lookup.c | 20 | ||||
| -rw-r--r-- | 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; |