Re:Is Prefix of String in Table? a Journey into SIMD String...
by trentnelson on Monday May 14, 2018 @03:58PM
(#17068909)
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?
[ Parent
| on HN ]
Re:Is Prefix of String in Table? a Journey into SIMD String...
by jhallenworld on Monday May 14, 2018 @04:51PM
(#17069343)
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 --101101After 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.
Re:Is Prefix of String in Table? a Journey into SIMD String...
by trentnelson on Monday May 14, 2018 @07:40PM
(#17070400)
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.