A boolean single_bit_set() routine would simplify the numerous
constructs of the form (((n & (n - 1)) == 0)) when testing for
single-bitness.
Signed-off-by: Robert P. J. Day <[email protected]>
---
This is similar to the current is_power_of_2() routine defined in
include/linux/log2.h, which is mathematically identical but,
semantically, should be defined independently just so the code is more
readable.
I'm open to an alternative function name.
diff --git a/include/linux/bitops.h b/include/linux/bitops.h
index 6182913..1c0c840 100644
--- a/include/linux/bitops.h
+++ b/include/linux/bitops.h
@@ -45,6 +45,13 @@ static inline unsigned long hweight_long(unsigned long w)
return sizeof(w) == 4 ? hweight32(w) : hweight64(w);
}
+static inline __attribute__((const))
+bool single_bit_set(unsigned long n)
+{
+ return (n != 0 && ((n & (n - 1)) == 0));
+}
+
+
/**
* rol32 - rotate a 32-bit value left
* @word: value to rotate
========================================================================
Robert P. J. Day Waterloo, Ontario, CANADA
Linux Consulting, Training and Annoying Kernel Pedantry.
Web page: http://crashcourse.ca
Linked In: http://www.linkedin.com/in/rpjday
Twitter: http://twitter.com/rpjday
========================================================================
Robert P. J. Day wrote:
> A boolean single_bit_set() routine would simplify the numerous
> constructs of the form (((n & (n - 1)) == 0)) when testing for
> single-bitness.
>
> Signed-off-by: Robert P. J. Day <[email protected]>
>
> ---
>
> This is similar to the current is_power_of_2() routine defined in
> include/linux/log2.h, which is mathematically identical but,
> semantically, should be defined independently just so the code is more
> readable.
>
> I'm open to an alternative function name.
>
> diff --git a/include/linux/bitops.h b/include/linux/bitops.h
> index 6182913..1c0c840 100644
> --- a/include/linux/bitops.h
> +++ b/include/linux/bitops.h
> @@ -45,6 +45,13 @@ static inline unsigned long hweight_long(unsigned long w)
> return sizeof(w) == 4 ? hweight32(w) : hweight64(w);
> }
>
> +static inline __attribute__((const))
> +bool single_bit_set(unsigned long n)
> +{
> + return (n != 0 && ((n & (n - 1)) == 0));
> +}
> +
> +
It would be nice to be able to override this per architecture.
For example a more efficient implementation on CPUs that have a
population count instruction (__builtin_popcountl()) might be:
static inline __attribute__((const))
bool singe_bit_set(unsigned long n)
{
return __builtin_popcountl(n) == 1;
}
Also, are we still putting 'inline' everywhere?
David Daney
On Thu, 23 Apr 2009, David Daney wrote:
> Robert P. J. Day wrote:
> > A boolean single_bit_set() routine would simplify the numerous
> > constructs of the form (((n & (n - 1)) == 0)) when testing for
> > single-bitness.
> >
> > Signed-off-by: Robert P. J. Day <[email protected]>
> >
> > ---
> >
> > This is similar to the current is_power_of_2() routine defined in
> > include/linux/log2.h, which is mathematically identical but,
> > semantically, should be defined independently just so the code is more
> > readable.
> >
> > I'm open to an alternative function name.
> >
> > diff --git a/include/linux/bitops.h b/include/linux/bitops.h
> > index 6182913..1c0c840 100644
> > --- a/include/linux/bitops.h
> > +++ b/include/linux/bitops.h
> > @@ -45,6 +45,13 @@ static inline unsigned long hweight_long(unsigned long w)
> > return sizeof(w) == 4 ? hweight32(w) : hweight64(w);
> > }
> >
> > +static inline __attribute__((const))
> > +bool single_bit_set(unsigned long n)
> > +{
> > + return (n != 0 && ((n & (n - 1)) == 0));
> > +}
> > +
> > +
>
>
> It would be nice to be able to override this per architecture.
sure, that makes sense. but in the meantime, there's nothing to
keep from starting the process and, arch by arch, overriding it down
the road as it becomes convenient.
> Also, are we still putting 'inline' everywhere?
beats me. are we? and, just to be definitively pedantic about
this, for maximum readability, i think it would be nice to define
*both* the function and its converse:
if (exactly_one_bit_set())
if (more_than_one_bit_set())
or something to that effect. i'll leave the final naming decisions up
to others higher up the food chain.
rday
p.s. you can see the potential simplification by running, at the top
of the kernel tree:
$ grep -Ern "([^\(\)]+) ?\& ?\(\1 ?- ?1\)" .
some of those represent power of 2 semantics, while others are the
single bit thingy. and others are just weird.
========================================================================
Robert P. J. Day Waterloo, Ontario, CANADA
Linux Consulting, Training and Annoying Kernel Pedantry.
Web page: http://crashcourse.ca
Linked In: http://www.linkedin.com/in/rpjday
Twitter: http://twitter.com/rpjday
========================================================================
On Thu, 23 Apr 2009 12:57:11 -0700
David Daney <[email protected]> wrote:
> > +static inline __attribute__((const))
> > +bool single_bit_set(unsigned long n)
> > +{
> > + return (n != 0 && ((n & (n - 1)) == 0));
> > +}
> > +
> > +
>
>
> It would be nice to be able to override this per architecture.
>
> For example a more efficient implementation on CPUs that have a
> population count instruction (__builtin_popcountl()) might be:
>
> static inline __attribute__((const))
> bool singe_bit_set(unsigned long n)
> {
> return __builtin_popcountl(n) == 1;
> }
Already done, via hweight_long().
On Thu, 23 Apr 2009, Andrew Morton wrote:
> On Thu, 23 Apr 2009 12:57:11 -0700
> David Daney <[email protected]> wrote:
>
> > > +static inline __attribute__((const))
> > > +bool single_bit_set(unsigned long n)
> > > +{
> > > + return (n != 0 && ((n & (n - 1)) == 0));
> > > +}
> > > +
> > > +
> >
> >
> > It would be nice to be able to override this per architecture.
> >
> > For example a more efficient implementation on CPUs that have a
> > population count instruction (__builtin_popcountl()) might be:
> >
> > static inline __attribute__((const))
> > bool singe_bit_set(unsigned long n)
> > {
> > return __builtin_popcountl(n) == 1;
> > }
>
> Already done, via hweight_long().
so it would be a simple matter to define the bit set boolean in
terms of hweight_long(), yes? so what about, in bitops.h:
static inline bool
exactly_one_bit_set(unsigned long w)
{
return hweight_long(w) == 1;
}
static inline bool
more_than_one_bit_set(unsigned long w)
{
return hweight_long(w) > 1;
}
or something to that effect, *if* people think it's worth it.
obviously, none of the above is strictly necessary, but it would make
a lot of code semantically cleaner.
rday
p.s. i notice that, even in a single header file like bitops.h, there
is a mixture of both "inline" and "__inline__". what's the
recommended choice these days?
--
========================================================================
Robert P. J. Day Waterloo, Ontario, CANADA
Linux Consulting, Training and Annoying Kernel Pedantry.
Web page: http://crashcourse.ca
Linked In: http://www.linkedin.com/in/rpjday
Twitter: http://twitter.com/rpjday
========================================================================
On Thu, 23 Apr 2009, Andrew Morton wrote:
> On Thu, 23 Apr 2009 12:57:11 -0700
> David Daney <[email protected]> wrote:
>
> > > +static inline __attribute__((const))
> > > +bool single_bit_set(unsigned long n)
> > > +{
> > > + return (n != 0 && ((n & (n - 1)) == 0));
> > > +}
> > > +
> > > +
> >
> >
> > It would be nice to be able to override this per architecture.
> >
> > For example a more efficient implementation on CPUs that have a
> > population count instruction (__builtin_popcountl()) might be:
> >
> > static inline __attribute__((const))
> > bool singe_bit_set(unsigned long n)
> > {
> > return __builtin_popcountl(n) == 1;
> > }
>
> Already done, via hweight_long().
i'm guessing that taking advantage of helper functions like that
might simplify code like, say, this from fs/nfs/internal.h:
/*
* Determine the actual block size (and log2 thereof)
*/
static inline
unsigned long nfs_block_bits(unsigned long bsize, unsigned char *nrbitsp)
{
/* make sure blocksize is a power of two */
if ((bsize & (bsize - 1)) || nrbitsp) {
unsigned char nrbits;
for (nrbits = 31; nrbits && !(bsize & (1 << nrbits)); nrbits--)
;
bsize = 1 << nrbits;
if (nrbitsp)
*nrbitsp = nrbits;
}
return bsize;
}
surely, there's a simpler way to write that.
rday
--
========================================================================
Robert P. J. Day Waterloo, Ontario, CANADA
Linux Consulting, Training and Annoying Kernel Pedantry.
Web page: http://crashcourse.ca
Linked In: http://www.linkedin.com/in/rpjday
Twitter: http://twitter.com/rpjday
========================================================================
On Fri, 24 Apr 2009 06:40:39 -0400 (EDT) "Robert P. J. Day" <[email protected]> wrote:
> so it would be a simple matter to define the bit set boolean in
> terms of hweight_long(), yes? so what about, in bitops.h:
>
> static inline bool
> exactly_one_bit_set(unsigned long w)
> {
> return hweight_long(w) == 1;
> }
>
> static inline bool
> more_than_one_bit_set(unsigned long w)
> {
> return hweight_long(w) > 1;
> }
>
> or something to that effect, *if* people think it's worth it.
> obviously, none of the above is strictly necessary, but it would make
> a lot of code semantically cleaner.
>
Doing plain old
if (hweight32(foo) == 1)
(say) at the call sites quite clearly expresses what the code is trying
to do.
> rday
>
> p.s. i notice that, even in a single header file like bitops.h, there
> is a mixture of both "inline" and "__inline__". what's the
> recommended choice these days?
`inline'. Or uninline the function ;)
On Fri, 24 Apr 2009, Andrew Morton wrote:
> On Fri, 24 Apr 2009 06:40:39 -0400 (EDT) "Robert P. J. Day" <[email protected]> wrote:
>
> > so it would be a simple matter to define the bit set boolean in
> > terms of hweight_long(), yes? so what about, in bitops.h:
> >
> > static inline bool
> > exactly_one_bit_set(unsigned long w)
> > {
> > return hweight_long(w) == 1;
> > }
> >
> > static inline bool
> > more_than_one_bit_set(unsigned long w)
> > {
> > return hweight_long(w) > 1;
> > }
> >
> > or something to that effect, *if* people think it's worth it.
> > obviously, none of the above is strictly necessary, but it would make
> > a lot of code semantically cleaner.
> >
>
> Doing plain old
>
> if (hweight32(foo) == 1)
>
> (say) at the call sites quite clearly expresses what the code is trying
> to do.
yes, that seems reasonable. but would you really prefer "hweight32"
over "hweight_long"?
rday
--
========================================================================
Robert P. J. Day Waterloo, Ontario, CANADA
Linux Consulting, Training and Annoying Kernel Pedantry.
Web page: http://crashcourse.ca
Linked In: http://www.linkedin.com/in/rpjday
Twitter: http://twitter.com/rpjday
========================================================================
Andrew Morton píše v Pá 24. 04. 2009 v 10:46 -0700:
> On Fri, 24 Apr 2009 06:40:39 -0400 (EDT) "Robert P. J. Day" <[email protected]> wrote:
>
> > so it would be a simple matter to define the bit set boolean in
> > terms of hweight_long(), yes? so what about, in bitops.h:
> >
> > static inline bool
> > exactly_one_bit_set(unsigned long w)
> > {
> > return hweight_long(w) == 1;
> > }
> >
> > static inline bool
> > more_than_one_bit_set(unsigned long w)
> > {
> > return hweight_long(w) > 1;
> > }
> >
Andrew, you must be kidding! Are you seriously suggesting to replace a
simple and instruction with a call to an extern library function with 17
instructions (not including the call and ret)?
I'd better check the use of hweight in the kernel to eradicate as many
calls to it as possible...
Petr Tesarik
Petr Tesarik wrote:
>
> Ok, then my only concern is that the hweight* functions return the exact
> weight, which might be much less efficient if all we need is to know
> whether it's 1.
>
> Theoretically, gcc should be able to optimize things out, but I'm not
> all that optimistic about how well it does it.
>
I can almost guarantee it won't in this case.
-hpa
On Mon, 29 Jun 2009, Petr Tesarik wrote:
> Andrew Morton píše v Pá 24. 04. 2009 v 10:46 -0700:
> > On Fri, 24 Apr 2009 06:40:39 -0400 (EDT) "Robert P. J. Day" <[email protected]> wrote:
> >
> > > so it would be a simple matter to define the bit set boolean in
> > > terms of hweight_long(), yes? so what about, in bitops.h:
> > >
> > > static inline bool
> > > exactly_one_bit_set(unsigned long w)
> > > {
> > > return hweight_long(w) == 1;
> > > }
> > >
> > > static inline bool
> > > more_than_one_bit_set(unsigned long w)
> > > {
> > > return hweight_long(w) > 1;
> > > }
> > >
>
> Andrew, you must be kidding! Are you seriously suggesting to replace
> a simple and instruction with a call to an extern library function
> with 17 instructions (not including the call and ret)?
>
> I'd better check the use of hweight in the kernel to eradicate as
> many calls to it as possible...
since i originally muttered about this, the rationale behind it was
not for performance (obviously), but for semantic clarification, so
that when you saw the expression "n & (n-1)", it was more obvious
which test you were doing semantically:
1) is n a power of 2?
2) does n represent a single set bit?
nothing ever came of that, but that was the thinking behind it.
rday
--
========================================================================
Robert P. J. Day Waterloo, Ontario, CANADA
Linux Consulting, Training and Annoying Kernel Pedantry.
Web page: http://crashcourse.ca
Linked In: http://www.linkedin.com/in/rpjday
Twitter: http://twitter.com/rpjday
========================================================================
Robert P. J. Day píše v Po 29. 06. 2009 v 14:50 -0400:
> On Mon, 29 Jun 2009, Petr Tesarik wrote:
>
> > Andrew Morton píše v Pá 24. 04. 2009 v 10:46 -0700:
> > > On Fri, 24 Apr 2009 06:40:39 -0400 (EDT) "Robert P. J. Day" <[email protected]> wrote:
> > >
> > > > so it would be a simple matter to define the bit set boolean in
> > > > terms of hweight_long(), yes? so what about, in bitops.h:
> > > >
> > > > static inline bool
> > > > exactly_one_bit_set(unsigned long w)
> > > > {
> > > > return hweight_long(w) == 1;
> > > > }
> > > >
> > > > static inline bool
> > > > more_than_one_bit_set(unsigned long w)
> > > > {
> > > > return hweight_long(w) > 1;
> > > > }
> > > >
> >
> > Andrew, you must be kidding! Are you seriously suggesting to replace
> > a simple and instruction with a call to an extern library function
> > with 17 instructions (not including the call and ret)?
> >
> > I'd better check the use of hweight in the kernel to eradicate as
> > many calls to it as possible...
>
> since i originally muttered about this, the rationale behind it was
> not for performance (obviously), but for semantic clarification, so
> that when you saw the expression "n & (n-1)", it was more obvious
> which test you were doing semantically:
>
> 1) is n a power of 2?
> 2) does n represent a single set bit?
>
> nothing ever came of that, but that was the thinking behind it.
Yes, I can remember and I would still appreciate it. It's always better
to show _what_ the code does rather than _how_ it does it.
IIRC Andrew rejected your patch on the grounds that it is possible to
replace the expression "n & (n-1)" with "hweight(n) == 1" if one wants
to show that it really tests for a single bit set. But I don't like his
proposal quite as much as yours, because of the big overhead.
In short, if you re-post your patch, I'll gladly join you in the battle
of getting it in. ;-)
Petr Tesarik
On Tue, 30 Jun 2009, Petr Tesarik wrote:
> Robert P. J. Day píše v Po 29. 06. 2009 v 14:50 -0400:
> > since i originally muttered about this, the rationale behind it
> > was not for performance (obviously), but for semantic
> > clarification, so that when you saw the expression "n & (n-1)", it
> > was more obvious which test you were doing semantically:
> >
> > 1) is n a power of 2?
> > 2) does n represent a single set bit?
> >
> > nothing ever came of that, but that was the thinking behind it.
>
> Yes, I can remember and I would still appreciate it. It's always
> better to show _what_ the code does rather than _how_ it does it.
>
> IIRC Andrew rejected your patch on the grounds that it is possible
> to replace the expression "n & (n-1)" with "hweight(n) == 1" if one
> wants to show that it really tests for a single bit set. But I don't
> like his proposal quite as much as yours, because of the big
> overhead.
>
> In short, if you re-post your patch, I'll gladly join you in the
> battle of getting it in. ;-)
i never meant for this to turn into a pitched battle of
philosophies -- it just seemed like a simple way to make the code
clearer, particularly since some of the patches i've submitted allowed
for the removal of comments like "test that blocksize is a power of
2" given that what you're testing is now painfully obvious. :-)
if someone has a quick, simple and performance non-crippling
suggestion for this, i'm all ears. but there's no point thinking
about it if it's actually going to cause performance issues.
rday
p.s. a simple grep to find potential cleanup of the form n&(n-1):
grep -Ern "([^\(\)]+) ?\& ?\(\1 ?- ?1\)" * | less
--
========================================================================
Robert P. J. Day Waterloo, Ontario, CANADA
Linux Consulting, Training and Annoying Kernel Pedantry.
Web page: http://crashcourse.ca
Linked In: http://www.linkedin.com/in/rpjday
Twitter: http://twitter.com/rpjday
========================================================================