News for hackers. Stuff that matters.
Re:Is Prefix of String in Table? a Journey into SIMD String... by trentnelson on Monday May 14, 2018 @12:17PM (#17066731)
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.

Re:Is Prefix of String in Table? a Journey into SIMD String... by ridiculous_fish on Monday May 14, 2018 @01:21PM (#17067345)
Ok, I see further down the article does describe some of the assumptions: short strings, very small set size, optimized for negative matching.

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.

Re:Is Prefix of String in Table? a Journey into SIMD String... by teraflop on Monday May 14, 2018 @02:07PM (#17067879)
It's in the third paragraph of the article:

> A SIMD-friendly C structure called STRING_TABLE was derived. It is optimized for up to 16 strings, ideally of length less than or equal 16 characters.

Re:Is Prefix of String in Table? a Journey into SIMD String... by ridiculous_fish on Monday May 14, 2018 @02:31PM (#17068127)
I understood this to mean that the input would be processed in chunks of 16 (as is common with SIMD), not that the total input size was <= 16.