From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 2178) id 8CCD63854D9E; Mon, 11 Apr 2022 14:07:01 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 8CCD63854D9E Content-Type: text/plain; charset="us-ascii" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit From: Florian Weimer To: glibc-cvs@sourceware.org Subject: [glibc/fw/dl-bind-performance] elf: Optimize symbol binding by pre-computing divisions X-Act-Checkin: glibc X-Git-Author: Florian Weimer X-Git-Refname: refs/heads/fw/dl-bind-performance X-Git-Oldrev: 0e5a24f5a968c0f791ea5e6625ad41a27c82cce6 X-Git-Newrev: 0fa7402cbb4c88ab230eb4447f3fc2a182b17ae7 Message-Id: <20220411140701.8CCD63854D9E@sourceware.org> Date: Mon, 11 Apr 2022 14:07:01 +0000 (GMT) X-BeenThere: glibc-cvs@sourceware.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Glibc-cvs mailing list List-Unsubscribe: , List-Archive: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 11 Apr 2022 14:07:01 -0000 https://sourceware.org/git/gitweb.cgi?p=glibc.git;h=0fa7402cbb4c88ab230eb4447f3fc2a182b17ae7 commit 0fa7402cbb4c88ab230eb4447f3fc2a182b17ae7 Author: Florian Weimer 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 #include #include +#include #include @@ -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;