lkml.org 
[lkml]   [2022]   [Aug]   [24]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
From
SubjectRE: [PATCH v2 1/3] lib/find_bit: introduce FIND_FIRST_BIT() macro
Date
...
> 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)

\
 
 \ /
  Last update: 2022-08-24 16:19    [W:0.060 / U:0.760 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site