4 ms·

Or they won’t as everyone who worked on perl based website from 2000 will tell you. This is a massively overstated title and lede. However the solutions give

• pjscott 14y ago
  Perl also has some clever memoization which handles a lot of cases that choke less mature regular expression engines. But neither of these is a satisfying solution; backtracking control verbs can only help you if you use them, and the memoization is not the solution to all woes, as the benchmark in the "Performance" section of this article shows: http://swtch.com/~rsc/regexp/regexp1.html http://swtch.com/~rsc/regexp/regexp1.html The sky isn't falling, but it's still possible to get struck by lightning. (And of course, you're vulnerable to DoS attacks if you run user-supplied regexps with backreferences -- this is provably NP-hard.)
  • vampirechicken 14y ago
    Not to gainsay everything you've written here, because I think that I think there's plenty of room in my universe for new regex engines, but the article is five years old and benchmarks Perl 5.8.7. We are of course up to 5.16.1 these days, and I'd be more inclined to pay attention to benchmarks if they were performed with remotely current versions of the software. Otherwise, thanks for the enlightening post.
    • pjscott 14y ago
      Just ran the same benchmark on Perl 5.12.3 (because it came installed by default on my machine), and got the same exponential-time matching behavior. If you have a more recent version of Perl than I do, I'd be interested in hearing the results. This takes about 10 seconds on my machine, but should be nigh-instantaneous if they've fixed the problem in a later version of Perl: "aaaaaaaaaaaaaaaaaaaaaaaaaaa" =~ /a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?aaaaaaaaaaaaaaaaaaaaaaaaaaa/
      • vampirechicken 14y ago
        I have 5.8.8, and I have 5.14.2. I've also taken the liberty of converting the string of a?'s into a{0,27}. I recognize that you're trying to demonstrate pathologically bad behavior, but as written, you've got a pathologically bad regex. Note the speed up from 24 & 30 seconds to seven one-thousandths of a second in both cases. Again, I like the idea of a regex engine with different design considerations than Perl's. Your article would have been much better if it has used a class of pathological data with real world examples, and not used contrived examples that I rewrote in less time than it took to run. So here's my results: 5.14.2: $ time perl -e 'print "aaaaaaaaaaaaaaaaaaaaaaaaaaa" =~ /a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?aaaaaaaaaaaaaaaaaaaaaaaaaaa/ ' 1 real 0m24.227s user 0m24.210s sys 0m0.008s $ time perl -e 'print "aaaaaaaaaaaaaaaaaaaaaaaaaaa" =~ /a{0,27}aaaaaaaaaaaaaaaaaaaaaaaaaaa/ ' 1 real 0m0.007s user 0m0.004s sys 0m0.004s ---------------------------------- 5..8.8: $ time perl -e 'print "aaaaaaaaaaaaaaaaaaaaaaaaaaa" =~ /a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?aaaaaaaaaaa aaaaaaaaaaaaaaaa/ ' 1 real 0m30.065s user 0m30.046s sys 0m0.016s $ time perl -e 'print "aaaaaaaaaaaaaaaaaaaaaaaaaaa" =~ /a{0,27}aaaaaaaaaaaaaaaaaaaaaaaaaaa/ ' 1 real 0m0.007s user 0m0.004s sys 0m0.004s --------------------------------
        • pjscott 14y ago
          Real-world examples tend to be subtler, and not quite as easy to explain in an introductory article. Of course you wouldn't really use the for-demonstration-only regex I mentioned. Instead, you would write something reasonable-looking that works just fine unless it encounters a highly unlikely bad input. That's the way I've always seen it happen.
          • vampirechicken 14y ago
            In the "real world" I usually try to optimize for the average case, and deal with the "highly unlikely bad input" as a special case. I'm still impressed with the new regex engine, but I have a pathological hatred of contrived examples. It's not you, it's me.