Optimize is_power_of_2().
PATCH 1/1 Optimize is_power_of_2().
From: Vegard Nossum <[email protected]>
Date: Fri, 15 Jun 2007 18:35:49 +0200
Subject: [PATCH] Optimize is_power_of_2().
Rationale: Removes one conditional branch and reduces icache footprint.
Proof: If n is false, the product of n and any value is false. If n is true, the truth of (n * x) is the truth of x.
--- include/linux/log2.h | 2 +- 1 files changed, 1 insertions(+), 1 deletions(-)
include/linux/log2.h +1 -1
@@ -51,7 +51,7 @@ int __ilog2_u64(u64 n)static inline __attribute__((const))bool is_power_of_2 (unsigned long n) { -return (n !=0 && ((n & (n -1 )) ==0 )); +return n * !(n & (n -1 )); }/*
Signature · 1 line
1.5.0.6
Quoted 8 lines · Vegard Nossum
From: Vegard Nossum <[email protected]>
Date: Fri, 15 Jun 2007 18:35:49 +0200
Subject: [PATCH] Optimizeis_power_of_2().Rationale: Removes one conditional branch and reduces icache footprint.
Proof: If n is false, the product of n and any value is false. If n is true, the truth of (n * x) is the truth of x.
You realize that on a lot of platforms, multiplication is done by an out-of-line subroutine, and that even on those that aren't, it's generally a long-pipeline operation, right?
-hpa
Quoted 5 lines · H. Peter Anvin
Quoted 4 lines · Vegard Nossum
From: Vegard Nossum <[email protected]>
Date: Fri, 15 Jun 2007 18:35:49 +0200
Subject: [PATCH] Optimizeis_power_of_2().
Quoted 7 lines
Quoted 3 lines
Rationale: Removes one conditional branch and reduces icache footprint. Proof: If n is false, the product of n and any value is false. If n is true, the truth of (n * x) is the truth of x.
You realize that on a lot of platforms, multiplication is done by an out-of-line subroutine, and that even on those that aren't, it's generally a long-pipeline operation, right?
i was *just* about to mention somthing of the sort, but probably not as succinctly.
rday
Signature · 7 lines
======================================================================== Robert P. J. Day Linux Consulting, Training and Annoying Kernel Pedantry Waterloo, Ontario, CANADA http://fsdev.net/wiki/index.php?title=Main_Page ========================================================================
Quoted 10 lines · Robert P. J. Day
Quoted 8 lines · H. Peter Anvin
Quoted 7 lines · Vegard Nossum
From: Vegard Nossum <[email protected]>
Date: Fri, 15 Jun 2007 18:35:49 +0200
Subject: [PATCH] Optimizeis_power_of_2().Rationale: Removes one conditional branch and reduces icache footprint. Proof: If n is false, the product of n and any value is false. If n is true, the truth of (n * x) is the truth of x.
Quoted 7 lines
Quoted 3 lines
You realize that on a lot of platforms, multiplication is done by an out-of-line subroutine, and that even on those that aren't, it's generally a long-pipeline operation, right?
i was *just* about to mention somthing of the sort, but probably not as succinctly.
You also realize, I hope, that obfuscating this for the compiler just hurts. As has already been described, there are versions involving jumps, selects, multiplication, tables, ffs, and popcount. All of those operations are hideously expensive on some architectures and cheap on others.
Personally, I would bet that the version as originally written is probably best, since select (conditional move) is a fairly commonly supported operation, especially on architectures where jumps are expensive.
Just to confuse the situation further, here is yet another version:
bool is_power_of_2(unsigned long n)
{
return !!n & !(n & (n-1));
}... which, on i686 compiles to:
00000000 <is_power_of_2>:
0: 85 c0 test %eax,%eax 2: 8d 50 ff lea 0xffffffff(%eax),%edx 5: 0f 95 c1 setne %cl 8: 85 d0 test %edx,%eax a: 0f 94 c0 sete %al d: 0f b6 c0 movzbl %al,%eax 10: 21 c8 and %ecx,%eax 12: c3 ret
In the current version, gcc does generate a jump on i686 and x86-64:
00000000 <is_power_of_2>:
0: 89 c2 mov %eax,%edx 2: 31 c0 xor %eax,%eax 4: 85 d2 test %edx,%edx 6: 74 0b je 13 <is_power_of_2+0x13> 8: 8d 42 ff lea 0xffffffff(%edx),%eax b: 85 c2 test %eax,%edx d: 0f 94 c0 sete %al 10: 83 e0 01 and $0x1,%eax 13: f3 c3 repz ret
-hpa
Quoted 5 lines · Vegard Nossum
bool
is_power_of_2(unsigned long n)
{include/linux/log2.h +1
-1-return (n !=0 && ((n & (n -1 )) ==0 )); +return n * !(n & (n -1 ));}
There is a third way which uses neither * nor &&, but []:
bool is_power_of_2(unsigned long n)
{
static const bool yn[] = {
[0] = false,
[1 ... (8 * sizeof(n) - 1)] = true,
};
return yn[(n & (n - 1)) == 0];
}Jan
Quoted 8 lines · On Fri, 15 Jun 2007 21:47:50 +0200 (CEST) Jan Engelhardt…
Quoted 5 lines · Vegard Nossum
bool
is_power_of_2(unsigned long n)
{include/linux/log2.h +1
-1-return (n !=0 && ((n & (n -1 )) ==0 )); +return n * !(n & (n -1 ));}
There is a third way which uses neither * nor &&, but []:
I assume using something GCC-specific is right out?
bool is_power_of_to(unsigned long n)
{
return __builtin_ffsl(n) == 1;
}- DML
Quoted 12 lines · On Fri, 15 Jun 2007 14:54:20 -0500 "David M. Lloyd" <[email protected]> wrote:
Quoted 8 lines · On Fri, 15 Jun 2007 21:47:50 +0200 (CEST) Jan Engelhardt…
Quoted 5 lines · Vegard Nossum
bool
is_power_of_2(unsigned long n)
{include/linux/log2.h +1
-1-return (n !=0 && ((n & (n -1 )) ==0 )); +return n * !(n & (n -1 ));}
There is a third way which uses neither * nor &&, but []:
Quoted 5 lines
I assume using something GCC-specific is right out?
bool
is_power_of_to(unsigned long n){ return __builtin_ffsl(n) == 1;
Pretend I typed this instead:
bool is_power_of_2(unsigned long n)
{
return __builtin_popcountl(n) == 1;
}All I can say is, it's really hot here :P
- DML