Using SIMD for `string.h`

[ncruces]

I make a no-CGO Go SQLite driver, by compiling the amalgamation to Wasm, then loading the result with wazero.

To compile SQLite, I use wasi-sdk which uses wasi-libc, based on musl. I'd heard that musl is slow(er than glibc), which is true, to a point.

musl uses SWAR on a size_t to implement various functions in string.h. This is fine, except size_t is just 32-bit on Wasm, whereas most CPUs these days are 64-bit.

I found that implementing a few of those functions with Wasm SIMD128 can make them go around 4x faster.

Other functions don't even use SWAR; redoing those can make them 16x faster.

I found that using SIMD intrinsics (rather than SWAR) seemingly makes it easier to avoid UB, but the code would definitely benefit from more eyeballs. The code (MIT licensed) is at: https://github.com/ncruces/go-sqlite3/blob/main/sqlite3/libc/string.h

I also reimplemented qsort but that's another issue.

See this for some benchmarks on both x86-64 and Aarch64 (wazero only).

Reviewing this, testing it across other runtimes and platforms, figuring out where it fits and your build infra are all a significant time investment, so opening an issue just to see if there's even interest in something like this (and hopefully find if someone would be willing to pick up some of the work I'm less familiar with).

[sunfishcode]

This is cool, and I expect it's of interest to many wasi-libc users.

At a quick glance at the code, I have a few initial notes:

Since these routines do increase code size, would it make sense to enclose the SIMD code in #ifndef __OPTIMIZE_SIZE__?

For memcpy, memset``, and memmove, does implementing them using the _builtin*` form help? I expect clang should do that optimization automatically.

This approach of defining these functions in a header file has the convenient property that they won't require us to publish separate libc.a builds for simd128 and no-simd128, which seems like a good way to get started here. That said, it also does mean that when libc itself calls memcpy, it won't get the optimized form, because we don't currently build it with simd128 enabled. So we may eventually need to look at distributing separate libc.a builds for simd128 and no-simd128, as there are many engines out there that don't support simd128.

[ncruces]

This is cool, and I expect it's of interest to many wasi-libc users.

At a quick glance at the code, I have a few initial notes:

Thanks! I'll reply inline, not necessarily in order.

This approach of defining these functions in a header file has the convenient property that they won't require us to publish separate libc.a builds for simd128 and no-simd128, which seems like a good way to get started here.

I made these to use with SQLite, which concatenates all files in a single compilation unit, so a "single file" worked best for me. Then I adapted it to "header only" to try to make it useful for others who might be doing clang -I<dir> foo.c. But this isn't necessarily the best way to upstream these. Tbh, I don't know.

The goal of opening this issue was precisely to find out.

Since these routines do increase code size, would it make sense to enclose the SIMD code in #ifndef __OPTIMIZE_SIZE__?

They don't, necessarily. If you compare (e.g.) strlen (before, after) a few of these probably reduce code size. Overall a .wasm with just the functions from string.h goes down from ~3500 to ~3000 bytes; but I bet a few functions increase in size.

For memcpy, memset, and memmove, does implementing them using the __builtin_* form help? I expect clang should do that optimization automatically.

If you look at the .wat these calls just become memory.fill and memory.copy, which also means they're very likely to be inlined (if not by clang, by wasm-opt).

Again, I'm not necessarily claiming this is the best implementation for wasi-libc. You already have BULK_MEMORY_THRESHOLD, although I'm not sure that setting it to zero is enough to optimize the entire function away (I would've preferred n >= BULK_MEMORY_THRESHOLD).

But this implementation worked best for me. I can try to explain why. When you're copying/setting a known at compile time constant & small number of bytes, clang (regardless of how memcpy and friends are actually implemented) removes the entire call and replaces it with SIMD instructions to copy, which is great. So all that is left are copies by a dynamic number of bytes. And for my Wasm runtime at least, having a check at runtime really does not pay off.

[ncruces]

My suggestion for how to go about this, if you'd like to see this upstreamed, would be that you decide where the code for each function might go, and then I can try to make a separate PR for each function (or class of functions, some are very similar), where we can discuss the actual implementation, and I can document the rational for each approach.

I just wanted to first start a discussion and hopefully avoid wasting our time on misguided approaches.

[ncruces]

Added exhaustive tests of the more complicated functions (and caught a bug in memchr, which is the most challenging function). Also added a bunch of comments documenting the implementation of each function. I'm now reasonably confident these are correct.

[ncruces]

Added SIMD optimized versions of strspn/strcspn (link) and strstr/memmem (link with link). Credit for both these algorithms goes to @WojciechMula.

Fixed a few issues with C++, and got some additional functions (e.g. strncpy) to piggyback on these (now much faster) functions.

Numbers are rough, and only for wazero, but these should give you some indication of the benefits:

function	speedup
memchr	4.3×
memcmp	10.0×
strlen	4.9×
strchr	4.2×
strrchr	9.9×
strcmp	12.8×
strncmp	16.3×
strspn	9.1×
strcspn	9.7×
strstr	5.6×
geomean	7.8×

Feel free to use as is, or work on integration.

[ncruces]

Added case-insensitive compares (strcasecmp, strncasecmp, strcasestr) and fuzzed all the functions.

[abrown]

In talking to @alexcrichton, @sbc100, @sunfishcode, everyone was excited to see a PR for this. Here were several thoughts to get it upstreamed:

• it needs to be off-by-default behind a separate preprocessor macro
• it needs to be tested, at a minimum with libc-test (ping me if you need help bringing in those tests)

[ncruces]

I would need help with basically anything project related. I'm relatively proficient in C/++, but not necessarily build systems and project structure. That's also very opinionated, so naturally you should call the shots.

Would these continue to live in an header? If so, what folder? Single header or multiple? I'm not sure how well this distribution mechanism works. I mean, it works for me, but a friend tried to use this with a abseil and C++ project and failed.

I can definitely add a #ifdef STRING_SIMD_INTRINSICS or something. Should that be namespaced? There's BULK_MEMORY_THRESHOLD (no namespace) but that's not used in a public header (in fact I'm not even clear how that works with separate compilation, etc).

Same for tests. The code is actually well tested (I have unit tests, benchmarks, and plenty of fuzzing), but that's all in Go. Some tests may be hard to replicated from within the sandbox. For instance: I test with data at the very "far" edge of memory, but I can't force malloc to give me such memory.

[ncruces]

Added a README with updated rough numbers, and some algorithmic details.

[abrown]

@ncruces, it may be a good idea to shift the conversation to Zulip so we can hash out some of these details. I'm willing to help work with you on this there!

[ncruces]

I don't have an account, but I guess I can create one. Link me the chat/topic/? Other than that, I'll do my best, but I have lots on my plate, so I tend to work in bursts, when I have spare time.

[abrown]

Heh, whenever you have time is good — I appreciate your interest in bringing this here! You can probably log in to the Zulip instance using your GitHub ID and feel free to message me directly: abrown.