Wojciech Muła

One of my favourite articles is "SIMD-friendly algorithms for substring searching" by Wojciech Muła [2]. If you were unfamiliar with SIMD and just jumped into the code, it'd be incomprehensible due to the intrinsics, but the generic algorithm description at the top is pretty simple if you take some time understand it. It blew my mind once I understood what was happening, because it's quite clever but one of those "I could've thought of that" algorithms. There was some pretty good discussion on it last year (feat. ripgrep). [2] 1. http://0x80.pl/notesen/2016-11-28-simd-strfind.html 2. https://news.ycombinator.com/item?id=44274001

Maybe http://0x80.pl -- this site features mainly SIMD/SWAR code.

https://en.algorithmica.org/hpc/ and http://0x80.pl/ have some stuff about this, but the latter can be dense. I've had fun getting my hands dirty with some problems at https://highload.fun/ but there's not much direction unless you go to the telegram chat and ask people questions.

Wojciech Muła really groks SIMD. It's well worth exploring his other work in that area: http://0x80.pl/articles/index.html

There is more! You can be _faster_ than __builtin_popcount()! Wojciech Muła did an excellent SSSE3 implementation: http://0x80.pl/articles/sse-popcount.html My understanding is that the set-up time is slower than the POPCNT cpu instruction, but throughput is higher. Useful if you need to count bits not on a register, but on a whole array.

Reading http://0x80.pl/articles/sse-popcount.html, I would think the hardware instruction is slower than the best software implementation. Or has that changed on newer hardware?

I recommend reading over this: http://0x80.pl/articles/convert-to-bin.html btw all this SWAR stuff should be aligned before applying.

