3 ms·

Hmm, interesting idea. The main problem I see is that PEXT can only move bits from within an 64-bit operand, so we can't operate on the 512-bit vectors anymore

Hmm, interesting idea. The main problem I see is that PEXT can only move bits from within an 64-bit operand, so we can't operate on the 512-bit vectors anymore, AFAICT. We'd have to split the loop up into 8-byte chunks instead, and expand the mask from 1 to 8 bits per comparison, so PEXT pulls out all the bits of each character (e.g. a 4-bit mask 1011 becomes 0xFF00FFFF). This mask computation could be done in 512-byte chunks, but we'd have to split the original 1-bit mask up into 8-bit slices that each get popcounted individually (either in a 256 byte table lookup or with the popcount instruction). That's just so we know how much to increment the pointer between each 8-byte chunk. All in all, I think the 8 popcounts + 8 PEXTs would make it slower than the full 512-bit version (there's only one PEXT execution unit on Skylake X chips). It might be competitive on machines without AVX-512, though. I'll try out some code--I should actually be able to run this one :)

deleted 8y ago
[deleted]
deleted 8y ago
[deleted]
BeeOnRope 8y ago
If you could avoid actually using POPCNT for the popcount, and the limiting factor was the pext, the "speed limit" of this approach would be around 0.125 cycles per input byte since pext handles 8 bytes and you can do 1 per cycle. Of course that assumes that you can fit 100% of the remaining work for every 8 byte chunk into what's left of that cycle (ie into no more than 3 uops). Since you have at least a store and a load per word, that's probably going to be impossible! It's not totally unlikely that you could get to around 0.25 cycles though. A good approach would be to vectorize the rest of the work and store the resulting mask values and increments in 64-byte chunks, to be re-read by the scalar part (since there is no really efficient way to get stuff from vector to GP regs). So the scalar part would have 3 loads (mask, increment, input data) a store and the pointer increment. I guess you could load-op the addition, so it seems possible you might be limited by the 3 loads (taking 1.5 cycles).

deleted 8y ago

[deleted]

deleted 8y ago

[deleted]

BeeOnRope 8y ago

If you could avoid actually using POPCNT for the popcount, and the limiting factor was the pext, the "speed limit" of this approach would be around 0.125 cycles per input byte since pext handles 8 bytes and you can do 1 per cycle. Of course that assumes that you can fit 100% of the remaining work for every 8 byte chunk into what's left of that cycle (ie into no more than 3 uops). Since you have at least a store and a load per word, that's probably going to be impossible! It's not totally unlikely that you could get to around 0.25 cycles though. A good approach would be to vectorize the rest of the work and store the resulting mask values and increments in 64-byte chunks, to be re-read by the scalar part (since there is no really efficient way to get stuff from vector to GP regs). So the scalar part would have 3 loads (mask, increment, input data) a store and the pointer increment. I guess you could load-op the addition, so it seems possible you might be limited by the 3 loads (taking 1.5 cycles).