3 ms·
If you're really worried about the worst-case behavior of regular expressions be sure to select an engine designed specifically to not choke on pathological inp
by kibwen 14y ago
If you're really worried about the worst-case behavior of regular expressions be sure to select an engine designed specifically to not choke on pathological inputs, such as Russ Cox's RE2:
http://code.google.com/p/re2/ http://code.google.com/p/re2/
The rather interesting analysis is here:
http://swtch.com/~rsc/regexp/regexp1.html http://swtch.com/~rsc/regexp/regexp1.html
Not that it's a free lunch, since you're gaining a constant amount of overhead in exchange for a sane growth pattern.
EDIT: Of course the article would mention RE2. That's what I get for reading the comments before TFA...
- pjscott 14y agoThis gets a section in the article, but it's worth repeating, since RE2 is just that good. It's as close to Perl-compatible as a non-backtracking regular expression engine is likely to get, pleasantly fast, and stable enough for Google to use in production. Regarding speed, I've actually found that re2 is faster on some non-pathological regexps, and a little slower on most. As usual, if you care about this, benchmark it. I've managed to get some easy 2x speedups by switching from Python's re to re2, even though re is usually faster.
- kibwen 14y agoGood to hear that RE2's constant factor doesn't seem too large, I know the Rust guys were looking to potentially use it as the regex engine in their stdlib, but were torn on whether that constant factor would prove troublesome.
- Mr_T_ 14y agoDoes anyone know if the Go standard library implements RE2? I'm asking because I know that Russ Cox is on the Go team and the documentation mentions RE2: http://golang.org/pkg/regexp/ http://golang.org/pkg/regexp/
- pjscott 14y agoFrom looking at the source code, Go's regexp package uses O(n) NFA-based matching, as described here: http://swtch.com/~rsc/regexp/regexp2.html http://swtch.com/~rsc/regexp/regexp2.html It isn't nearly as highly optimized as RE2, but it works in a similar way.