Re: hashinit(): power of 2 fast path
On Sun, Apr 29, 2018 at 10:52:27AM +0200, Mathieu - wrote:
> Disregard that, brainfart on my side.
>
> Mathieu - wrote:
> > Anton Lindqvist wrote:
> > > Hi,
> > > If the elements argument passed to hashinit() is a power of 2 there's no
> > > need to find the closest power of 2 that can fit all elements since
> > > elements == hashsize will always be true. During boot of a stock amd64
> > > kernel running inside vmd 80% of the calls to hashinit() includes a
> > > power of 2 size.
> > >
> > > Comments? OK?
> >
> >
> > Hi,
> >
> > Dunno how much a win it is. But anyhow this will blow in hashfree as
> > hashsize won't be the same.
> >
> >
> > Mathieu.
> >
> >
> >
> > >
> > > Index: kern/kern_subr.c
> > > ===
> > > RCS file: /cvs/src/sys/kern/kern_subr.c,v
> > > retrieving revision 1.49
> > > diff -u -p -r1.49 kern_subr.c
> > > --- kern/kern_subr.c 14 Feb 2017 10:31:15 - 1.49
> > > +++ kern/kern_subr.c 28 Apr 2018 20:21:40 -
> > > @@ -163,8 +163,11 @@ hashinit(int elements, int type, int fla
> > >
> > > if (elements <= 0)
> > > panic("hashinit: bad cnt");
> > > - for (hashsize = 1; hashsize < elements; hashsize <<= 1)
> > > - continue;
> > > + if ((elements & (elements - 1)) == 0)
> > > + hashsize = elements;
> > > + else
> > > + for (hashsize = 1; hashsize < elements; hashsize <<= 1)
> > > + continue;
> > > hashtbl = mallocarray(hashsize, sizeof(*hashtbl), type, flags);
> > > if (hashtbl == NULL)
> > > return NULL;
> > >
> >
But the same logic could also be applied in hashfree() with the same
reasoning as in hashinit() still being valid.
OK?
Index: kern/kern_subr.c
===
RCS file: /cvs/src/sys/kern/kern_subr.c,v
retrieving revision 1.49
diff -u -p -r1.49 kern_subr.c
--- kern/kern_subr.c14 Feb 2017 10:31:15 - 1.49
+++ kern/kern_subr.c29 Apr 2018 09:21:26 -
@@ -163,8 +163,11 @@ hashinit(int elements, int type, int fla
if (elements <= 0)
panic("hashinit: bad cnt");
- for (hashsize = 1; hashsize < elements; hashsize <<= 1)
- continue;
+ if ((elements & (elements - 1)) == 0)
+ hashsize = elements;
+ else
+ for (hashsize = 1; hashsize < elements; hashsize <<= 1)
+ continue;
hashtbl = mallocarray(hashsize, sizeof(*hashtbl), type, flags);
if (hashtbl == NULL)
return NULL;
@@ -182,8 +185,11 @@ hashfree(void *hash, int elements, int t
if (elements <= 0)
panic("hashfree: bad cnt");
- for (hashsize = 1; hashsize < elements; hashsize <<= 1)
- continue;
+ if ((elements & (elements - 1)) == 0)
+ hashsize = elements;
+ else
+ for (hashsize = 1; hashsize < elements; hashsize <<= 1)
+ continue;
free(hashtbl, type, sizeof(*hashtbl) * hashsize);
}
Re: hashinit(): power of 2 fast path
Disregard that, brainfart on my side.
Mathieu - wrote:
> Anton Lindqvist wrote:
> > Hi,
> > If the elements argument passed to hashinit() is a power of 2 there's no
> > need to find the closest power of 2 that can fit all elements since
> > elements == hashsize will always be true. During boot of a stock amd64
> > kernel running inside vmd 80% of the calls to hashinit() includes a
> > power of 2 size.
> >
> > Comments? OK?
>
>
> Hi,
>
> Dunno how much a win it is. But anyhow this will blow in hashfree as
> hashsize won't be the same.
>
>
> Mathieu.
>
>
>
> >
> > Index: kern/kern_subr.c
> > ===
> > RCS file: /cvs/src/sys/kern/kern_subr.c,v
> > retrieving revision 1.49
> > diff -u -p -r1.49 kern_subr.c
> > --- kern/kern_subr.c14 Feb 2017 10:31:15 - 1.49
> > +++ kern/kern_subr.c28 Apr 2018 20:21:40 -
> > @@ -163,8 +163,11 @@ hashinit(int elements, int type, int fla
> >
> > if (elements <= 0)
> > panic("hashinit: bad cnt");
> > - for (hashsize = 1; hashsize < elements; hashsize <<= 1)
> > - continue;
> > + if ((elements & (elements - 1)) == 0)
> > + hashsize = elements;
> > + else
> > + for (hashsize = 1; hashsize < elements; hashsize <<= 1)
> > + continue;
> > hashtbl = mallocarray(hashsize, sizeof(*hashtbl), type, flags);
> > if (hashtbl == NULL)
> > return NULL;
> >
>
Re: hashinit(): power of 2 fast path
Anton Lindqvist wrote:
> Hi,
> If the elements argument passed to hashinit() is a power of 2 there's no
> need to find the closest power of 2 that can fit all elements since
> elements == hashsize will always be true. During boot of a stock amd64
> kernel running inside vmd 80% of the calls to hashinit() includes a
> power of 2 size.
>
> Comments? OK?
Hi,
Dunno how much a win it is. But anyhow this will blow in hashfree as
hashsize won't be the same.
Mathieu.
>
> Index: kern/kern_subr.c
> ===
> RCS file: /cvs/src/sys/kern/kern_subr.c,v
> retrieving revision 1.49
> diff -u -p -r1.49 kern_subr.c
> --- kern/kern_subr.c 14 Feb 2017 10:31:15 - 1.49
> +++ kern/kern_subr.c 28 Apr 2018 20:21:40 -
> @@ -163,8 +163,11 @@ hashinit(int elements, int type, int fla
>
> if (elements <= 0)
> panic("hashinit: bad cnt");
> - for (hashsize = 1; hashsize < elements; hashsize <<= 1)
> - continue;
> + if ((elements & (elements - 1)) == 0)
> + hashsize = elements;
> + else
> + for (hashsize = 1; hashsize < elements; hashsize <<= 1)
> + continue;
> hashtbl = mallocarray(hashsize, sizeof(*hashtbl), type, flags);
> if (hashtbl == NULL)
> return NULL;
>
hashinit(): power of 2 fast path
Hi,
If the elements argument passed to hashinit() is a power of 2 there's no
need to find the closest power of 2 that can fit all elements since
elements == hashsize will always be true. During boot of a stock amd64
kernel running inside vmd 80% of the calls to hashinit() includes a
power of 2 size.
Comments? OK?
Index: kern/kern_subr.c
===
RCS file: /cvs/src/sys/kern/kern_subr.c,v
retrieving revision 1.49
diff -u -p -r1.49 kern_subr.c
--- kern/kern_subr.c14 Feb 2017 10:31:15 - 1.49
+++ kern/kern_subr.c28 Apr 2018 20:21:40 -
@@ -163,8 +163,11 @@ hashinit(int elements, int type, int fla
if (elements <= 0)
panic("hashinit: bad cnt");
- for (hashsize = 1; hashsize < elements; hashsize <<= 1)
- continue;
+ if ((elements & (elements - 1)) == 0)
+ hashsize = elements;
+ else
+ for (hashsize = 1; hashsize < elements; hashsize <<= 1)
+ continue;
hashtbl = mallocarray(hashsize, sizeof(*hashtbl), type, flags);
if (hashtbl == NULL)
return NULL;
