Messages in this thread | | | From | David Laight <> | Subject | RE: [PATCH v2 1/3] lib/find_bit: introduce FIND_FIRST_BIT() macro | Date | Wed, 24 Aug 2022 14:18:40 +0000 |
| |
... > 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)
| |