3 ms·

Sure, if you make a bunch of assumptions and manually implement how you think a regex will compile your code, allowing the optimizer to take your compile time i

by Kranar 1y ago

Sure, if you make a bunch of assumptions and manually implement how you think a regex will compile your code, allowing the optimizer to take your compile time implementation and make a finely tuned algorithm specifically for one use case, you can make something that outperforms what is kind of a dumb algorithm. But if you use an actual regex the way people actually use them, using either the one provided by their standard library or one that is readily available then regex is pretty slow. Certainly, in principle a regex is neither fast or slow, it's a declarative description of a set of strings. Any claim about its performance rests on particular implementations. For example you wrote out a benchmark that presumably is a lot faster than a naive search... but notice you didn't use the standard library <regex>, instead you manually implemented an algorithm to perform a search and then just decided that this is what a regex implementation would have done anyways (ignoring that by implementing it directly in source code, the optimizer can then fine tune it). So now... there is a 10% chance that you genuinely didn't know that C++ has a <regex> library that you could have used, or you did in fact know that C++ has such a library and you chose not to you use it because... you also know it's very slow. I did the benchmark myself using the standard library regex, boost regex, and PCRE2 regex, and all of them are about 5-15x slower than the simple loop: https://gist.github.com/kranar/a3187cba00d57ba630b74b84f09b4c07 https://gist.github.com/kranar/a3187cba00d57ba630b74b84f09b4...

tylerhou 1y ago
> Sure, if you make a bunch of assumptions and manually implement how you think a regex will compile your code, allowing the optimizer to take your compile time implementation and make a finely tuned algorithm specifically for one use case, But that's not what is happening. The only thing that the optimizer does is unrolls the loop that advances the state. Otherwise, the sequence of instructions is standard: two loads and some pointer arithmetic. There is no finely tuned algorithm. https://godbolt.org/z/fqdb5bssc https://godbolt.org/z/fqdb5bssc > But if you use an actual regex the way people actually use them, using either the one provided by their standard library or one that is readily available then regex is pretty slow. Yes, most regex implementations are not designed to be efficient, they are designed for ergonomics (including supporting exponential-time features like lookaround). (Both boost::regex and PCRE2 support exponential-time features; std::regex is just not optimized at all.) This is well-known. https://swtch.com/~rsc/regexp/regexp1.html https://swtch.com/~rsc/regexp/regexp1.html. That's why I said "well-optimized regex." Most regexes, in practice, are not well-optimized! Maybe this is a semantic distinction between what you and I consider a "regex." I interpreted "regex" as how people in CS theory understand it; i.e., a finite automata that decides whether a string is in a given language. I think that's perfectly reasonable here, as the given problem is finding the fastest algorithm that decides whether a string is in the language generated by ASCII characters without the vowels. I think it's reasonable for me to use a (not hand-optimized) implementation that obeys that definition in my comparison.
- Kranar 1y ago
  >The only thing that the optimizer does is unrolls the loop that advances the state. The idea that you'd dismiss loop unrolling as some kind of non-issue is incredibly baffling, you need only compare the benchmark built without optimizations enabled to the one with optimizations enabled, and you'll see that the unoptimized build is about half as fast! Speaking of Python the most recent Python release has some significant performance increases in some scenarios because of some additional loop unrolling that has been exploited. >That's why I said "well-optimized regex." Most regexes, in practice, are not well-optimized! So then what exactly is the point of your argument? I point out that using regex's are slow, which almost anyone would reasonably assume means that using regex libraries tend to be slow. Is the entire point of your comment that you can take a regex and then manually implement a special purpose algorithm for it that isn't slow? Was that the point of your comment, because if so you could have made that clear initially and saved both of us a lot of time. >I think that's perfectly reasonable here, as the given problem is finding the fastest algorithm that decides whether a string is in the language generated by ASCII characters without the vowels. No it's not reasonable at all because if you take your definition then there is nothing to use. Being a regular language is not something you can "use" or "not use", it's a property of a set of strings, you don't get to use it. The language consisting of all strings that have at least one vowel in them is a regular language, case closed, usage has nothing to do with it. In the sense that you're using it, any algorithm whatsoever that returns true or false for a string that matches some arbitrary regular language can be considered an implementation of a regex, for some fixed regular language. But of course this is a completely trivial argument which is why there's absolutely no point in discussing it. In the non-trivial sense that everyone else uses it... regex's are libraries that people use that let them write a string representing a pattern and then the library returns an object that can be used to test whether or not a string matches that pattern, or can be used to search for a substring that matches a pattern along with a host of functionality. The claim in my original post is that these libraries, including the one used by the blog post, tend to be slow. They are, as you point out, designed for ergonomics and convenience, not for performance. It is not at all reasonable to argue that some arbitrary implementation you divined for a particular regular language constitutes some argument that regular expressions are a high performance means of performing string matching, but at least you have clarified your position and shown it to be absolutely trivial and meaningless, and hopefully anyone who has read your post won't be misled into thinking you meant that regex libraries that are commonly used by actual engineers like Python's, or PCRE2, or boost or the standard library are fast... but I have my doubts about that.

