RE: [PATCH v2 1/3] lib/find_bit: introduce FIND_FIRST_BIT() macro

From: David Laight <David.Laight@ACULAB.COM>
To: 'Yury Norov' <yury.norov@gmail.com>,
	Andy Shevchenko <andy.shevchenko@gmail.com>
Cc: Linus Torvalds <torvalds@linux-foundation.org>,
	Linux Kernel Mailing List <linux-kernel@vger.kernel.org>,
	Guenter Roeck <linux@roeck-us.net>,
	"Dennis Zhou" <dennis@kernel.org>,
	Russell King <linux@armlinux.org.uk>,
	"Catalin Marinas" <catalin.marinas@arm.com>,
	Andy Shevchenko <andriy.shevchenko@linux.intel.com>,
	Rasmus Villemoes <linux@rasmusvillemoes.dk>,
	Alexey Klimov <aklimov@redhat.com>,
	Kees Cook <keescook@chromium.org>,
	Andy Whitcroft <apw@canonical.com>
Subject: RE: [PATCH v2 1/3] lib/find_bit: introduce FIND_FIRST_BIT() macro
Date: Wed, 24 Aug 2022 14:18:40 +0000	[thread overview]
Message-ID: <eed65809f99d49acbbbf3ba3ce6568a0@AcuMS.aculab.com> (raw)
In-Reply-To: <YwYlWjlWO3fFrtQp@yury-laptop>

...
> And generated code looks almost the same, except that
> on x86_64 your version is bigger. Compare before:
> 0000000000000000 <_find_first_bit>:
>    0:   mov    %rsi,%rax
>    3:   test   %rsi,%rsi
>    6:   je     35 <_find_first_bit+0x35>
>    8:   xor    %edx,%edx
>    a:   jmp    19 <_find_first_bit+0x19>
>    c:   add    $0x40,%rdx               // Track bits and
>   10:   add    $0x8,%rdi                // index separately

That add is free - happens in parallel with other instrutcions

>   14:   cmp    %rax,%rdx
>   17:   jae    35 <_find_first_bit+0x35>

The instructions below will (probably/hopefully) be
speculatively executed in parallel with the cmp/jae above

>   19:   mov    (%rdi),%rcx
>   1c:   test   %rcx,%rcx
>   1f:   je     c <_find_first_bit+0xc>
>   21:   tzcnt  %rcx,%rcx
>   26:   add    %rdx,%rcx
>   29:   cmp    %rcx,%rax
>   2c:   cmova  %rcx,%rax
>   30:   jmp    35 <_find_first_bit+0x35>
>   35:   jmp    3a <_find_first_bit+0x3a>
>   3a:   nopw   0x0(%rax,%rax,1)
> 
> And after:
> 0000000000000000 <_find_first_bit>:
>    0:   mov    %rsi,%rax
>    3:   test   %rsi,%rsi
>    6:   je     39 <_find_first_bit+0x39>
>    8:   xor    %edx,%edx
>    a:   jmp    15 <_find_first_bit+0x15>
>    c:   add    $0x40,%rdx               // Track bits only
>   10:   cmp    %rdx,%rax
>   13:   jbe    39 <_find_first_bit+0x39>
>   15:   mov    %rdx,%rcx
>   18:   shr    $0x6,%rcx                // But divide here
>   1c:   mov    (%rdi,%rcx,8),%rcx
>   20:   test   %rcx,%rcx

That is a long register dependency chain involving %cx.
It will limit the execution speed to (at least 6) clocks/iteration.
The older version might be 3 clocks/iteration.
So this could easily run at half the speed.

	David

>   23:   je     c <_find_first_bit+0xc>
>   25:   tzcnt  %rcx,%rcx
>   2a:   add    %rcx,%rdx
>   2d:   cmp    %rdx,%rax
>   30:   cmova  %rdx,%rax
>   34:   jmp    39 <_find_first_bit+0x39>
>   39:   jmp    3e <_find_first_bit+0x3e>
>   3e:   xchg   %ax,%ax                  // Which adds 4 bytes to .text
> 
> Thanks,
> Yury
> 
> > > +               val = (EXPRESSION);                                             \
> > > +               if (val) {                                                      \
> > > +                       sz = min(idx * BITS_PER_LONG + __ffs(word_op(val)), sz);\
> >
> > sz = min(idx + __ffs(...));
> >
> > > +                       break;                                                  \
> > > +               }                                                               \
> > > +       }                                                                       \
> > > +                                                                               \
> > > +       sz;                                                                     \
> > > +})
> >
> >
> > --
> > With Best Regards,
> > Andy Shevchenko

-
Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK
Registration No: 1397386 (Wales)