Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

trent.me

Post reply on HN
Print view View original

51–60 of 61 posts

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

#51

Post by resource0x »

jhallenworld wrote: post #20

Here is a way to do it with a perfect hash table (so only one lookup). Find a 128-bit mask that will be used to select bits of the input string. You want to minimize the number of 1 bits in the mask, since the table size is 2^(number of 1 bits). On the other hand, you need to pick enough 1 bits so that there is only one string per table entry. AND this mask with the input string. COMPRESS these bits using the mask. T…

Is there any way to quickly compute 32-bit hash code of the string using SIMD? If yes, then we get a very fast perfect hash map: https://github.com/tatumizer/pigeon_map. Hash code in question is not supposed to be of crypto quality, just "good enough" will be good enough :)

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

#52

Post by trentnelson »

jhallenworld wrote: post #43
trentnelson wrote: post #35

Earlier quoted context omitted.

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?

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 00101…

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.

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

#53

Post by Myrmornis »

Myrmornis wrote: post #39
trentnelson wrote: post #38

Earlier quoted context omitted.

Well... I mean the first version (IsPrefixOfStringInTable_1) uses the lengths from the string array to improve performance versus the baseline: http://trent.me/is-prefix-of-string-in-table/#IsPrefixOfStri... The super-simple baseline referred to in the intro was whipped up as a trivial example of the simplest approach you could take for the problem. Trie was never in contention as I didn't want to rely on any algorit…

What's the issue with "pointer-chasing"? That it might be inefficient in practice (despite preferable runtime complexity?) due to making poor use of CPU caches?

To the person who downvoted this: you're using downvotes wrongly. I was asking a question about computer science. Down-voting people who ask questions about computer science is not the way to encourage the sort of conversation we're trying to encourage on HN.

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

#54

Post by anitil »

garmaine wrote: post #30
trentnelson wrote: post #24

Fun tidbits: a) I bombed, like, 6 coding interviews whilst writing this article. Two of them were related to string processing, too, which I thought was funny. (In a depressingly ironic kind of way.) No point, other than I seemingly suck at the "leetcode" coding interview style companies seem to rely upon these days. And b) there are at least two Easter eggs in this post that no-one seems to have noticed. Oh, and c)…

So you’re looking for a job then?

Asking the right questions garmaine

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

#55

Post by gravypod »

Is this somewhere a Bloom Filter (or similar probabilistic data structures) could be used to improve performance? From a quick survey of cryptographic hash functions something like BLAKE2 would serve your needs at ~4ops/byte. If you had a wide enough bloom filter you can turn your check, in most cases, into a binary &.

Just a thought. The author here obviously already knows what they're doing and has likely thought of this but I'd be interested in hearing why this ASM-optimized approach was chosen instead.

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

#56

Post by trentnelson »

gravypod wrote: post #55

Is this somewhere a Bloom Filter (or similar probabilistic data structures) could be used to improve performance? From a quick survey of cryptographic hash functions something like BLAKE2 would serve your needs at ~4ops/byte. If you had a wide enough bloom filter you can turn your check, in most cases, into a binary &. Just a thought. The author here obviously already knows what they're doing and has likely thought o…

The initial length + unique character test allows us to negative match in a way that is effectively identical to a bloom filter.

If the initial negative match test indicates no match, then we can be certain there is not a match. Otherwise, we might have a match, and need to compare the candidate strings in more detail.

I can't imagine how hashing would help in either the fast-path negative match case, or the prefix match case. Hashing is sort of at odds with prefix matching, in my opinion.

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

#57

Post by FreakLegion »

gravypod wrote: post #55

Is this somewhere a Bloom Filter (or similar probabilistic data structures) could be used to improve performance? From a quick survey of cryptographic hash functions something like BLAKE2 would serve your needs at ~4ops/byte. If you had a wide enough bloom filter you can turn your check, in most cases, into a binary &. Just a thought. The author here obviously already knows what they're doing and has likely thought o…

It's prefix rather than exact matching, so the Bloom filter et al. aren't going to work so well.

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

#58

Post by gravypod »

trentnelson wrote: post #56
gravypod wrote: post #55

