Date: Sat, 24 Dec 2016 12:13:35 +0530
From: Yury Norov <ynorov@caviumnetworks.com>
To: Matthew Wilcox <mawilcox@linuxonhyperv.com>
CC: Yury Norov <yury.norov@gmail.com>,
        Rasmus Villemoes <linux@rasmusvillemoes.dk>,
        George Spelvin <linux@horizon.com>,
        Akinobu Mita <akinobu.mita@gmail.com>,
        Thomas Gleixner <tglx@linutronix.de>,
        Andrew Morton <akpm@linux-foundation.org>,
        <linux-kernel@vger.kernel.org>,
        Matthew Wilcox <mawilcox@microsoft.com>
Subject: Re: [PATCH] find_bit: Micro-optimise find_next_*_bit
Message-ID: <20161224064335.GA7280@yury-N73SV>
References: <1482513603-9630-1-git-send-email-mawilcox@linuxonhyperv.com>
MIME-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Content-Disposition: inline
In-Reply-To: <1482513603-9630-1-git-send-email-mawilcox@linuxonhyperv.com>
User-Agent: Mutt/1.5.24 (2015-08-30)
SpamDiagnosticOutput: 1:99
SpamDiagnosticMetadata: NSPM
X-MS-Exchange-CrossTenant-OriginalArrivalTime: 24 Dec 2016 06:43:47.3135 (UTC)
X-MS-Exchange-CrossTenant-FromEntityHeader: Hosted
X-MS-Exchange-Transport-CrossTenantHeadersStamped: DM3PR07MB2249
Sender: linux-kernel-owner@vger.kernel.org
List-ID: <linux-kernel.vger.kernel.org>
X-Mailing-List: linux-kernel@vger.kernel.org
Content-Length: 2076
Lines: 60

Hi Mattew,

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