Rapidstring: Maybe the fastest string library ever
github.com
github.com
If any of you have some questions or feedback, I would be delighted to hear it.
Very nice and thoroughly documented code! Well done! What gave you the initial idea to write this maybe-fastest-ever string library? Did you just have an idea one day of how it could be done and you just went for it? Or did you have a performance issue and come up with this to speed something up at work, or what?
I had a bit of trouble finding stuff in the documentation at first. You direct people towards Modules on the very first line of the Main Page but it's too subtle. When scanning the page looking for how to get to the list of all the classes and functions in the project, my eyes are drawn to the headings which are basically all irrelevant. It would help to add some headings beyond the autogenerated ones, and to provide a link from the struct documentation to set of functions that manipulate that struct (if possible). Additionally, the top of every page says "rapidstring 0.1.0" and I'm not sure what that number means. The version is listed on the main page as 1.0.0.
The documentation is well-written, which I think is a really good sign, and the problems I mentioned are only really an issue for the very first time somebody tries to use the documentation.
But it's still just a membuf library, without any string support. No encoding, no Unicode, no upper/lower/fc/norm support, which would be important to compare or find strings. And coreutils (e.g grep) still have no unicode support. It's 2018, not the seventies anymore. Unicode strings need to be normalized to be able to be found.
It's like saying you have the fastest integer math library ever written, with the minor caveat that it only supports numbers smaller than 256 because it achieves that speed by being simply a hardcoded lookup table, and crashes if you give it anything else.
Of the functions that take strings, the old ...A() versions should never be called anyway since they depend on the obsolete concept of code pages. The proper way to work with strings on Windows (IMHO) is to encode all string data to UTF-8, only encode/decode from/to UCS-2 when needed, and call the ...W() functions explicitely (don't use the global UNICODE define).
Also see: http://utf8everywhere.org/
And with case-insensitivity it gets worse, as there are some locale dependent additional rules, for Turkish and Lithuania. And this depends on "some" global settings.
Tbh I just stopped caring and now happily live in my little world where utf8 is the solution to everything, doesn't yield any problems ever, and anyone telling me differently gets completely ignored.
* Receives a string expected to be encoded in UTF-8, and an offset to it expected to be a UTF-8 sequence boundary.
* Scans forward or backward for the next or previous UTF-8 sequence boundary.
* Optionally returns the code point for the scanned UTF-8 sequence.
* Has proper error handling for every imaginable cases: out of boundary, not a boundary, not a valid UTF-8 sequence. (OOB case needs to be handled because it will be the end condition of the iteration. Preferably should be distinct from other error conditions.)
Every other functionality can build upon this little function, in particular the iteration and UTF-8 validation will be trivial. The full Unicode support including case mapping, folding, normalization and property lookup will of course require a not-so-small table but is not strictly necessary anyway.
Björn Höhrmann's Flexible and Economical UTF-8 Decoder [1] will be handy for a concise implementation.
And it's not easy. I implemented the third of its kind. First there was ICU, which is overly bloated. You don't need 30MB for a simple string libc. Then there is libunistring which has overly slow iterators, so not usable for coreutils. And then there's my safelibc, which is small and fast, but only for wide-chars, not utf-8.
I fixed and updated the musl case-mapping, making it 2x faster, but this is not in yet. And there's not even a properly spec'ed wcscmp/wcsicmp to find strings. glibc is an overall mess. I won't touch that. wcsicmp/wcsfc/wcsnorm are not even in POSIX.
In computer jargon I believe CISC and the PDP-11 have seniority. That's why all multi-word functions like memcpy are in C's string.h header.
I admit two words "string" and "text" are now interchangable. But that doesn't make strings have less requirements, people are just expecting more out of strings.
Just like the strings in the C and C++ standard library.
It's a mess and a big security risk. We are still in the stone age of string support.
1. ShiftOr for short strings. Easy to implement.
This algorithm is not sub-linear like Boyer Moore - it examines every position, but it uses bit-parallelism to validate a match, making it outperform algorithms that rely on jumping then separate verification stages, for short strings.
2. Variants of Wu-Manber for longer strings. Hard to find a good description, but not too hard to implement.
Wu-Manber is a search algorithm designed for multi-pattern searching, based on Boyer-Moore-Horspool and hashes. However, it also performs really well for single-pattern searching. I have encountered variants of this in various places, e.g. Lecroq's in "Fast Exact String Matching Algorithms".
These algorithms use a hash of a q-gram to look up how far it's safe to shift. Q-grams tend to appear less frequently in search patterns vs. single characters, so you get longer jumps, at the cost of reading more characters and producing a hash.
3. Horspool (or Boyer-Moore-Horspool).
This algorithm performs quite well - not as well as ShiftOr for shorter patterns or Wu-Manber variants for longer ones, but still respectable. It's essentially Boyer-Moore but only using one of the shift tables, which makes it much easier to implement.
4. Qgram-Filtering by Branislav Durian, Hannu Peltola, Leena Salmela and Jorma Tarhio
For longer patterns, this algorithm outperforms the others mostly. However, it can be a bit complicated to implement well, and it has some nasty worst-cases (rarely encountered) where the performance becomes absolutely dreadful. For that reason I tend not to use it.
There are hundreds of possible search algorithms available now (see https://github.com/smart-tool/smart for implementations of many of them with a benchmark tool). However, it's hard to figure out exactly which algorithm is the best given your data and pattern. For that reason, I tend to keep things simple.
I would just use ShiftOr for short patterns, and another one for longer patterns. I would tend to use a Wu-Manber variant there, but Horspool would probably give acceptable performance.
The only other consideration is the time it takes to build the pattern indexes. For short searches, or if you have to re-build the pattern index on each repeated search, it can actually be quicker to just do a naive "check the string at each position" search, since it doesn't require building anything before searching.
In any case, if you'd like to discuss search algorithms when you want to implement them, I'd be happy to help. I'm mattpalms, gmail.com.
Picking the right byte can be tricky, but a static common sense ranking actually works quite well. At least, the users of ripgrep seem to think so. :-)
For some reason, I've never seen this algorithm described in the literature. It doesn't have nice theoretical properties, but it's quite practical.
That said it’s much easier to make faster than libN string libraries if you don’t have abi constraints to deal with.
This uses any value struct to hold much of its metadata which causes all sorts of abi issues - basically, if your own app uses this it can’t expose it to plugins or anything, otherwise any update could break existing compiled plugins.
Why would you store the size and capacity as part of the buffer? It makes the buffer more complex (you need a separate unsized struct or some mess special-casing the first 16 bytes or so), wastes heap size, requires dereferencing before you can even check on size & capacity, and makes SSO harder/more limited.
AFAIK both C++'s std::string and Rust's String store size and capacity on the stack, separate from the buffer.
To decrease the memory footprint of your small strings. It can see how some uses cases where a large proportion of strings are very small would benefit from it.
I was just curious to know if that design decision was based on analysis of a real use case, or if it was due to a compatibility issue or something.
If you do that you have to spill your SSO to the heap way earlier, rapidstring would have 15 bytes SSO instead of the current 31, and std::string would be limited to 7 compared to the current 23~31.
If you're coming from a GC'd language like Java, Ruby, etc, then there's a bit of a mindset shift around strings.