Is this somewhere a Bloom Filter (or similar probabilistic data structures) could be used to improve performance? From a quick survey of cryptographic hash functions something like BLAKE2 would serve your needs at ~4ops/byte. If you had a wide enough bloom filter you can turn your check, in most cases, into a binary &. Just a thought. The author here obviously already knows what they're doing and has likely thought o…

The initial length + unique character test allows us to negative match in a way that is effectively identical to a bloom filter. If the initial negative match test indicates no match, then we can be certain there is not a match. Otherwise, we might have a match, and need to compare the candidate strings in more detail. I can't imagine how hashing would help in either the fast-path negative match case, or the prefix m…

Could you get good-enough performance with something simpler and more portable?

The optimized assembly is much more complicated and specialized. Porting platforms/architectures is very difficult and you loose out on the compiler's abilities to make assumptions and optimize your code.

String length is a very poor probabilistic filter as you're specifically looking substrings.

Also if you already have a hash of your input string's prefix, and the hash of all of your known strings, in the case where you actually need to check against your "known" strings becomes a fast search of a set of numbers making the fail-through case of your code negligible. If you impose a limit of strings in your "known" pool the compiler can have a field day.

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

#59

Post by trentnelson »

gravypod wrote: post #58
trentnelson wrote: post #56

Earlier quoted context omitted.

The initial length + unique character test allows us to negative match in a way that is effectively identical to a bloom filter. If the initial negative match test indicates no match, then we can be certain there is not a match. Otherwise, we might have a match, and need to compare the candidate strings in more detail. I can't imagine how hashing would help in either the fast-path negative match case, or the prefix m…

Could you get good-enough performance with something simpler and more portable? The optimized assembly is much more complicated and specialized. Porting platforms/architectures is very difficult and you loose out on the compiler's abilities to make assumptions and optimize your code. String length is a very poor probabilistic filter as you're specifically looking substrings. Also if you already have a hash of your in…

> Could you get good-enough performance with something simpler and more portable?

Hmmm. Did you read the article? Any of the C versions are relatively simple and portable. They basically work the same as the assembly ones and give great performance... I'm not sure what you're trying to get at.

> The optimized assembly is much more complicated and specialized.

Well, it's my article, I wanted to see if I could beat a PGO C compiler with all its optimizations turned on :-)

> Porting platforms/architectures is very difficult and you loose out on the compiler's abilities to make assumptions and optimize your code.

I know the trade-offs that come with assembly. But if you're okay with them, you can get the best possible performance out of the underlying hardware. That was the goal of this article.

> String length is a very poor probabilistic filter as you're specifically looking substrings.

I don't understand this comment. String length is a great filter because if any strings in the table are longer than the input search string, then there's no way we can have a prefix match.

> Also if you already have a hash of your input string's prefix, and the hash of all of your known strings, in the case where you actually need to check against your "known" strings becomes a fast search of a set of numbers making the fail-through case of your code negligible. If you impose a limit of strings in your "known" pool the compiler can have a field day.

I don't know where this fascination with hashes comes from... have you looked at the implementation? Even when it has to do a string match, the timings now are around 13-14 cycles. The nature of the data structure means you're really only ever doing max 2 comparisons... 3 if someone is sending you worst case data (and even so, with 3, you're only clocking ~20 cycles).

Hashing and prefix matching just don't play well nicely together.

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

#60

Post by trentnelson »

resource0x wrote: post #51
jhallenworld wrote: post #20

Here is a way to do it with a perfect hash table (so only one lookup). Find a 128-bit mask that will be used to select bits of the input string. You want to minimize the number of 1 bits in the mask, since the table size is 2^(number of 1 bits). On the other hand, you need to pick enough 1 bits so that there is only one string per table entry. AND this mask with the input string. COMPRESS these bits using the mask. T…

Is there any way to quickly compute 32-bit hash code of the string using SIMD? If yes, then we get a very fast perfect hash map: https://github.com/tatumizer/pigeon_map . Hash code in question is not supposed to be of crypto quality, just "good enough" will be good enough :)

Where's all this newfound interest in hash maps coming from? Once you hash something, you lose the prefix information, making it kinda' useless for this activity. Unless you create a hash for every string length variation... but, that seems like a lot of overhead for very little gain.

I also can't see how you'd get that negative match fast path performance if you were reliant on hashes. That owes its speed to the length and unique char filter working in concert.

Post reply on HN