Bitap: My favorite string matching algorithm(jo3-l.dev) |
Bitap: My favorite string matching algorithm(jo3-l.dev) |
There were some good comments that post's thread [2], including from burntsushi of ripgrep.
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...
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.
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).
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.
Sometimes there's an offset (like with Latin, +/- 32), sometimes lowercase and uppercase is interleaved (eg. Latin extended), and sometimes they are in totally different blocks simply because they forgot to add both letter cases at once... (the distance of the codepoints affects UTF-8 encoding difference the most).
I've also paid attention to optimize the most common case where both UTF-8 encodings' first bytes are the same (that's 40508 pairs out of 40549). But no escape, it must handle the remaining 41 pairs specially in a slower code path, which would not be needed at all should UNICODE guys did their homework better.
Lots to read about here for those interested (and that's without getting into `Casefold`, `NFKC_Casefold`, simple vs complex case mappings, the CLDR, etc.):
https://www.unicode.org/versions/Unicode17.0.0/core-spec/cha...
1. Linearity - the naive approach is quadratic on worst case data (imagine searching for 100 0's in a text of 0's).
2. Sublinearity - sublinear search algorithms skip over text that cannot match. They typically have the somewhat counter-intuitive property that they get much faster the longer the pattern is. So long patterns will be faster using a sub linear search algorithm.
Most of the everyday searching and parsing that I end up doing involves relatively short patterns. Maybe I am an outlier :-)