Skip to contentSkip to conversation

find_bit: Micro-optimise find_next_*_bit

PATCH In review Matthew Wilcox 3 participants 3 messages Dec 23, 2016 – Dec 24, 2016

Subsystems (2)
lore
Share & tools
lore
#0 lore raw

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
index 18072ea9c20e..7d4a681d625f 100644
@@ -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
reviewer Acked-by on v1 1/1
#1 lore raw
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,

Acked-by on v1 1/1
#2 lore raw
In reply to Matthew Wilcox

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 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
index 18072ea9c20e..7d4a681d625f 100644
@@ -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.