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

41–50 of 61 posts

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

#41

Post by dragontamer »

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?

> That it might be inefficient in practice

That's basically it.

Consider that his algorithm completes 16-searches in 20-cycles, or roughly 5 nanoseconds.

A single fetch from main-memory will take 50-nanoseconds, or be ~10x slower than the methodology discussed in this post. Even a fetch from L3 cache is typically 10-nanoseconds, while a fetch from L1 cache is 1ns or ~4-cycles. This SIMD-methodology is incredibly FAST.

The "best-case" scenario of this SIMD code is 6-cycles, which is faster than two L1 fetches. (!!!)

Note: two L1 fetches would likely go into the reorder buffer and be out-of-ordered into an efficient manner. But... ignore that plz since that destroys the point I'm trying to make. Lol. Still, you can see how repeatedly forcing even L1 fetches would slow down the code, and "pointer chasing" is more likely to fill up the Reorder buffers, since you cannot rely upon prefetchers to pre-fetch the data, or other such tricks of the CPU.

Algorithmic complexity means that eventually, the linear / SIMD methodology eventually will be slower with a big-enough dataset. But when looking at small data-sets and optimizing them to the maximum ability (ie: searching 16-strings ASAP), linear / sequential scans are king. Kinda like why insertion sort ends up winning in a lot of small cases over other sorts. CPUs and RAM are incredibly well optimized for sequential data scans.

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

#42

Post by obl »

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?

in itself pointer chasing does not mean misusing CPU caches (your dataset could fit in cache and you could be pointer chasing inside it).

the main issue that is strictly due to pointer chasing is that you risk having long dependency chains in your instruction stream (address of the load depends on the result of the previous load, the address of which depends on the result of ...).

This is pretty bad for a modern CPU since a lot of the speed comes from overlapping independent computations.

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

#43

Post by jhallenworld »

trentnelson wrote: post #35
jhallenworld wrote: post #34

Earlier quoted context omitted.

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?

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 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 Processing

#45

Post by trentnelson »

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?

I think with SIMD type stuff and small data sets (e.g. Similarly, with SIMD and small data sets, you’re going to be faster than anything involving a pointer chasing data structure. Pointers tend to mean branchy-ness; they require more backend resources; they often introduce dependencies that can inhibit out of order pipelines.

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

#46

Post by trentnelson »

xenadu02 wrote: post #40
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 worl…

Heh, “predict the shit out of”, I like that.

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

#47

Post by trentnelson »

godelski wrote: post #44

I always love learning about performance and how this low level stuff works. Is there a book that people recommend for this type of stuff?

I bought a bunch of assembly/MASM books from the 90s recently, if that helps. Writing assembly is a skill that atrophies so quickly without constant exercise, so once you spool up to an acceptable level of assembly productivity, you really need to make a conscious effort keep practicing to maintain it.

If I go for a couple of weeks, I’ll come back and be like “wait, how do I check if this is a NULL pointer again?”.

The Computer Archtecture books are good, you can pick up 2nd hand copies of older versions for cheap. Intel and AMD manuals are good, too.

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

#49

Post by glangdale »

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…

Excellent! I built a string matcher based on these same principles at Intel while working on Hyperscan but never released it. I'm pleased to see that you have discovered and publicized this yourself as I can say the cat is out of the bag. :-)

You can use PEXT alone without even messing with SIMD as long as there's enough good distinguishing bits in the early (first/last 8) parts of the string. The only thing that complicates this is that, as in the example in the article, sometimes some strings are proper prefixes/suffixes of others (which one is problematic depends on which direction you're using).

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

#50

Post by glangdale »

This is fine work, and well presented. The only flaw (which I've discussed on Twitter with Trent) is the performance analysis against a single string at a time means we can't really analyze the effects of branch prediction on a realistic input (as the branch predictor will converge to 'perfection' almost immediately). I think these effects would be small, but it really does need to be properly analyzed.
Post reply on HN