On: Is Prefix of String in Table? a Journey into SIMD String Processing

[jhallenworld]

There is an Intel PEXT instruction, but I don't know the cycle count and I think it's limited to 64 bits. With PEXT the whole prefix match is four instructions.

[trentnelson → jhallenworld]

PEXT is pretty cheap... but, I still don't think I understand how what you're suggesting could optimally apply to prefix matching against all 16 strings at once, or why it would offer a substantial speed-up to the approach I've used? Can you elaborate?

[jhallenworld → trentnelson]

Here is a small example:

Strings (written right to left):

    -----101
    --100101
    -----010
    --100010

Mask:

    00111010

Table:

    Index Contents
    0000  -----101
    0001  -----010
    0010  -----101
    0011  -----010
    0100  -----101
    0101  -----010
    0110  -----101
    0111  -----010
    1000  --100101
    1001  --100010
    1010  -----101
    1011  -----010
    1100  -----101
    1101  -----010
    1110  -----101
    1111  -----010

Suppose the input is --101101

After the mask, the result is 00101000

After the compress, the result is 1010

Table index 1010 has -----101, so it's a hit. with string 101.

Now Suppose the input is --100101

After the mask, the result is 00100000

After the compress, the result is 1000

Table index 1000 has --100101, so it's a hit. with string 100101.

[trentnelson → jhallenworld]

I can't see how this avoids needing to do a comparison against the string in the slot once you've actually found the index though. I think I need to see this in C or asm to grok what the benefits are.