News for hackers. Stuff that matters.
Re:Is Prefix of String in Table? a Journey into SIMD String... by dragontamer on Monday May 14, 2018 @01:40PM (#17067553)
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-optimize "strings of length 16" instead of "strings of length 32" ?? The vast majority of your code uses "xmm" registers (16-bytes), but it would seem like it'd be straightforward to target ymm registers (32-bytes) instead.

Were there any particular reason why you chose 16-bytes instead of 32-bytes? Like maybe targeting AVX but not AVX2?? (Then again, I see a rare ymm register here and there... sooo... I guess I'm just a bit confused with the design decision)

* 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.

------------

I'll have to spend some time studying your code and explanation. Thank you very much for the writeup! It will be helpful for my SIMD-studies. There really isn't enough material out there on AVX / SSE optimizations.

Re:Is Prefix of String in Table? a Journey into SIMD String... by trentnelson on Monday May 14, 2018 @01:52PM (#17067703)
> Were there any particular reason why you chose 16-bytes instead of 32-bytes? Like maybe targeting AVX but not AVX2?? (Then again, I see a rare ymm register here and there... sooo... I guess I'm just a bit confused with the design decision)

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.

Re:Is Prefix of String in Table? a Journey into SIMD String... by gameswithgo on Monday May 14, 2018 @02:56PM (#17068357)
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... by dragontamer on Monday May 14, 2018 @03:07PM (#17068457)
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... by trentnelson on Monday May 14, 2018 @03:12PM (#17068501)
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... by trentnelson on Monday May 14, 2018 @03:15PM (#17068523)
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... by gumby on Monday May 14, 2018 @04:03PM (#17068950)
Note that some of the AVX instructions will slow down the rest of your CPU -- not a reason to avoid them, but you you need to understand your workload (you can't just throw them willy-nilly into the code path).