Re: [PATCH] find_bit: Micro-optimise find_next_*_bit

From: Yury Norov
Date: Sat Dec 24 2016 - 01:44:15 EST


Hi Mattew,

On Fri, Dec 23, 2016 at 09:20:03AM -0800, Matthew Wilcox wrote:
> From: Matthew Wilcox <mawilcox@xxxxxxxxxxxxx>
>
> 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

> 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.
>
> Signed-off-by: Matthew Wilcox <mawilcox@xxxxxxxxxxxxx>
> ---
> lib/find_bit.c | 2 +-
> 1 file changed, 1 insertion(+), 1 deletion(-)
>
> diff --git a/lib/find_bit.c b/lib/find_bit.c
> index 18072ea9c20e..7d4a681d625f 100644
> --- a/lib/find_bit.c
> +++ b/lib/find_bit.c
> @@ -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;
> --
> 2.11.0


There's also _find_next_bit_le() with same code. I think it should be
also patched.

Acked-by: Yury Norov <ynorov@xxxxxxxxxxxxxxxxxx>