4 ms·
If you were interested in performance you probably would not have been using boost::regex to begin with. RE2 is often an order of magnitude faster. You might
by stuckagain 10y ago
If you were interested in performance you probably would not have been using boost::regex to begin with. RE2 is often an order of magnitude faster. You might choose boost if you require backtracking, but that's crazy anyway due to exponential time.
- 0xFFC 10y agoWhat is backtracking?
- bowmessage 10y agohttp://stackoverflow.com/questions/9011592/in-regular-expressions-what-is-a-backtracking-back-referencing http://stackoverflow.com/questions/9011592/in-regular-expres...
- Phritzy 10y agohttps://regex101.com/r/G23xYd/2 https://regex101.com/r/G23xYd/2
- deleted 10y ago[deleted]
- kbenson 10y agoA feature of certain types of regular expression engines. It allows for certain types of regular expressions but at the cost of possibly going exponential if you aren't careful about your expression. [1] 1: http://www.regular-expressions.info/catastrophic.html http://www.regular-expressions.info/catastrophic.html
- carussell 10y agoLooks like there's (a lot of) confusion in these comments about the difference between backtracking and backreferences. The `\2` in Phritzy's snippet is a backreference. Backtracking is an implementation strategy for writing a regular expression engine. I don't know why anyone choosing an engine would "require backtracking". It's an implementation detail, not a feature. (Although the fact that Thompson NFAs avoid exponential time complexity inherent to backtracking is something that I suppose could be considered a feature.) Here's a link to some real literature: https://swtch.com/~rsc/regexp/regexp1.html https://swtch.com/~rsc/regexp/regexp1.html
- stuckagain 10y agoThere are features of some regular expressions for which the only known solution is backtracking. If you want those features then you "require backtracking".
- ue_ 10y agoOut of interest, what are some of these? I have a hard time believing that the implementors of the Perl regex engine chose to write it that way for no reason while the Thompson NFA figures are thrown about. I knew there must havevbeen something this 'implementation detail' was good for.
- eridius 10y agoI believe backreferences require backtracking.
- tatref 10y agoNo, but variable size lookahead/behind do. This is because the engine has to go back if the remaining part of a regex fails. For some examples, see http://www.regular-expressions.info/recursebacktrack.html http://www.regular-expressions.info/recursebacktrack.html) EDIT: you are correct, backreferences do require backtracking, my bad.
- geofft 10y agoAn easy example is matching palindromes. You simply can't match a palindrome by moving forward only; you have to go back and see if every letter matches. So, if you want to search for the longest palindrome in a string, you'll necessarily be doing a lot of backtracking. There's no RE2-compatible regular expression for matching palindromes, but additional features as found in PCRE and similar "regex" engines can do it with backreferences or with look-around assertions. See http://stackoverflow.com/q/3746487 http://stackoverflow.com/q/3746487 and http://stackoverflow.com/q/3664881 http://stackoverflow.com/q/3664881 for two ways to write such a regex.
- 10y ago
- flogic 10y agoIn my experience, the exponential time thing isn't really a big deal. I've used Perl regular expressions on a very regular basis for about 16 years now. Exponential time has been an issue only once. Obviously if I were accepting regular expressions from random people, I'd use RE2. But for my day to day purposes, it's pretty much a complete non issue.
- kbenson 10y ago> Obviously if I were accepting regular expressions from random people, I'd use RE2. And if you're using Perl, it's not hard to do so[1]. Pluggable regex engines FTW. :) 1: https://metacpan.org/pod/re::engine::RE2 https://metacpan.org/pod/re::engine::RE2
- kmike84 10y agore2 is not only about exponential time: matching of regexes like a|b|c is O(N) in backtracking engines and O(1) in DFA-based engines like re2. It can make a big difference in practice for generated regexes - e.g. if you want to check if an URL has one of the thousand substrings in it (think adblock-like use cases). With backtracking regex or with a loop it'd be O(N) regarding the number of options, but with DFA it is O(1) regarding the number of options. I've seen 1000x speedups for similar use cases with re2 vs re from Python stdlib.
- slavik81 10y agoIs there a quick and easy way to check if a particular regex could take exponential time?
- WildUtah 10y agoAll regexes run in O(N) where N is the length of the string matched. But some regex engines accept non-regular expressions. [0] The usual notation for it is an escaped number: \1 or \2 or so on. They're used to refer back to capturing groups earlier in the expression, usually marked by parentheses. Regular expressions don't have backreferences but various enhanced expressions add them. If you use those extensions, you are in danger of exponential execution time unless you are careful and know what you're doing. In particular you should know not to use regular expressions as your principal tool to build a parser. [0]https://en.wikipedia.org/wiki/Chomsky_hierarchy https://en.wikipedia.org/wiki/Chomsky_hierarchy
- burntsushi 10y agoIt's worth pointing out that if you're using a regex engine that only uses backtracking, then you can't assume all regular expressions take linear time. For example, running `(a)c` against `aaaaaaaaaa` takes exponential time in the number of `a` characters even though it is regular. A hybrid regular expression engine could, in theory, recognize that a particular expression is regular and therefore use a finite state machine to guarantee linear time and space execution (where the size of the regex is held constant).
- beeforpork 10y agoBut unfortunately, converting a non-deteministic finite automaton (i.e., regexp) to a deterministic finite automaton (i.e., engine that can do matches in linear time) may take exponential time and/or space. Yet, I should add, flex does that with extraordinary success. Most grammars are not that bad, it seems.
- burntsushi 10y ago
- zintinio5 10y agoFrom my understanding the main benefit of RE2 is not speed, but linearly scaling execution time with respect to the input size, along with bounded memory usage. For certain inputs, it may outperform other engines, but the converse may also be true. As with any feature that may be abused, backtracking may also be useful: for example, you may need to write a script to munge text. Since you're not exposing it to arbitrary user input, it's a reasonable feature.
- stuckagain 10y agoRE2 is not dramatically faster than all other regex implementations, but it is dramatically faster than boost::regex, which is among the slowest I've ever tested.
- zintinio5 10y agoAh, fair enough.