From mboxrd@z Thu Jan 1 00:00:00 1970 X-Msuck: nntp://news.gmane.org/gmane.linux.lib.musl.general/8010 Path: news.gmane.org!not-for-mail From: Alexander Monakov 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 09:29:25 +0300 (MSK) Message-ID: References: <1435101895-18240-1-git-send-email-amonakov@ispras.ru> <1435101895-18240-2-git-send-email-amonakov@ispras.ru> <20150624053906.GQ1173@brightrain.aerifal.cx> 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 1435127386 8268 80.91.229.3 (24 Jun 2015 06:29:46 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Wed, 24 Jun 2015 06:29:46 +0000 (UTC) To: musl@lists.openwall.com Original-X-From: musl-return-8023-gllmg-musl=m.gmane.org@lists.openwall.com Wed Jun 24 08:29:39 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 1Z7eBm-0001WC-KE for gllmg-musl@m.gmane.org; Wed, 24 Jun 2015 08:29:38 +0200 Original-Received: (qmail 23796 invoked by uid 550); 24 Jun 2015 06:29:37 -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 23777 invoked from network); 24 Jun 2015 06:29:37 -0000 In-Reply-To: <20150624053906.GQ1173@brightrain.aerifal.cx> User-Agent: Alpine 2.11 (LNX 23 2013-08-11) Xref: news.gmane.org gmane.linux.lib.musl.general:8010 Archived-At: > > 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 ? It seems to give a small improvement for me, but with the other patches, too small to measure reliably. As I'm using a big testcase, the impact on typical libraries should be really tiny. > 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. I wanted it to be nearby the hashtab pointer, which needs to be loaded anyway. If ghashmask needs to move so that loading it will access a different cache line, it's likely to diminish an already small improvement, at which point it's easier to drop this patch :) Would be nice if someone could test on a platform with slower caches. Alexander