3 ms·
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
by trentnelson 8y ago
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 8y agoHere 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 8y agoI 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.