Rapidstring: Maybe the fastest string library ever

Post by lifthrasiir » Thu, Aug 02, 2018, 5:25 AM UTC

zlynx wrote: post #60

rurban wrote: post #37

Earlier quoted context omitted.

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…

Why try to redefine the word "string?" 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.

Hey, even C contains a locale-dependent string comparison, namely `strcoll` (since 1990!).

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.

Post by burntsushi » Tue, Aug 07, 2018, 1:08 AM UTC

MattPalmer1086 wrote: post #55

johnboyer wrote: post #54

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 my experience, it is difficult to beat a very simple heuristic in most settings: when provided a string, pick the most infrequently occurring byte in that string, and use that as your skip loop in a vector optimized routine such as memchr. If you guess the right byte, you'll spend most of your time in a highly optimized routine that makes the most out of your CPU.

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.

Re: Rapidstring: Maybe the fastest string library ever

Re: Rapidstring: Maybe the fastest string library ever