TL;DR: I’m looking for a SIMD abstraction layer that will let me do some high-speed byte searching without having to worry about a dozen different instruction sets. Not having luck finding such.
I’m optimizing some JSON-parsing code, and by far the biggest bottleneck is string searching, specifically searching for the next occurrence of one of two or more characters. For example, when scanning a string I search for both double-quote and backslash. (Plus 00 if the JSON has not been validated.)
Yesterday I was experimenting with Apple’s “simd” library, which is based on Clang vector extensions, and it does pretty well, but I am not sure if this is portable to non-Apple systems or non-Clang compilers. (GCC has its own extensions, which Clang partially supports, but when I tried those Clang generated slow non-SIMD code.)
Often this trick works:
This thread gives an example of this technique in Rust:
This even works with runtime-detection of available SIMD instructions, you just need to convince the compiler to codegen several copies of function for different target features.
That sounds like the idiom I got from sa-json, which in my code I abstracted as:
This is what I’m currently using, as I haven’t gotten anything else to run faster. I tried unrolling it further, to 8 lines, but that was slower. (On my computer, which is a MacBook Pro with an M1 Pro.)
I’m able to parse+validate JSON at up to 2GB/sec depending on the input file, so it’s not too shabby.
The right way to answer these kinds of questions is to look at godbolt, but, as this is a template and I can’t just paste it into the compiler explorer as is, I would hazard a guess instead!
My gut feel is that the compiler would have trouble with those early breaks — as written, the code has the property that it doesn’t load any bytes past the matched character, and auto-vectorized version would do a bit of an over-read here. This should be equivalent, but I think as of today clang has trouble seeing that (again, as I haven’t looked at the assembly here, this is a wild speculation and is probably wrong). So I’d try to help the compiler a little bit more here, by making the code branchless.
Applying the trick in Rust seems to help relative to Rust version with manual unrolling
Full benchmark here:
And here’s godbolt of manually unrolled loop with branchless chunked:
You can see that the former has a bunch of funky vector instructions like
vpmovmskb, while the latter is, well, an unrolled loop.
I am only 0.7 sure that the results would be the same for C++, but, if godbolt for your version doesn’t actually include a lot of vector instructions, than its 0.95 that a massive improvement is possible!
NINJAEDIT: changed the commit, as the first version of the code didn’t actually auto-vectorized and contained memchr calls.
Possibly a naive question, but how/where do you make sure that the
p[n]dereferences are valid? Is this encoded in the predicate, where it will at least be valid once?
The predicate is assumed to be true at least once before the end of the data — either the predicate checks for a 00 sentinel, or the data’s already been validated to contain what it’s looking for.
My understanding (not a Rust expert) is that this is achieved using the
chunks_exactslice iterator which only looks at the part of the buffer that’s evenly divisible by the chunk size. I assume dealing with the remainder is left as an exercise to the reader. (Or the calling code can arrange to make the buffer an evenly divisible size, padded out with nul bytes - usually the cleanest option when doing SIMD if you can somehow pull it off.)
The code I was commenting on is C++, though.
Modern compilers are pretty good at vectorising if they can prove that things don’t alias and are adequately aligned. I’ve had both gcc and clang generate better code by adding restrict and alignas in places than by manually vectorising. There’s also the vector attribute that gives you primitive operations on vector types. There’s also an OpenMP simd pragma that basically says ‘skip the analysis, I promise it’s safe to vectorise’.
Would Intel’s ISPC be at the right level of abstraction for you? (As well as x86 it also targets NEON. Many major OSes are supported.)
Interesting! It would require writing the code in their custom C-like language; I wonder how much of the core parsing I could put in there, and how much it could speed it up. Thanks for the link.
simd everywhere may be of interest
In Julia you could use the SIMD.jl package to do SIMD manually while also abstracting across different processor types. Or you could use Metal.jl to create arrays on the M1’s GPU and perform operations on it pretty easily. Or you could use LoopVectorization.jl and have the library and the compiler be very free with rewriting standard for loops that you prefix with a macro.
OK, but this is C++ and will be used in a bigger C++ and/or Go project.
Cool, well nevermind :)
Careful with this one. I’ve had performance regressions by measuring this in isolation, seeing that the lookup table version was “faster” and so switching to it, but then later discovering that in the actual situation that code runs in, it was significantly slower than straightforward comparisons because the cache behaviour is worse.
Assuming that micro-benchmarks reflect reality can be trouble.
Hm, does parsing a 35MB file still count as a micro-benchmark? I’m testing with a dozen or so files of up to that size.
In actual use, some of the work will be a single scan through potentially-large data (validating / indexing the JSON), followed by smaller scans of subranges of the data for individual queries. The latter might expose the kind of cache slowdown you describe, but how to account for that in tests?
I’ve also considered making the LUT a bit-vector rather than a byte-vector, so only 32 bytes instead of 256 at the expense of some extra bit-twiddling, but I haven’t benchmarked that.
Doing full parsing with large files is probably fine, I’d say. An obvious micro-benchmark would be just benchmarking that function itself, although It Depends. Parsing and just throwing everything away might be a bit different from parsing and actually using the data for something in an application, like loading it into a data structure. Data aside, you can also get “fun” effects from the instruction cache when different approaches have different amounts of code that lives in different places.