I also have a favourite string matching algorithm, the "Generic SIMD" from this post [1] by Wojciech Muła (I haven't really read the other two SIMD algorithms since I wasn't planning on working with intrinsics).
There were some good comments that post's thread [2], including from burntsushi of ripgrep.
I've also implemented a SIMD accelerated, but case in-sensitive (*) search algorithm as an stb-style single header library, also based on Wojciech Muła's work.
See the performance comparison in the README, it's about 6 times faster than libc.
(*) - full UTF-8 support, but only works for UNICODE codepoints where the UTF-8 encoding lengths are the same for lowercase and uppercase. There are only 27 out of 40576 pairs which aren't handled (listed in the README).
> UNICODE codepoints where the UTF-8 encoding lengths are the same for lowercase and uppercase.
This very same property got me to post this [1], which sent me down the rabbithole of learning about Unicode in earnest and building my Unicode tool. Which may have an initial release some time this millennia... maybe.
I like burntsushi's string-searching work because it's well documented, split modularly into libraries/applications, and runs the gamut from low- to high-level (his blog posts and comments online are extremely helpful too). I use these three tools which he maintains:
Low level: memchr [1];
Medium level: Regex (Rust crate) [2];
High level: ripgrep [3].
Other names to look out for are the previously aforementioned Wojciech Muła, as well as Daniel Lemire (of simdjson [4][5]). Not SIMD-specific, but Data-Oriented Design can be a big help in terms of thinking about SIMD and cache-friendly data layout (as well as trimming down the work that the computer needs to do, generally). I've talked that to death, so I'll just link those comments here [6].
Ah, last weekend I was just updating my own string search algorithm to use Bitap (Shift-OR variant) instead of KMP, when the pattern length is < 64. It is faster. It is a very lovely algorithm indeed.
My search algorithm, HashChain [1] is a very fast sublinear algorithm, but is uses KMP (and now Bitap) to verify matches so it has a linear worst case (instead of quadratic, like Boyer Moore Horspool).
It is a really nice derivation of Bitap from first principles. I had not seen that before. Good job!
One small nit: he says the naive algorithm is linear - maybe it is for the average case, but it has a quadratic worst case complexity. Bitap is linear even for worst case.
I can see how this could be advantageous for moderate length patterns up to 64 bytes.
But for short registered sized patterns (4 or 8 bytes), I am somewhat skeptical of any significant advantage over a very tight, brute force register based loop comparing multi-byte chunks.
(OP here.) You're correct that for short patterns there's little advantage over the brute-force algorithm, and in fact the brute-force algorithm should actually be faster in many cases. Indeed the per-iteration comparison against the pattern in the brute-force algorithm is essentially a memcmp, which is vectorized and runs very fast on modern hardware. Consequently all mainstream programming languages that I know of just use the brute-force algorithm as a fallback when the pattern is short, as opposed to something more complicated like bitap.
I tried to be fairly careful to not overstate the performance benefits in the original post for this reason.
Ok, so why not use a fast memcmp on the first 4-8 chars of the pattern to identify any potential match and once found, work from there to verify if a full match exists?
This is essentially what I have have been doing for years and it is very simple. I'm sure it is not always the fastest but it's not too shabby either in the real world.
I also have a favourite string matching algorithm, the "Generic SIMD" from this post [1] by Wojciech Muła (I haven't really read the other two SIMD algorithms since I wasn't planning on working with intrinsics).
There were some good comments that post's thread [2], including from burntsushi of ripgrep.
1. http://0x80.pl/notesen/2016-11-28-simd-strfind.html
2. https://news.ycombinator.com/item?id=44274001
I've also implemented a SIMD accelerated, but case in-sensitive (*) search algorithm as an stb-style single header library, also based on Wojciech Muła's work.
https://gitlab.com/bztsrc/fast_memcasemem
See the performance comparison in the README, it's about 6 times faster than libc.
(*) - full UTF-8 support, but only works for UNICODE codepoints where the UTF-8 encoding lengths are the same for lowercase and uppercase. There are only 27 out of 40576 pairs which aren't handled (listed in the README).
> UNICODE codepoints where the UTF-8 encoding lengths are the same for lowercase and uppercase.
This very same property got me to post this [1], which sent me down the rabbithole of learning about Unicode in earnest and building my Unicode tool. Which may have an initial release some time this millennia... maybe.
1. https://news.ycombinator.com/item?id=42014045
Always been interested in using SIMD to speed up searching. So far though i have not found a really nice one.
Need to figure out what area they excel in - there is no one search that is the best for all types of data and pattern/search length.
I like burntsushi's string-searching work because it's well documented, split modularly into libraries/applications, and runs the gamut from low- to high-level (his blog posts and comments online are extremely helpful too). I use these three tools which he maintains:
Low level: memchr [1];
Medium level: Regex (Rust crate) [2];
High level: ripgrep [3].
Other names to look out for are the previously aforementioned Wojciech Muła, as well as Daniel Lemire (of simdjson [4][5]). Not SIMD-specific, but Data-Oriented Design can be a big help in terms of thinking about SIMD and cache-friendly data layout (as well as trimming down the work that the computer needs to do, generally). I've talked that to death, so I'll just link those comments here [6].
1. https://docs.rs/memchr/latest/memchr/
2. https://docs.rs/regex/latest/regex/
3. https://github.com/burntsushi/ripgrep
4. https://www.youtube.com/watch?v=wlvKAT7SZIQ
5. https://arxiv.org/pdf/1902.08318
6. https://hn.algolia.com/?dateRange=all&page=0&prefix=true&que...
Ah, last weekend I was just updating my own string search algorithm to use Bitap (Shift-OR variant) instead of KMP, when the pattern length is < 64. It is faster. It is a very lovely algorithm indeed.
My search algorithm, HashChain [1] is a very fast sublinear algorithm, but is uses KMP (and now Bitap) to verify matches so it has a linear worst case (instead of quadratic, like Boyer Moore Horspool).
[1] https://github.com/nishihatapalmer/HashChain
It is a really nice derivation of Bitap from first principles. I had not seen that before. Good job!
One small nit: he says the naive algorithm is linear - maybe it is for the average case, but it has a quadratic worst case complexity. Bitap is linear even for worst case.
Interesting algorithm.
I can see how this could be advantageous for moderate length patterns up to 64 bytes.
But for short registered sized patterns (4 or 8 bytes), I am somewhat skeptical of any significant advantage over a very tight, brute force register based loop comparing multi-byte chunks.
(OP here.) You're correct that for short patterns there's little advantage over the brute-force algorithm, and in fact the brute-force algorithm should actually be faster in many cases. Indeed the per-iteration comparison against the pattern in the brute-force algorithm is essentially a memcmp, which is vectorized and runs very fast on modern hardware. Consequently all mainstream programming languages that I know of just use the brute-force algorithm as a fallback when the pattern is short, as opposed to something more complicated like bitap.
I tried to be fairly careful to not overstate the performance benefits in the original post for this reason.
Ok, so why not use a fast memcmp on the first 4-8 chars of the pattern to identify any potential match and once found, work from there to verify if a full match exists?
This is essentially what I have have been doing for years and it is very simple. I'm sure it is not always the fastest but it's not too shabby either in the real world.