by Kranar 1y ago

tylerhou 1y ago

> Sure, if you make a bunch of assumptions and manually implement how you think a regex will compile your code, allowing the optimizer to take your compile time implementation and make a finely tuned algorithm specifically for one use case, But that's not what is happening. The only thing that the optimizer does is unrolls the loop that advances the state. Otherwise, the sequence of instructions is standard: two loads and some pointer arithmetic. There is no finely tuned algorithm. https://godbolt.org/z/fqdb5bssc https://godbolt.org/z/fqdb5bssc > But if you use an actual regex the way people actually use them, using either the one provided by their standard library or one that is readily available then regex is pretty slow. Yes, most regex implementations are not designed to be efficient, they are designed for ergonomics (including supporting exponential-time features like lookaround). (Both boost::regex and PCRE2 support exponential-time features; std::regex is just not optimized at all.) This is well-known. https://swtch.com/~rsc/regexp/regexp1.html https://swtch.com/~rsc/regexp/regexp1.html. That's why I said "well-optimized regex." Most regexes, in practice, are not well-optimized! Maybe this is a semantic distinction between what you and I consider a "regex." I interpreted "regex" as how people in CS theory understand it; i.e., a finite automata that decides whether a string is in a given language. I think that's perfectly reasonable here, as the given problem is finding the fastest algorithm that decides whether a string is in the language generated by ASCII characters without the vowels. I think it's reasonable for me to use a (not hand-optimized) implementation that obeys that definition in my comparison.

Kranar 1y ago
>The only thing that the optimizer does is unrolls the loop that advances the state. The idea that you'd dismiss loop unrolling as some kind of non-issue is incredibly baffling, you need only compare the benchmark built without optimizations enabled to the one with optimizations enabled, and you'll see that the unoptimized build is about half as fast! Speaking of Python the most recent Python release has some significant performance increases in some scenarios because of some additional loop unrolling that has been exploited. >That's why I said "well-optimized regex." Most regexes, in practice, are not well-optimized! So then what exactly is the point of your argument? I point out that using regex's are slow, which almost anyone would reasonably assume means that using regex libraries tend to be slow. Is the entire point of your comment that you can take a regex and then manually implement a special purpose algorithm for it that isn't slow? Was that the point of your comment, because if so you could have made that clear initially and saved both of us a lot of time. >I think that's perfectly reasonable here, as the given problem is finding the fastest algorithm that decides whether a string is in the language generated by ASCII characters without the vowels. No it's not reasonable at all because if you take your definition then there is nothing to use. Being a regular language is not something you can "use" or "not use", it's a property of a set of strings, you don't get to use it. The language consisting of all strings that have at least one vowel in them is a regular language, case closed, usage has nothing to do with it. In the sense that you're using it, any algorithm whatsoever that returns true or false for a string that matches some arbitrary regular language can be considered an implementation of a regex, for some fixed regular language. But of course this is a completely trivial argument which is why there's absolutely no point in discussing it. In the non-trivial sense that everyone else uses it... regex's are libraries that people use that let them write a string representing a pattern and then the library returns an object that can be used to test whether or not a string matches that pattern, or can be used to search for a substring that matches a pattern along with a host of functionality. The claim in my original post is that these libraries, including the one used by the blog post, tend to be slow. They are, as you point out, designed for ergonomics and convenience, not for performance. It is not at all reasonable to argue that some arbitrary implementation you divined for a particular regular language constitutes some argument that regular expressions are a high performance means of performing string matching, but at least you have clarified your position and shown it to be absolutely trivial and meaningless, and hopefully anyone who has read your post won't be misled into thinking you meant that regex libraries that are commonly used by actual engineers like Python's, or PCRE2, or boost or the standard library are fast... but I have my doubts about that.