find_bit: Micro-optimise find_next_*_bit
Subsystems (2)
PATCH 1/1 find_bit: Micro-optimise find_next_*_bit
From: Matthew Wilcox <[email protected]>
This saves 20 bytes on my x86-64 build, mostly due to alignment considerations ... I think it actually saves about five bytes of instructions. There's really two parts to this commit. First, the first half of the test: (!nbits || start >= nbits) is trivially a subset of the second half, since nbits and start are both unsigned. Second, while looking at the disassembly, I noticed that GCC was predicting the branch taken. Since this is a failure case, it's clearly the less likely of the two branches, so add an unlikely() to override GCC's heuristics.
--- lib/find_bit.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
lib/find_bit.c +1 -1
@@ -33,7 +33,7 @@ static unsigned long _find_next_bit(const unsigned long *addr, {unsigned long tmp; -if (!nbits || start >= nbits) +if (unlikely (start >= nbits))return nbits; tmp = addr[start /BITS_PER_LONG ] ^ invert;
Signature · 1 line
2.11.0
Quoted 4 lines · Matthew Wilcox
From: Matthew Wilcox <[email protected]>
First, the first half of the test: (!nbits || start >= nbits) is trivially a subset of the second half, since nbits and start are both unsigned.
Yeah, I filed that as a missed optimization bug with gcc a year ago, but it seems that even 6.3 still does two tests - clang 3.6 is a bit smarter. Anyway,
Hi Mattew,
Quoted 7 lines · Matthew Wilcox
From: Matthew Wilcox <[email protected]>
This saves 20 bytes on my x86-64 build, mostly due to alignment considerations ... I think it actually saves about five bytes of instructions. There's really two parts to this commit. First, the first half of the test: (!nbits || start >= nbits) is trivially a subset of the second half, since nbits and start are both unsigned.
Yes... It's obvious... when you point it out.
ARM64 GCC compiler didn't notice it as well as me:
37 0000000000000070 <find_next_bit>:
38 70: eb1f003f cmp x1, xzr 39 74: fa421020 ccmp x1, x2, #0x0, ne 40 78: 54000088 b.hi 88 <find_next_bit+0x18> 41 7c: aa0103e0 mov x0, x1 42 80: d65f03c0 ret 43 84: d503201f nop 44 88: a9bf7bfd stp x29, x30, [sp,#-16]! 45 8c: 910003fd mov x29, sp 46 90: d2800003 mov x3, #0x0 // #0 47 94: 97ffffdb bl 0 <_find_next_bit.part.0> 48 98: a8c17bfd ldp x29, x30, [sp],#16 49 9c: d65f03c0 ret
Quoted 25 lines
Second,
while looking at the disassembly, I noticed that GCC was predicting the branch taken. Since this is a failure case, it's clearly the less likely of the two branches, so add anunlikely()to override GCC's heuristics.Signed-off-by Matthew Wilcox <[email protected]>--- lib/find_bit.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)lib/find_bit.c +1
-1@@ -33,7 +33,7 @@ static unsigned long _find_next_bit(const unsigned long *addr, {unsigned long tmp; -if (!nbits || start >= nbits) +if (unlikely (start >= nbits))return nbits; tmp = addr[start /BITS_PER_LONG ] ^ invert;Signature · 1 line
2.11.0
There's also _find_next_bit_le() with same code. I think it should be also patched.