Re: [PATCH 02/17] bitops: Add generic parity calculation for u64

Yury Norov
2025-02-27T19:41:58Z

On Wed, Feb 26, 2025 at 10:29:11PM +0000, David Laight wrote:
> On Mon, 24 Feb 2025 14:27:03 -0500
> Yury Norov <yury.norov@gmail.com> wrote:
> ....
> > +#define parity(val) \
> > +({ \
> > + u64 __v = (val); \
> > + int __ret; \
> > + switch (BITS_PER_TYPE(val)) { \
> > + case 64: \
> > + __v ^= __v >> 32; \
> > + fallthrough; \
> > + case 32: \
> > + __v ^= __v >> 16; \
> > + fallthrough; \
> > + case 16: \
> > + __v ^= __v >> 8; \
> > + fallthrough; \
> > + case 8: \
> > + __v ^= __v >> 4; \
> > + __ret = (0x6996 >> (__v & 0xf)) & 1; \
> > + break; \
> > + default: \
> > + BUILD_BUG(); \
> > + } \
> > + __ret; \
> > +})
> > +
>
> You really don't want to do that!
> gcc makes a right hash of it for x86 (32bit).
> See https://www.godbolt.org/z/jG8dv3cvs

GCC fails to even understand this. Of course, the __v should be an
__auto_type. But that way GCC fails to understand that case 64 is
a dead code for all smaller type and throws a false-positive
Wshift-count-overflow. This is a known issue, unfixed for 25 years!

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=4210

> You do better using a __v32 after the 64bit xor.

It should be an __auto_type. I already mentioned. So because of that,
we can either do something like this:

#define parity(val) \
({ \
#ifdef CLANG \
__auto_type __v = (val); \
#else /* GCC; because of this and that */ \
u64 __v = (val); \
#endif \
int __ret; \

Or simply disable Wshift-count-overflow for GCC.

> Even the 64bit version is probably sub-optimal (both gcc and clang).
> The whole lot ends up being a bit single register dependency chain.
> You want to do:

No, I don't. I want to have a sane compiler that does it for me.

> mov %eax, %edx
> shrl $n, %eax
> xor %edx, %eax
> so that the 'mov' and 'shrl' can happen in the same clock
> (without relying on the register-register move being optimised out).
>
> I dropped in the arm64 for an example of where the magic shift of 6996
> just adds an extra instruction.

It's still unclear to me that this parity thing is used in hot paths.
If that holds, it's unclear that your hand-made version is better than
what's generated by GCC.

Do you have any perf test?

Thanks,
Yury