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

The overhead of dispatching a kernel to the GPU (and subsequent memory copy of the search string) would take tens of thousands (if not hundreds of thousands) of CPU cycles, so, it's not really applicable in this single-shot prefix lookup case.

Where it would be interesting: much larger prefix data sets (say, the name of all known cities, states, countries etc) and identifying where they occur in an even larger text corpus (like a wikipedia dump).

In that approach, you'd obviously compare against a multi-threaded CPU implementation... but, it'd be interesting to see the comparison.

However, they inevitably involve pointer chasing, are quite branchy, and not really amenable to SIMD optimizations. They also do not have any means in place for doing a fast-path negative match, which was important for me.

I think you'd really struggle to get anything based on pointer chasing and binary search to compete with the CPU cycle counts I was seeing toward the end for the assembly versions (e.g. 6 cycles for negative match, 14 for prefix match, 21 for worst-case false-positive negative match).

I comment a little bit about it here: http://trent.me/is-prefix-of-string-in-table/#other-applicat...

> The other nice side-effect is that it forces you to pick which table a given string should go in. I made this decision by looking at which types occurred most frequently, and simply put those in the first table. Less frequent types go in subsequent tables.

> I have a hunch there's a lot of mileage in that approach; that is, linear scanning an array of string tables until a match is found. There will be an inflection point where some form of a log(n) binary tree search will perform better overall, but it would be very interesting to see how many strings you need to potentially match against before that point is hit.

> Unless the likelihood of matching any given string in your set is completely random, by ordering the strings in your tables by how frequently they occur, the amortized cost of parsing a chunk of text would be very competitive using this approach, I would think.

> A fun experiment for next time, perhaps!

Some constructive feedback: move that information up to the "Goal" section, maybe with a motivating example. The fact that the set size is <= 16 is important to know before discussing cycle counts.

Yeah, my target use case rarely had strings longer than 16 (which is quite common for prefix matching problems in the real world), so, 16 made the most sense. I'll probably do an AVX2 and AVX-512 version down the track; as I'll have 32-byte and 64-byte registers to play with, it will allow me to do some more interesting things (either longer prefix strings, or more comparisons).

> * SSE4.2 has string-specific instructions. Did you look into any of the SSE4.2 string instructions to see if they'd help in your case? (Ironically, forcing you back down to xmm registers, since its SSE only. So kind of a contradiction with my first question, lol) I fully admit that I don't actually know how to use the SSE4.2 string instructions, so don't look into my question too hard.

The instructions like pcmpistri were considered and explicitly rejected :-) They are surprisingly slow, and they only process 16 characters at a time, so you don't get the implicit benefits on longer strings that you would expect if you could do like a `rep pcmpistri` or something (like the accelerated `rep stosq` etc).

The first twelve instructions for the negative match logic execute in about 6 CPU cycles. A pcmpistri-type instruction will often clock in around 7-14 cycles. So, with my approach, using the "basically free" instructions like vpcmpeqb, vpcmpgtb etc, I can detect if my input string doesn't have any prefix matches in a table of 16 prefixes in ~6 cycles, which is pretty neat.