From mboxrd@z Thu Jan 1 00:00:00 1970 X-Msuck: nntp://news.gmane.org/gmane.linux.lib.musl.general/8013 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 02:50:05 -0400 Message-ID: <20150624065005.GS1173@brightrain.aerifal.cx> 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 1435128636 26767 80.91.229.3 (24 Jun 2015 06:50:36 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Wed, 24 Jun 2015 06:50:36 +0000 (UTC) To: musl@lists.openwall.com Original-X-From: musl-return-8026-gllmg-musl=m.gmane.org@lists.openwall.com Wed Jun 24 08:50:29 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 1Z7eVq-00079y-3A for gllmg-musl@m.gmane.org; Wed, 24 Jun 2015 08:50:22 +0200 Original-Received: (qmail 5143 invoked by uid 550); 24 Jun 2015 06:50: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 4092 invoked from network); 24 Jun 2015 06:50:18 -0000 Content-Disposition: inline In-Reply-To: User-Agent: Mutt/1.5.21 (2010-09-15) Original-Sender: Rich Felker Xref: news.gmane.org gmane.linux.lib.musl.general:8013 Archived-At: On Wed, Jun 24, 2015 at 09:29:25AM +0300, Alexander Monakov wrote: > > > 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 :) Well we could just reorder some things to put them adjacent to one another without wasting the padding, if it helps. I don't want to reject this part outright, but I think changes like this that obviously have some cost and where the benefit is non-obvious should have some strong justification. (The umod stuff obviously has some size cost too in struct dso, but its benefit is a lot more clear, especially on archs without hardware div.) Maybe it would make sense to omit the ghashmask part to begin with (it makes the patch smaller anyway) and then do some testing to see whether it's really beneficial once the other things are merged and we have a stable basis for performance comparison. Rich