Rendered at 22:32:46 GMT+0000 (Coordinated Universal Time) with Cloudflare Workers.
Rendello 18 hours ago [-]
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).
Rendello 5 hours ago [-]
> 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.
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.
Rendello 6 hours ago [-]
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.
jqpabc123 5 hours ago [-]
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.
jo3_l 4 hours ago [-]
(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.
jqpabc123 3 hours ago [-]
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.
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
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).
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
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.
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...
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
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.
I tried to be fairly careful to not overstate the performance benefits in the original post for this reason.
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.