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

31–40 of 61 posts

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

#31

Post by rurban »

trentnelson wrote: post #22
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…

Patches welcome :-) But seriously though, I played around with compression a bit initially: https://github.com/tpn/tracer/blob/master/StringTable/String... . Referenced Hacker's Delight when I was working on it. Granted, this was just for compressing the USHORT lengths into BYTE-sized lengths. Are you sure your compression suggestion would work for prefix matches? If you can get lower latency than the fastest assembl…

True. A gperf alike hash table (with special key indices) works only ok with compile-time known strings. But a simple CMP-alike perfect hash table with double indirection would be worthwhile to test against.

I called it Hanov after http://stevehanov.ca/blog/index.php?id=119 Problem is there that you have to calc a hash for each string, which is only fast with __builtin_crc/_mm_crc32_u64

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

#32

Post by gridspy »

floor_ wrote: post #4
trentnelson wrote: post #3

Earlier quoted context omitted.

On the plus side, it only takes, like, 3 hours to read end-to-end.

You should simd your reading process and split that in to threads.

Inter-thread communication is hard.

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

#33

Post by trentnelson »

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?

Sure am!

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

#34

Post by jhallenworld »

trentnelson wrote: post #22
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…

Patches welcome :-) But seriously though, I played around with compression a bit initially: https://github.com/tpn/tracer/blob/master/StringTable/String... . Referenced Hacker's Delight when I was working on it. Granted, this was just for compressing the USHORT lengths into BYTE-sized lengths. Are you sure your compression suggestion would work for prefix matches? If you can get lower latency than the fastest assembl…

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.

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

#35

Post by trentnelson »

jhallenworld wrote: post #34
trentnelson wrote: post #22

Earlier quoted context omitted.

Patches welcome :-) But seriously though, I played around with compression a bit initially: https://github.com/tpn/tracer/blob/master/StringTable/String... . Referenced Hacker's Delight when I was working on it. Granted, this was just for compressing the USHORT lengths into BYTE-sized lengths. Are you sure your compression suggestion would work for prefix matches? If you can get lower latency than the fastest assembl…

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.

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?

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

#36

Post by gumby »

> A reference implementation was written in C as a baseline, which simply looped through an array of strings, comparing each one, byte-by-byte, looking for a prefix match.

This is a poor choice; the 1970s boyer-moore also is significantly faster for most case as it avoids many pointless searches. And if you have a dedicated search table you can optimize the search even more (e.g. pre-sorting keys and targets, using a more dedicated structure like a trie, etc)

I think these approaches would also be amenable to deliberate acceleration with intrinsics, as you did with your brute force search.

Regardless, interesting work.

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

#37

Post by gumby »

dragontamer wrote: post #18

Absolutely excellent! SIMD-units of the x86-64 CPU are not discussed enough IMO. And every time they are discussed, I'm always blown away by their efficiency in solving some tasks. --------------- Full disclosure: I don't understand what you've done yet. I've just skimmed the article really quick, but I already have some questions. Hopefully you didn't answer them already elsewhere, lol. * Any reason to highly-optimi…

Note that some of the AVX instructions will slow down the rest of your CPU -- not a reason to avoid them, but you you need to understand your workload (you can't just throw them willy-nilly into the code path).

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

#38

Post by trentnelson »

gumby wrote: post #36

> A reference implementation was written in C as a baseline, which simply looped through an array of strings, comparing each one, byte-by-byte, looking for a prefix match. This is a poor choice; the 1970s boyer-moore also is significantly faster for most case as it avoids many pointless searches. And if you have a dedicated search table you can optimize the search even more (e.g. pre-sorting keys and targets, using a…

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 algorithms that involved pointer chasing. There's this comment at the top of StringTable.h:

    The design is optimized for relatively short strings (less than or equal to
    16 chars), and relatively few of them (less than or equal to 16).  These
    restrictive size constraints facilitate aggressive SIMD optimizations when
    searching for the strings within the table, with the goal to minimize the
    maximum possible latency incurred by the lookup mechanism.  The trade-off
    is usability and flexibility -- two things which can be better served by
    prefix trees if the pointer-chasing behavior of said data structures can
    be tolerated.
https://github.com/tpn/tracer/blob/v0.1.12/StringTable2/Stri...

I'm not sure if Boyer-Moore is well suited to the specific use case I wanted to address. It is geared toward looking for occurrences of a pattern in a stream of text bytes, which isn't really what I'm doing at all. I have an input string of known length. I have up to 16 strings in a table, and I want to quickly check if any of those strings "start with or are equal to" my input string, with special emphasis on negative matching being on the fast path, and preserving the location of the match in the table (so it can be cast to an enum, for example).

So, this article was specifically about the SIMD-oriented STRING_TABLE structure, not necessarily about the history of string processing. Another article potentially comparing this approach to tries, Boyer-Moor or Aho-Corasick would make sense in the context of larger prefix table data sets (and a larger text corpus being searched, e.g. wikipedia dumps).

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

#39

Post by Myrmornis »

trentnelson wrote: post #38
gumby wrote: post #36

> A reference implementation was written in C as a baseline, which simply looped through an array of strings, comparing each one, byte-by-byte, looking for a prefix match. This is a poor choice; the 1970s boyer-moore also is significantly faster for most case as it avoids many pointless searches. And if you have a dedicated search table you can optimize the search even more (e.g. pre-sorting keys and targets, using a…

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?

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

#40

Post by xenadu02 »

ridiculous_fish wrote: post #7

This seems like a complicated way to speed up a linear scan. What's the advantage of this approach over just sorting the strings and doing a binary search, which is log N? (Not a naive binary search using strcmp, but the trick where you find the lower and upper bounds given index 0, refine it using index 1, etc. until your input is exhausted.)

Chasing pointers is cache death. Many theoretically optimal algorithms have been struck down by the God of Memory Latency.

eg, If you measure it, tree performance will often be much improved by storing slightly less than one cache line's worth of data at each node. The CPU can pipeline and predict the shit out of the linear search at each node to the point that all the theoretical O(1) or O(log N) lookups in the world get demolished by a CS101 scan of the array. This makes a relatively good general use cache aware data structure because small collections tend to fit into a single cache line while large data structures have relatively few pointers to chase.

Of course as the OP demonstrates, optimizing for your specific use case can yield even more dramatic improvements.

Post reply on HN