11 ms·
Regular Expression Matching Can Be Simple and Fast (2007)
- abainbridge 7y agoIs there any information about the performance when not looking for things like when a?a?a?aaa matches aaaaaa?
- feniv 7y agoThe author, Russ Cox, has a whole series of articles on the topic of regex - https://swtch.com/~rsc/regexp/ https://swtch.com/~rsc/regexp/ The rust Regex crate docs even refer to his posts as a reference since the rust version is based on his efficient RE2 Regex implementation at Google.
- dang 7y agoThreads from 2018: https://news.ycombinator.com/item?id=16341519 https://news.ycombinator.com/item?id=16341519 2015: https://news.ycombinator.com/item?id=9374858 https://news.ycombinator.com/item?id=9374858 2009: https://news.ycombinator.com/item?id=820201 https://news.ycombinator.com/item?id=820201 also 2009: https://news.ycombinator.com/item?id=466845 https://news.ycombinator.com/item?id=466845
- Quarrel 7y agoBut if you want faster, (but more complicated): https://github.com/intel/hyperscan https://github.com/intel/hyperscan
- rurban 7y agoWith much less features. hyperscan only works with very limited regular expressions. Russ' re2 just cannot do backtracking.
- hyperpallium 7y agoNow you have an exponential space problem.
- tempguy9999 7y agoA quick skim of the article doesn't show any sophisticated pattern reduction pattern so the parent's comment would appear fair. Straightforward regex implementations have to be exponential in time or space for pathologies, and if it's not time here then it's space, so why is this being downvoted?
- yorwba 7y agoA program that is not exponential in time can't require exponential space, because it can't touch that much space in that little time. Even if you count the NFA as part of the input, the expansion into a DFA only happens while matching one character at a time, so to blow up the cache to a size exponential in the number of NFA states, you'd have to be matching on a string of comparable length that forces all possible state combinations to occur. If you don't count the NFA as part of the input, the matching algorithm for any particular NFA is actually constant-space, because the maximum space required is independent of the string you're processing.
- tempguy9999 7y agoI'm assuming the DFA is built ahead of time, which is pretty conventional in my understanding. This may be something in the article I missed, that the DFA is built incrementally at runtime by this algo. If so, my mistake. I'll read again. @chubot: ok, I am wrong, thanks for the details! Upvoted both.
- chubot 7y agoNo, your understanding and the parent's isn't correct. The NFA is linear in the size of the regex. That is, a regex like a+b+c+ will have an NFA that's 3x the size of the NFA for a+. Interpreting the NFA is done in time LINEAR with respect to the input data. Code is given in Cox's articles. Yes worst case linear. You're probably thinking of NFA -> DFA conversion, i.e. the "subset construction". First of all, RE2 doesn't always do that. You can always operate on NFAs. (and it does that because of capturing is hard with DFAs, IIRC) Second of all, "exponential in size of input pattern" is NOT a problem. Exponential in the size of the DATA is a problem, and that doesn't happen. When you are measuring the runtime of regexes, the size of the pattern is a small constant. (Think matching a+b+c+ against gigabytes of data.) The magic of regexes is that you can match any regular language in linear time and constant space. You can't do that with "regexes". That's the WHOLE POINT of these articles. I have wanted to write a summary of Russ Cox's articles on my blog for awhile. They are very good, but they are very dense, and most people still aren't getting the message. The message is: "Use regular languages and not regexes". (e.g. constructs like backreferences and lookaround assertions make the language nonregular) [1] Side note: I tested re2c and its regex compilation time is linear up to matching 47,000 fixed strings in parallel (from /usr/share/dict/words) https://github.com/oilshell/blog-code/blob/master/fgrep-problem-benchmarks/fixed-strings.sh#L328 https://github.com/oilshell/blog-code/blob/master/fgrep-prob... re2c ALWAYS builds a DFA, unlike RE2. (Note: they are completely unrelated projects, despite their similar names.) Even taking into the account that exponential in the size of the pattern is not a problem, it's still not exponential in the size of the pattern (for the fgrep problem). If the DFA were exponentially sized, then it would take exponential time to construct it, but it doesn't in this case.
- DigitalTerminal 7y agoAlso relevant is Google V8's Irregexp: https://blog.chromium.org/2009/02/irregexp-google-chromes-new-regexp.html https://blog.chromium.org/2009/02/irregexp-google-chromes-ne.... They claim 3x speedups.
- zamadatix 7y agohttps://github.com/google/re2 https://github.com/google/re2 is probably a better matched library by Google since the post focuses on truly regular expressions and a lot of irregexp's design is around making the irregular part not as costly.
- pier25 7y agoA bit off topic, but here are some Regex benchmarks that might be of interest: https://github.com/mariomka/regex-benchmark https://github.com/mariomka/regex-benchmark Surprisingly JS is about 10 times faster than Go.
- statictype 7y agoPresumably the JS's regex engine is implemented in C? Can't believe the .NET implementation is so slow.
- pier25 7y agoYes, most likely, or maybe C++.
- ridiculous_fish 7y agov8 and JSC both JIT-compile regexes.
- yxhuvud 7y agoWhat I wonder is if the regexps could be preprocessed in a way so that the fast variant is used for all or at least most cases where it it possible to use it.