9
$\begingroup$

In a 2007 article, Russ Cox (at presents, he leads the development of the Go programming language at Google) argues that regex engines in languages like Java, Perl, PHP, Python, Ruby are built on a different theoretical framework from implementations like awk or sed. Cox claims a difference in performance between 60s and 20microseconds (the difference is an order of magnitude of millions!). Link to the article.

Is this issue still up-to-date? That is, is the theory behind these groups of implementations basically different?

Is there any real life scenario when a programmer would need to pick some Jurassic implementation like awk (due to its solid theoretical framework) because otherwise the task at hand could not be dealt with?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
13
$\begingroup$

It isn't a matter of implementation. It's a matter of different approaches to parsing that unfortunately have similar names.

NFAs and DFAs (finite-state machines) can only recognize regular languages. Regular expressions are a way of specifying regular languages, and they can be compiled into efficient NFAs or DFAs that recognize the language. This is all taught in undergraduate CS courses.

The so-called "regexes" in Perl and its many imitators have a name that sounds like an abbreviation of "regular expression", and they syntactically resemble the regular expressions of sed and awk, but they are not regular expressions. They are really specifications of backtracking parsers. Backtracking parsers aren't limited to recognizing regular languages. (The name "regex" is Larry Wall's fault. He made a deliberate decision to not call them "regular expressions" because he knew that they weren't, but he should have invented an entirely different name.)

You don't need a Jurassic implementation of NFA/DFA based regular expression matching; modern maintained libraries are available for popular languages. But they lack many features of Perl-style regexes, and they don't offer much in exchange. They certainly have much better worst-case performance, but the pathological worst cases of backtracking parsers can be fixed by modifying the regexes, without losing the extra flexibility of backtracking.

The article by Cox is disingenuous. He evidently wants you to believe that the authors of regex libraries are ignorant of the theory of regular languages, and if they had just studied the standard undergraduate CS curriculum then they would have implemented their libraries in a different way and made them faster. That's false. It's impossible to implement Perl-style regexes that way, and he knows it. The popularity of Perl-style regexes is probably due in large part to their flexible feature set that goes far beyond what's available in any true regular expression library.

Improve this answer
$\endgroup$
5
  • 6
    $\begingroup$ It isn't disingenuous. Perl-style backtracking engines are deliberately choosing to use an exponentially attackable implementation, partially to support backreferences. This applies even if the regex doesn't actually use backreferences, and is therefore a severely bad implementation for those extremely common use cases, and there is no escape hatch in their engine. You're forgetting adversarial input, which literally applies whenever user input is used. $\endgroup$
    – obscurans
    Commented Feb 11, 2021 at 8:13
  • $\begingroup$ Anecdotally, for a project where I had to match some moderately large expressions against moderately large inputs, I went from it taking several days to half a minute by switching from Javas regex implementation which uses backtracking to Google's re2j, which uses a linear complexity parser as far as I understand. So I guess actually just supports actual regular expressions(?). I lost a few backreferences, but that was well worth it. I also should mention I didn't need to migrate all matchers, just the particularly bad ones. $\endgroup$
    – kutschkem
    Commented Feb 11, 2021 at 16:50
  • $\begingroup$ RE2 was used for Google Code Search, which allowed users to run pattern searches on a remote system. With a backtracking matcher, it'd be much more limited at best. Disregarding remote users, you're putting the burden on the user to worry about "good" patterns, which is the tradeoff for the flexibility of backrefs (whether or not you need them). $\endgroup$
    – leewz
    Commented Feb 11, 2021 at 21:21
  • $\begingroup$ I believe it is possible to mix the two methods, using the theoretical algorithm on "pure" subexpressions, and then backtracking at a higher level if you need to. $\endgroup$
    – leewz
    Commented Feb 11, 2021 at 21:24
  • 1
    $\begingroup$ @obscurans: Right -- in Perl, patterns are considered code: if you wouldn't trust a user-supplied subroutine, then you can't trust a user-supplied pattern. In Perl this is somewhat intuitive IMHO, because patterns are integrated so well into the language syntax; but in languages where Perl-style patterns are just a library, the patterns just look like strings, and it's less obvious that they're still code and still need to be trusted. I find Perl-style patterns extremely useful, but yeah, it would be nice if Perl/Java/etc. also had libraries for awk/sed-style expressions. $\endgroup$
    – ruakh
    Commented Feb 13, 2021 at 21:32
7
$\begingroup$

Cox's post is still relevant and up-to-date. The key quote is this one:

Most of the time, in fact, regular expression matching in Perl is fast enough. As the graph shows, though, it is possible to write so-called “pathological” regular expressions that Perl matches very very slowly. In contrast, there are no regular expressions that are pathological for the Thompson NFA implementation.

Later in the post, Cox gives examples that are relevant in the real world:

Examples include using (.*) (.*) (.*) (.*) (.*) to split five space-separated fields, or using alternations where the common cases are not listed first.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.