Skip to contentSkip to conversation

Introduce a boolean "single_bit_set" function.

PATCH In review Robert P. J. Day 5 participants 17 messages Apr 23, 2009 – Jun 30, 2009 Bitops API

lore
Share & tools
lore
#0 lore raw

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
index 6182913..1c0c840 100644
@@ -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

========================================================================

#1 lore raw
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.

---

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 +0 -0
index 6182913..1c0c840 100644

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

#2 lore raw
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.

---

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 +0 -0
index 6182913..1c0c840 100644
@@ -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

========================================================================

#3 lore raw
In reply to David Daney
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))
bool singe_bit_set(unsigned long n)

{
	return __builtin_popcountl(n) == 1;
}

Already done, via hweight_long().

#4 lore raw
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))
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

========================================================================

#5 lore raw
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 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)

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 ;)

#6 lore raw
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 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)

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

========================================================================

#7 lore raw
In reply to Andrew Morton

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 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;

}

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

#8 lore raw
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 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;

}

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

========================================================================

#9 lore raw

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 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;

}

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

#10 lore raw
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

========================================================================

#11 lore raw
In reply to Andrew Morton
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))
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

========================================================================

#12 lore raw
In reply to Robert P. J. Day

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.

Quoted 8 lines

---

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.

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!

#13 lore raw
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.

---

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.

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

========================================================================

#14 lore raw
In reply to Petr Tesarik
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.

---

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.

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

========================================================================

#15 lore raw

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.

Quoted 8 lines

---

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.

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:

http://www.crashcourse.ca/wiki/index.php/The_style_script

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

#16 lore raw
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