From mboxrd@z Thu Jan 1 00:00:00 1970 X-Msuck: nntp://news.gmane.org/gmane.linux.lib.musl.general/8008 Path: news.gmane.org!not-for-mail From: Rich Felker Newsgroups: gmane.linux.lib.musl.general Subject: Re: [PATCH 1/5] dynlink.c: use bloom filter in gnu hash lookup Date: Wed, 24 Jun 2015 01:39:06 -0400 Message-ID: <20150624053906.GQ1173@brightrain.aerifal.cx> References: <1435101895-18240-1-git-send-email-amonakov@ispras.ru> <1435101895-18240-2-git-send-email-amonakov@ispras.ru> Reply-To: musl@lists.openwall.com NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Trace: ger.gmane.org 1435124362 26699 80.91.229.3 (24 Jun 2015 05:39:22 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Wed, 24 Jun 2015 05:39:22 +0000 (UTC) To: musl@lists.openwall.com Original-X-From: musl-return-8021-gllmg-musl=m.gmane.org@lists.openwall.com Wed Jun 24 07:39:21 2015 Return-path: Envelope-to: gllmg-musl@m.gmane.org Original-Received: from mother.openwall.net ([195.42.179.200]) by plane.gmane.org with smtp (Exim 4.69) (envelope-from ) id 1Z7dP6-0005ZP-C4 for gllmg-musl@m.gmane.org; Wed, 24 Jun 2015 07:39:20 +0200 Original-Received: (qmail 23805 invoked by uid 550); 24 Jun 2015 05:39:19 -0000 Mailing-List: contact musl-help@lists.openwall.com; run by ezmlm Precedence: bulk List-Post: List-Help: List-Unsubscribe: List-Subscribe: Original-Received: (qmail 23783 invoked from network); 24 Jun 2015 05:39:18 -0000 Content-Disposition: inline In-Reply-To: <1435101895-18240-2-git-send-email-amonakov@ispras.ru> User-Agent: Mutt/1.5.21 (2010-09-15) Original-Sender: Rich Felker Xref: news.gmane.org gmane.linux.lib.musl.general:8008 Archived-At: On Wed, Jun 24, 2015 at 02:24:51AM +0300, Alexander Monakov wrote: > Introduce gnu_lookup_filtered and use it to speed up symbol lookups in > find_sym (do_dlsym is left as is, based on an expectation that frequently > dlsym queries will use a dlopen handle rather than RTLD_NEXT or RTLD_DEFAULT, > and will not need to look at more than one DSO). The size of the bloom filter > table minus 1, ghashmask, is stored in the dso struct together with the > hashtable pointer to reduce pointer chasing on the hot path. > --- > src/ldso/dynlink.c | 30 ++++++++++++++++++++++++++---- > 1 file changed, 26 insertions(+), 4 deletions(-) > > diff --git a/src/ldso/dynlink.c b/src/ldso/dynlink.c > index b77c6f6..fa91b39 100644 > --- a/src/ldso/dynlink.c > +++ b/src/ldso/dynlink.c > @@ -54,6 +54,7 @@ struct dso { > Sym *syms; > uint32_t *hashtab; > uint32_t *ghashtab; > + uint32_t ghashmask; > int16_t *versym; > char *strings; > unsigned char *map; > @@ -200,6 +201,19 @@ static Sym *gnu_lookup(const char *s, uint32_t h1, struct dso *dso) > return 0; > } > > +static Sym *gnu_lookup_filtered(const char *s, uint32_t h1, struct dso *dso, uint32_t fofs, size_t fmask) > +{ > + uint32_t *hashtab = dso->ghashtab; > + size_t *bloomwords = hashtab+4; > + size_t f = bloomwords[fofs & dso->ghashmask]; Is this measurably faster than fofs & hashtab[2]-1 ? If suspect not, in which case it seems desirable not to increase the size of struct dso. If it is worthwhile, at least don't sandwich a uint32_t between two pointers where it might incur another 32 bits of padding. Rich