51–60 of 62 posts
Earlier quoted context omitted.
It is a trade off. I see the length limit is 23 for SSO-23, but it could have been arbitrarily larger. What is the basis for the determination of those magic length limit targets?
The size of the pre-existing non-SSO string. SSO-23 is predicated on a stack layout of (pointer, capacity, size) (as in Clang). That's why SSO-23 applied to the pre-existing MSVC or GCC std::string yields 31 on-stack bytes, they have a stack size of 32 bytes.
Earlier quoted context omitted.
True, but sadly no relation in this case, it appears.
As it turns out, I actually have the Boyer-Moore string searching algorithm as one of the planned features in the Project section on GitHub.
Hey there, creator of the library here. Strangely enough my initial post about this on HN received no attention, but better late than never! If any of you have some questions or feedback, I would be delighted to hear it.
I like it. That's a good set of principles and a very clean API. 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 t…
Earlier quoted context omitted.
As it turns out, I actually have the Boyer-Moore string searching algorithm as one of the planned features in the Project section on GitHub.
Boyer Moore is OK, but there are better algorithms available. The simpler Horspool variant is usually a fair bit faster and also easier to implement. For short strings, e.g. less than 12 character, the ShiftOr algorithm is hard to beat. I've spent quite a bit of time writing and profiling different search algorithms as part of the byteseek project on GitHub. Let me know if you'd like details on other possible options…
Earlier quoted context omitted.
Boyer Moore is OK, but there are better algorithms available. The simpler Horspool variant is usually a fair bit faster and also easier to implement. For short strings, e.g. less than 12 character, the ShiftOr algorithm is hard to beat. I've spent quite a bit of time writing and profiling different search algorithms as part of the byteseek project on GitHub. Let me know if you'd like details on other possible options…
I would most definitely be interested. I always assumed that certain algorithms are better suited for certain string sizes, but I was never sure which ones. The ideal implementation is probably combining multiple algorithms with ranges of the string size.
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.
Earlier quoted context omitted.
True, but sadly no relation in this case, it appears.
As it turns out, I actually have the Boyer-Moore string searching algorithm as one of the planned features in the Project section on GitHub.
Earlier quoted context omitted.
Hey man don't worry about that, that's just the way of life. People notice things when they do, that part's not up to us. I've seen articles here posted years after they were written. 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 p…
I just really needed a string library written in C, and it didn't seem as though there were many options. The first thing I found was the Simple Dynamic Strings library, but it wasn't maintained and depended on GCC extensions, so I decided to write my own. After getting a basic functional concatenation, I benchmarked it against std::string to see how slow it was, and to my great surprise, it was actually faster. From…
Earlier quoted context omitted.
I like it. That's a good set of principles and a very clean API. 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 t…
Thanks for the feedback! I did forget to change the version in the documentation, updated that now. As for the usability of the docs, Doxygen isn't exactly known for its intuitive user interface, but I will try my best to make it easier to navigate.
Earlier quoted context omitted.
I would most definitely be interested. I always assumed that certain algorithms are better suited for certain string sizes, but I was never sure which ones. The ideal implementation is probably combining multiple algorithms with ranges of the string size.
Absolutely true that there isn't a single algorithm that beats all the others. Of the general string search algorithms which don't use specialized CPU instructions to obtain speedups, I would recommend: 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 re…
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.
Earlier quoted context omitted.
I don't see any functions in the OP's library that would require dedicated UTF-8 handling. The string length is given in bytes, not characters or codepoints. There's no functionality to give you the character at n-th location etc... you can easily implement all UNICODE-specific functionality in a separate library and use it together with the OPs library. IMHO that's even preferable.
Yes, but don't call it string library then. Strings should handle strings, and strings are unicode now. Unicode needs to be normalized and needs case-insensitive support. 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 the…
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.