Is Prefix of String in Table? a Journey into SIMD String Processing
1–10 of 61 posts
Re: Is Prefix of String in Table? a Journey into SIMD String Processing
#2I was wondering how long it took to write such content rich article, then I saw this:
> Hours spent on this article to date: 230.56.
Re: Is Prefix of String in Table? a Journey into SIMD String Processing
#3I was wondering how long it took to write such content rich article, then I saw this: > Hours spent on this article to date: 230.56.
On the plus side, it only takes, like, 3 hours to read end-to-end.
Re: Is Prefix of String in Table? a Journey into SIMD String Processing
#4Re: Is Prefix of String in Table? a Journey into SIMD String Processing
#5The article is much longer than I originally anticipated. If you're looking for some good bits, you could probably jump straight to here: http://trent.me/is-prefix-of-string-in-table/#IsPrefixOfStri...
That discusses the last C implementation before I took a stab at the assembly versions.
The final assembly section was pretty juicy as well: http://trent.me/is-prefix-of-string-in-table/#IsPrefixOfStri....
I was investigating why an earlier assembly version was so slow, then ended up writing a version that unequivocally beat all the C and previous assembly versions across the board (both prefix and negative matching, and worst case false-positive matching (where up to three comparisons needed to be done)).
TL;DR with optimized data structures specifically geared toward SIMD instructions, you can definitely get sizable performance improvements in both C with intrinsics, and then again with raw assembly.
Re: Is Prefix of String in Table? a Journey into SIMD String Processing
#6Side note: people have been inquiring how I made the diagrams and whatnot. I'll put a little section like that on the next article. For now though:
The two main diagrams, depicting struct layout and then the 5-pane register walk through, were done in Visio, then saved as SVG, with fonts edited directly in Vim (took a few cycles to figure out which fonts looked best across all devices).
The charts were done in Excel, connected to the CSV data files produced by the benchmark utility, then wired up using a PivotTable. A PivotChart was created, Save As -> PDF, edit PDF in Inkscape, delete surrounding border, crop canvas to fit diagram, Save As -> SVG. Edit SVG fonts in Vim, voila, nice vectorized graph!
Sounds laborious, and it took forever to get the flow down, once I'd settled on a process it was pretty easy to whip up new graphs.
Re: Is Prefix of String in Table? a Journey into SIMD String Processing
#7This 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.)
Re: Is Prefix of String in Table? a Journey into SIMD String Processing
#8Side note: people have been inquiring how I made the diagrams and whatnot. I'll put a little section like that on the next article. For now though: The two main diagrams, depicting struct layout and then the 5-pane register walk through, were done in Visio, then saved as SVG, with fonts edited directly in Vim (took a few cycles to figure out which fonts looked best across all devices). The charts were done in Excel,…
I admire your attention to detail and keen sense of aesthetics. Well done.
Re: Is Prefix of String in Table? a Journey into SIMD String Processing
#9This 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.)
He was only searching 16 strings. The overhead of a binary search on such a small N would likely overwhelm the algorithmic improvements of moving from an O(N) to O(log N) implementation.
Re: Is Prefix of String in Table? a Journey into SIMD String Processing
#10This 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.)
Sorting the strings by length, or lexicographical? Length sort wouldn't work for the prefix-oriented nature of the comparisons. Lexicographical sorting and a binary search involves pointer chasing, and doesn't provide any way to fast-path the negative match lookup.
If I'm getting called a trillion times on a hot-path, but only a million of those times I'm receiving a module name (search string) I'm interested in, then it behooves me to have the fastest negative match logic possible.
As it stands, the final assembly version can negative match in about 6 cycles, prefix match in about 14 cycles, and worst-case false-positive negative match (where three strings need to be compared, but there is no match) in 21 cycles. The CPI for the final routine is reported as around 0.266, which is pretty close to the optimal of 0.25.
I think you'd struggle to meet that performance with anything that relies on pointer chasing. I do comment on the likelihood of a log(n)-based algorithm overtaking performance when the data set is large enough here: http://trent.me/is-prefix-of-string-in-table/#other-applicat...
This particular use case wasn't intended for prefix matching against large data sets though, and thus, wasn't optimized for that.