Introduce a boolean "single_bit_set" function.
PATCH 1/1 Introduce a boolean "single_bit_set" function.
A boolean single_bit_set() routine would simplify the numerous constructs of the form (((n & (n - 1)) == 0)) when testing for single-bitness.
---
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.
include/linux/bitops.h +7 -0
@@ -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
========================================================================
Quoted 20 lines · Robert P. J. Day
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 ininclude/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.
include/linux/bitops.h +0
-0
include/linux/bitops.h static inline unsigned long hweight_long(unsigned long w) · line 54
Quoted 10 lines
include/linux/bitops.h +7
-0@@ -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
Quoted 24 lines · David Daney
Quoted 23 lines · Robert P. J. Day
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 ininclude/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.
include/linux/bitops.h +0
-0@@ -45,6 +45,13 @@ static inline unsigned long hweight_long(unsigned long w)return sizeof (w) ==4 ?hweight32 (w) :hweight64 (w); }
Quoted 10 lines
include/linux/bitops.h static inline unsigned long hweight_long(unsigned long w) · line 54
Quoted 7 lines
include/linux/bitops.h +7
-0+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.
Quoted 1 line
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
========================================================================
Quoted 11 lines · On Thu, 23 Apr 2009 12:57:11 -0700 David Daney <[email protected]>…
include/linux/bitops.h static inline unsigned long hweight_long(unsigned long w) · line 54
Quoted 7 lines
include/linux/bitops.h +7
-0+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.
Quoted 8 lines
For example a more efficient implementation on CPUs that have a population count instruction (
__builtin_popcountl()) might be:static inline __attribute__((const))
boolsinge_bit_set(unsigned long n){ return __builtin_popcountl(n) == 1; }
Already done, via hweight_long().
Quoted 17 lines · Andrew Morton
Quoted 14 lines · On Thu, 23 Apr 2009 12:57:11 -0700 David Daney <[email protected]>…
include/linux/bitops.h static inline unsigned long hweight_long(unsigned long w) · line 54
Quoted 7 lines
include/linux/bitops.h +7
-0+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:
Quoted 7 lines
Quoted 5 lines
static inline __attribute__((const))
boolsinge_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
========================================================================
Quoted 11 lines · On Fri, 24 Apr 2009 06:40:39 -0400 (EDT) "Robert P. J. Day"…
so it would be a simple matter to define the bit set boolean in
terms ofhweight_long(), yes? so what about, inbitops.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)
Quoted 8 lines
{ 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.
Quoted 5 lines
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 ;)
Quoted 22 lines · Andrew Morton
Quoted 11 lines · On Fri, 24 Apr 2009 06:40:39 -0400 (EDT) "Robert P. J. Day"…
so it would be a simple matter to define the bit set boolean in
terms ofhweight_long(), yes? so what about, inbitops.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)Quoted 8 lines
{ 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.
Quoted 6 lines
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:
Quoted 11 lines · On Fri, 24 Apr 2009 06:40:39 -0400 (EDT) "Robert P. J. Day"…
Quoted 10 lines
so it would be a simple matter to define the bit set boolean in
terms ofhweight_long(), yes? so what about, inbitops.h:static inline bool
exactly_one_bit_set(unsigned long w){ return hweight_long(w) == 1;}
Quoted 6 lines
Quoted 6 lines
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
Quoted 19 lines · Petr Tesarik
Andrew Morton píše v Pá 24. 04. 2009 v 10:46 -0700:
Quoted 11 lines · On Fri, 24 Apr 2009 06:40:39 -0400 (EDT) "Robert P. J. Day"…
Quoted 10 lines
so it would be a simple matter to define the bit set boolean in
terms ofhweight_long(), yes? so what about, inbitops.h:static inline bool
exactly_one_bit_set(unsigned long w){ return hweight_long(w) == 1;}
Quoted 6 lines
Quoted 6 lines
static inline bool
more_than_one_bit_set(unsigned long w){ return hweight_long(w) > 1;}
Quoted 6 lines
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:
Quoted 33 lines · Petr Tesarik
Quoted 20 lines
Andrew Morton píše v Pá 24. 04. 2009 v 10:46 -0700:
Quoted 11 lines · On Fri, 24 Apr 2009 06:40:39 -0400 (EDT) "Robert P. J. Day"…
Quoted 10 lines
so it would be a simple matter to define the bit set boolean in
terms ofhweight_long(), yes? so what about, inbitops.h:static inline bool
exactly_one_bit_set(unsigned long w){ return hweight_long(w) == 1;}
Quoted 6 lines
Quoted 6 lines
static inline bool
more_than_one_bit_set(unsigned long w){ return hweight_long(w) > 1;}
Quoted 6 lines
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:
Quoted 4 lines
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
Quoted 15 lines · Petr Tesarik
Robert P. J. Day píše v Po 29. 06. 2009 v 14:50 -0400:
Quoted 9 lines
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.
Quoted 8 lines
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
========================================================================
Quoted 17 lines · Andrew Morton
Quoted 14 lines · On Thu, 23 Apr 2009 12:57:11 -0700 David Daney <[email protected]>…
include/linux/bitops.h static inline unsigned long hweight_long(unsigned long w) · line 54
Quoted 7 lines
include/linux/bitops.h +7
-0+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:
Quoted 7 lines
Quoted 5 lines
static inline __attribute__((const))
boolsinge_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
========================================================================
Robert P. J. Day píše v Čt 23. 04. 2009 v 13:43 -0400:
Quoted 6 lines
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]>
Quoted 8 lines
---
This is similar to the current
is_power_of_2()routine defined ininclude/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.
ispow2() ?
Because what it really does is to check that a value is a power of two, doesn'it.
Regards,
Petr Tesarik
P.S. aka I want my bikeshed mathematical!
Quoted 14 lines · Petr Tesarik
Robert P. J. Day píše v Čt 23. 04. 2009 v 13:43 -0400:
Quoted 13 lines
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 ininclude/linux/log2.h, which is mathematically identical but, semantically, should be defined independently just so the code is more readable.
Quoted 6 lines
Quoted 1 line
I'm open to an alternative function name.
ispow2()?Because what it really does is to check that a value is a power of two, doesn'it.
yes, mathematically it's identical, but *semantically*, i think it's
worth distinguishing between those two tests. there's still a number of places in the code that can be rewritten with "is power of 2" tests, but that rewriting makes sense only if that's really what you're asking, as in checking an alleged block size value you've been passed, or something similar.
OTOH, there are lots of places in the code that have to verify that
only a single (flag?) bit has been set, and that code would read a lot better using a better worded test. someone already pointed out that perhaps one of the hweight*() routines from include/linux/bitops.h would be appropriate.
and, yes, i realize that there would be no functional change, but
rewriting tests like this not only makes the code more readable, it allows for the removal of accompanying comments that have to explain to the reader what's going on. but i'll leave the decision to those higher up the food chain.
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
========================================================================
Quoted 14 lines · Petr Tesarik
Robert P. J. Day píše v Čt 23. 04. 2009 v 13:43 -0400:
Quoted 13 lines
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 ininclude/linux/log2.h, which is mathematically identical but, semantically, should be defined independently just so the code is more readable.
Quoted 6 lines
Quoted 1 line
I'm open to an alternative function name.
ispow2()?Because what it really does is to check that a value is a power of two, doesn'it.
by the way, a search for places in the code that are candidates for
this kind of rewriting can be seen at one of my wiki kernel cleanup pages:
http://www.crashcourse.ca/wiki/index.php/The_style_script
scroll down, you'll see a section entitled "Testing for power of 2 or a single bit set". lots of potential for clarification if people think it's worth 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 Čt 28. 05. 2009 v 08:32 -0400:
Quoted 20 lines · Petr Tesarik
Quoted 19 lines
Robert P. J. Day píše v Čt 23. 04. 2009 v 13:43 -0400:
Quoted 6 lines
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]>Quoted 8 lines
---
This is similar to the current
is_power_of_2()routine defined ininclude/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.
ispow2()?
Quoted 8 lines
Quoted 2 lines
Because what it really does is to check that a value is a power of two, doesn'it.
by the way, a search for places in the code that are candidates for
this kind of rewriting can be seen at one of my wiki kernel cleanup pages:
Ah, yes, sorry, I missed the top of your email.
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.
Petr Tesarik
Quoted 8 lines · Petr Tesarik
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