5 ms·

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

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.

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.