> Lookup tables are always faster than calculation - is that true? Maybe on the Z80. Contemporary RAM was quite fast compared to it, by our sad standards. A table lookup per byte will see you hit a pretty hard limit of about 1 cycle per byte on all x86 CPUs of the last decade. If you’re doing a state machine or a multistage table[1] where the next table index depends on both the next byte and the previous table value, you’ll be lucky to see half that. Outracing your SSD[2] you’re not, with this approach. If instead you can load a 64-bit chunk (or several!) at a time, you’ll have quite a bit of leeway to do some computation to it before you’re losing to the lookup table, especially considering you’ve got fast shifts and even multiplies (another difference from the Z80). And if you’re doing 128- or 256-bit vectors, you’ve got even more compute budget—but you’re also going to spend a good portion of it just shuffling the right bytes into the right positions. Ultimately, though, one of your best tools there is going to be ... an instruction that does 16 resp. 32 lookups in a 16-entry table at a time[3]. So no, if you want to be fast on longer pieces of data, in-memory tables are not your friend. On smaller data, with just a couple of lookups, they could be[4]. In any case, you need to be thinking about your code’s performance in detail for these things to matter—I can’t think of a situation where “prefer a lookup table” is a useful heuristic. “Consider a lookup table” (then…

Make sure to read the post linked right at the beginning as well: http://0x80.pl/notesen/2023-04-30-lookup-in-strings.html as well as the magic bitboards linked, too https://www.chessprogramming.org/Magic_Bitboards Though honestly this post really needed some numbers and benchmarks.

The SIMD string matching optimization unfortunately missed a trick -- it's more selective to match the first and last characters of a pattern than the first two, and it's the same cost. Credit to Muła for this one: http://0x80.pl/notesen/2016-11-28-simd-strfind.html#generic-sse-avx2 .

But that's slower for small query sizes. This describes a few algorithms: http://0x80.pl/notesen/2018-10-18-simd-byte-lookup.html Both the alternative version by Geoff Langdale, and the special case for small sets, are substantially similar to the algorithms used in Hyperscan (truffle and shufti). https://github.com/intel/hyperscan Having something hard coded for spaces can be much faster, especially since 5 of the 6 characters are a range: a wrap-around subtraction and an unsigned less-than does the first 5; an equality compare does the other.

Wasm intrinsics look neat as a higher-level fixed size SIMD abstraction. I wonder how good the compilers can do if using them for AOT targets with libraries like simd-everywhere. string.h is missing strstr(), there's an algorithm of similar complexity you might consider: http://0x80.pl/notesen/2016-11-28-simd-strfind.html

The RISC-V Vector article[0] on the same site is quite interesting as well. 0. http://0x80.pl/notesen/2024-11-09-riscv-vector-extension.html

Oh, I don't think it's a general principal, it's very processor architecture specific. But here's one example from earlier avx-supporting CPUs: http://0x80.pl/articles/sse-popcount.html

I think Wojciech Muła, who devised the original SIMD-oriented Rabin Karp algorithm, also did measure MPSADBW approaches and found that it is not a good fit for general string-in-string searches [1]. Maybe not today though. [1] http://0x80.pl/articles/simd-strfind.html#id7

Looks to be using a lot of similar ideas to the ones explained well in these articles: https://kholdstare.github.io/technical/2020/05/26/faster-integer-parsi… http://0x80.pl/articles/simd-parsing-int-sequences.html

Interesting and similar here is that there are a bunch of algorithms from days of yore that made sense with performance back then, but these days where the CPU absolutely doesn't care whether it's comparing a single byte or 32 bytes at once this can shift some algorithms towards much simpler ones. E.g. for substring searches this page is rather interesting: http://0x80.pl/articles/simd-strfind.html which posits that some of the older algorithms were built with the assumption that comparing parts of memory is more expensive than a table lookup, which is in many cases no longer true.

If you can confine yourself to a table of 16 byte values, then Intel SSE3's instruction pshufb can let you have a table in a register, with 16 parallel lookups in one clock cycle (assuming your input are the low nibbles in another SSE3 register). More here: http://www.0x80.pl/notesen/2016-03-13-simd-lookup-pshufb.html

See also http://0x80.pl/articles/simd-strfind.html The basic idea there is: - mask_start = (64 chars from idx i) & (first letter) - mask_end = (64 chars from idx i + len - 1) & (last letter) if mask_start & mask_end is nonzero, you can now memcmp at the nonzero mask indices (which could also be done with AVX512 if the needle length is big enough) That should give better performance for long needles, since you can immediately check 64 chars of the needle against the first character match, whereas OP's version does one load per needle character (ok, it does check multiple matches in a 64-char window in parallel though). I wonder though if Boyer-Moore type of optimizations are possible (e.g. if the match breaks at substring length i, that means you can skip forward j chars from a precomputed table)

Depends on your goals? If you'd like to contribute code under Apache2, I'd be happy to collaborate. Feel free to reach out to the email in the Highway README. Some of the things on my short to medium-term todo list include: - CompressStore for 8-bit lanes (before Icelake, that will likely require splitting up into runs of 8 bytes with one PSHUFB + store each) - also ExpandLoad (analogous to CompressStore) and LeadingZeroCount - the C++ STL isn't autovectorized much (http://0x80.pl/notesen/2021-01-18-autovectorization-gcc-clang.html). Manual vectorization can help, we have some of the simpler algorithms already in hwy/contrib/algo, others such as unique, reverse, minmax_element, all_of are more interesting.

Speaking of modern computers, have you compared it to these SIMD string find algorithms by Wojciech Muła? They're a bit more recent: http://0x80.pl/articles/simd-strfind.html

It does actually! But only in some cases. See https://github.com/BurntSushi/ripgrep/issues/617#issuecomment-35456811… and https://github.com/rust-lang/regex/issues/408 and https://github.com/rust-lang/regex/pull/419 Note though that it is going away soon. It's going to be replaced with a combination of Two-Way, Rabin-Karp and a fast vectorized prefilter based on this: http://0x80.pl/articles/simd-strfind.html#algorithm-1-generic-simd The "secret sauce" is that in the vectorized prefilter, we don't just choose the first and last bytes. Instead, we pick bytes that we think will be rare based on a priori assumption of relative byte frequencies.

Regarding the C++ version: instead of copying data to a vector and then sorting the vector, it might be more profitable to use std::multimap<size_t, string>. This is a sorted container (likely rb-tree based) that handles duplicated keys. Also, as somebody else mentioned, iostreams are slow. Even simple reading of file can be several times slower than plain C (http://0x80.pl/notesen/2019-01-07-cpp-read-file.html).

0.25s for 200MB (in memory) seems pretty slow for a modern CPU (800MB/s) which is more than an order of magnitude below what you would expect from main memory. There can be a lot of performance left on the table even in standard library implementations: http://0x80.pl/articles/simd-strfind.html

The latter is generally not faster on most modern chips. Results in similar microcode to non vectoring assembly, but you need to put data in the SSE registers which is not free. A smart compiler would not use the new SSE version. (perhaps you didn't set the flags right?) This is why: http://0x80.pl/articles/sse-popcount.html

I would expect it depends on where the lookup table enters the picture. If the table lookup is at the end of a dependency chain, it's not going to stall anything and then you're putting less strain on the branch predictor/reordering machinery. The article is using pext, which is different from a regular table lookup. While it has horrible latency and overhead on older chips, on Zen3 it appears to decode to a single uop with a latency of 3, and on Haswell it also decodes to one uop with a latency of 3. So it's not as bad as a regular table lookup as long as you're on a new enough processor. It's also possible to do vectorized lookup table loads if your lookup table is small enough and you have a modern CPU, see http://0x80.pl/notesen/2016-03-13-simd-lookup-pshufb.html and http://0x80.pl/notesen/2019-02-03-simd-switch-implementation.html (there's a more generalized version of this I can't remember the URL of...)

When you add prefetching (that is, compare against the middle element and fetch both the middle of the left half and the middle of the right half ahead of time) you are essentially doing radix-4 search, just with fewer actual comparisons. (You can prefetch k layers ahead for radix-2^k search, but searching in small arrays will become more expensive this way.) I didn't benchmark it, but I guess on mid-to-large arrays it would actually work somewhat slower than prefetching because it is more instruction-heavy, and, more importantly, prefetches are "cancelable": if the memory bus is too busy with actual requests, they will be skipped, while in explicit radix-k search you would have to wait for all (k-1) elements even if the middle element happened to be already cached and you already know which elements you need next. That said, it could probably work with small arrays where caching is not a concern and especially if you optimize for latency and not throughput. You can also try to do the comparisons with SIMD (Wojciech Mula tried something similar and got a small boost: http://0x80.pl/articles/simd-search.html).

> Ah, Highway is C++ so that won't work for you then. And indeed CMPISTR is quite nonportable. I'm curious whether you are getting good performance from CMPISTR relative to AVX2 or even AVX-512, for those who have it? Wider vectors might reduce the advantage of specialized instructions. The main advantage of pcmpistrm is that it doesn't need preprocessing. You can beat its raw speed just fine, e.g. using the Muła/Langdale algorithm (http://0x80.pl/articles/simd-byte-lookup.html), but that algorithm requires costly preprocessing of the set to be matched. For string functions, input strings are usually very short and algorithms have to be optimised for that case; the steady state of a tight main loop is rarely reached and not the primary goal of optimisation. So as a result, any preprocessing before we can get started walking down the string gets really expensive. In fact, the benchmarks I wrote and whose results the Phoronox page has shamelessly ripped off use strings of just 64 bytes on average, which I believe is more representative for real-world cases than the very long strings other implementations seemed to have been optimised for. This is also the reason why I ended up using just SSE: not only do the instructions provided by SSE2 largely suffice for the job, but also is the advantage of longer vectors severely reduced when your input is unlikely to be longer than one or two of them. Plus for AVX and later, we have to do a VZEROUPPER before return (to ensure…

x86 doesn't have thousands. That's overstating it by quite a bit. The assembler I wrote contains 1095 encodings. It's from ~2004 but 100% complete at the time, so sure new instructions have been added since. But those are encodings. SAL has like 8 encodings, SAR has 12, CMP has 14, etc. These encodings are just different ways to use the same opcode but with different source/target parameters (8/16/32-bit immediates or registers, etc.) Someone wrote a script that disassembled all the binaries on their Linux machine and counted the number of actual instructions used (mostly by gcc, of course). Only a tiny fraction of the total instructions were used: http://0x80.pl/notesen/2014-01-01-instruction-utilization.html Just take the top 30 of that chart and learn those. The x86 contains a lot of instructions that no one needs to worry about. Things related to the ancient segment mode or x87 floating point, OS-privileged instructions (context switching, HLT/LIDT/etc.), AMD-only 3DNow, etc. The ISA is not the hard part anyway. Dealing with the ABI (System V on Linux) to interface with C/C++ code, the kernel syscall interface, position independent code/executable (PIC/PIE) are somewhat bigger concerns and are going to apply to RISC as well.

use the popcnt instruction or the popcnt intrinsic function. It counts how many bits are set to 1, you’re looking for 0. You can also cast it into a uint64_t integer and do an equality test. There might be a way to use fused multiply add. Also are you mmaping the file so you can just read it directly as a single buffer? You should be able to madvise to free pages after they’ve been checked. PUSHFB can also be used. http://0x80.pl/articles/sse-popcount.html Essentially you want to vectorize this tho memcmp may already be vectorized and do the cpu detection. Edit: also… You should be able to load 15 x 256 bits and then test them. Try VPTEST https://www.intel.com/content/www/us/en/develop/documentation/cpp-comp…