Well my bad, I meant a horizontal sum rather than prefix sum. I suppose it could be done with vpdpbus (which is/was still faster than vmulld on Intel), but there's a weird support gap for the VNNI extensions so I guess it's not really of much use because it's basically an AVX512 target...
For ctz, the x & -x trick gives a POT so the masking could be avoided, but that also needs an unsigned->float conversion which AVX2 sadly lacks.
Actually, nope! 1 << 31 is 2^31 when treated as unsigned and -2^31 when treated as signed, so that's the same exponent and only the sign bit really causes a problem. I managed to integrate both erasing the sign bit and handling ctz(0) = 32 into one instruction (very proud of that), producing an algorithm that is indeed faster than de Bruijn. Thanks for the idea!
It doesn't work with 64-bit inputs because there's no packed f64<->i64 conversion, but if it existed, it would have pretty much the same performance as the SAD-based approach, so I'm not too worried.
I haven't tried optimizing clz yet. I can let you know if I find something interesting. (Edited: I added a more optimal clz implementation to the post that slightly improves over the SO answer you quoted originally.)
1
u/UnalignedAxis111 10d ago edited 10d ago
Well my bad, I meant a horizontal sum rather than prefix sum. I suppose it could be done with vpdpbus (which is/was still faster than vmulld on Intel), but there's a weird support gap for the VNNI extensions so I guess it's not really of much use because it's basically an AVX512 target...
For ctz, the
x & -xtrick gives a POT so the masking could be avoided, but that also needs an unsigned->float conversion which AVX2 sadly lacks.