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

21–30 of 61 posts

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

#21

Post by teraflop »

ridiculous_fish wrote: post #17
trentnelson wrote: post #10

Earlier quoted context omitted.

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, the…

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.

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 Processing

#22

Post by trentnelson »

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 assembly version, I'm all ears: http://trent.me/is-prefix-of-string-in-table/#IsPrefixOfStri...

All of the compress/expand routines mentioned in that Hacker's Delight section you're quoting seem to mention upwards of 160+ instructions. My negative match logic fast-path only requires 12 instructions.

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

#23

Post by ridiculous_fish »

teraflop wrote: post #21
ridiculous_fish wrote: post #17

Earlier quoted context omitted.

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.

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.

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.

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

#24

Post by trentnelson »

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) perk of religiously keeping line length to <= 80 characters... the code is surprisingly readable on mobile devices!

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

#25

Post by gameswithgo »

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…

On benefit of sticking with 16 bytes is it work on any 64bit machine, and as well you don't run into weird throttling issues that you do with AVX/AVX2/AVX512

So it is a lot easier to make something general purpose, where almost anyone can use it and it will always be faster.

With AVX you sometimes have to take some care.

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

#26

Post by dragontamer »

gameswithgo wrote: post #25
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…

On benefit of sticking with 16 bytes is it work on any 64bit machine, and as well you don't run into weird throttling issues that you do with AVX/AVX2/AVX512 So it is a lot easier to make something general purpose, where almost anyone can use it and it will always be faster. With AVX you sometimes have to take some care.

He's using the "v" instructions, which requires AVX, and probably AVX2 (I haven't memorized all the instructions... but they're at least AVX). Even if he sticks with 16-bytes, the use of the "v" instructions basically requires a relatively recent processor.

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

#27

Post by trentnelson »

dragontamer wrote: post #26
gameswithgo wrote: post #25

Earlier quoted context omitted.

On benefit of sticking with 16 bytes is it work on any 64bit machine, and as well you don't run into weird throttling issues that you do with AVX/AVX2/AVX512 So it is a lot easier to make something general purpose, where almost anyone can use it and it will always be faster. With AVX you sometimes have to take some care.

He's using the "v" instructions, which requires AVX, and probably AVX2 (I haven't memorized all the instructions... but they're at least AVX). Even if he sticks with 16-bytes, the use of the "v" instructions basically requires a relatively recent processor.

Yeah it's actually a pretty inconsistent mish-mash of ISA usage. I could go straight SSE4.x but I'd lose out on the vp* goodies you get with AVX and AVX2, even if I'm only using XMM registers.

The "length of 16, num elements is 16" parity is nice though and simplifies the logic of the algorithm.

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

#28

Post by trentnelson »

gameswithgo wrote: post #25
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…

On benefit of sticking with 16 bytes is it work on any 64bit machine, and as well you don't run into weird throttling issues that you do with AVX/AVX2/AVX512 So it is a lot easier to make something general purpose, where almost anyone can use it and it will always be faster. With AVX you sometimes have to take some care.

Yeah I generally agree with regards to throttling/caps/license issues, especially re: AVX-512. AVX and AVX2 aren't too bad though. I'm not using computationally-intensive AVX instructions, just your standard vectorized and/not/or/test/cmp/gt etc. These are incredibly cheap from a CPU cycle perspective.

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

#30

Post by garmaine »

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?
Post reply on HN