[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date: Wed, 24 Jun 2015 02:50:05 -0400
From: Rich Felker <dalias@...c.org>
To: musl@...ts.openwall.com
Subject: Re: [PATCH 1/5] dynlink.c: use bloom filter in gnu hash lookup
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
Powered by blists - more mailing lists
Confused about mailing lists and their use?
Read about mailing lists on Wikipedia
and check out these
guidelines on proper formatting of your messages.
