# Slow regular-expression engine **URL:** \ **Category:** Ruby\ **Created:** [July 31, 2009, 6:30pm UTC](https://www.ruby-forum.com/t/slow-regular-expression-engine/173031 "2009-07-31T18:30:37Z")\ **Posts on this page:** 7\ **Page:** 1
**Author:** ![w\_a\_x\_man](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/w/e47774/32.png) [@w\_a\_x\_man](https://www.ruby-forum.com/u/w_a_x_man)\ **Post date:** [July 31, 2009, 6:30pm UTC](https://www.ruby-forum.com/t/slow-regular-expression-engine/173031/1 "2009-07-31T18:30:37Z")
This Awk code takes less than one hundredth of a second to run: BEGIN { regex = “o?o?o?o?o?o?o?o?o?o?o?o?o?o?” “o?o?o?o?o?o?o?o?o?o?o?o?o?” “ooooooooooooooooooooooooooooo” print “ooooooooooooooooooooooooooooo” ~ regex } This Ruby code takes 27.5 seconds: t = Time.now regex = Regexp.new( “o?o?o?o?o?o?o?o?o?o?o?o?o?o?” + “o?o?o?o?o?o?o?o?o?o?o?o?o?” + “ooooooooooooooooooooooooooooo” ) p “ooooooooooooooooooooooooooooo” =~ regex puts “#{ Time.now - t } seconds” See [Regular Expression Matching Can Be Simple And Fast](http://swtch.com/~rsc/regexp/regexp1.html) ---
**Author:** ![w\_a\_x\_man](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/w/e47774/32.png) [@w\_a\_x\_man](https://www.ruby-forum.com/u/w_a_x_man)\ **Post date:** [July 31, 2009, 6:51pm UTC](https://www.ruby-forum.com/t/slow-regular-expression-engine/173031/2 "2009-07-31T18:51:06Z")
On Jul 31, 11:37 am, removed\_email\_address@domain.invalid wrote: > > print “ooooooooooooooooooooooooooooo” ~ regex > > “ooooooooooooooooooooooooooooo” ) > > Regexp looks and is awful and could be written in a way better way which > > takes times of 0.000139965 seconds. > > t = Time.now > regex = Regexp.new(/o{0,27}ooooooooooooooooooooooooooooo/ ) > p “ooooooooooooooooooooooooooooo” =~ regex > puts “#{ Time.now - t } seconds” > > – > Dominik H. > removed\_email\_address@domain.invalid Quoting the article: … 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. Seeing the two graphs side by side prompts the question, “why doesn’t Perl use the Thompson NFA approach?” It can, it should … ---
**Author:** ![w\_a\_x\_man](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/w/e47774/32.png) [@w\_a\_x\_man](https://www.ruby-forum.com/u/w_a_x_man)\ **Post date:** [July 31, 2009, 6:41pm UTC](https://www.ruby-forum.com/t/slow-regular-expression-engine/173031/3 "2009-07-31T18:41:09Z")
w\_a\_x\_man [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) writes: > “ooooooooooooooooooooooooooooo” ) > > p “ooooooooooooooooooooooooooooo” =~ regex > > puts “#{ Time.now - t } seconds” > > See [Regular Expression Matching Can Be Simple And Fast](http://swtch.com/~rsc/regexp/regexp1.html) In Ruby 1.9 its 1/4 of the time (still slow). But: One might ask if that is a problem at all, considering that this Regexp looks and is awful and could be written in a way better way which takes times of 0.000139965 seconds. t = Time.now regex = Regexp.new(/o{0,27}ooooooooooooooooooooooooooooo/ ) p “ooooooooooooooooooooooooooooo” =~ regex puts “#{ Time.now - t } seconds” ---
**Author:** ![w\_a\_x\_man](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/w/e47774/32.png) [@w\_a\_x\_man](https://www.ruby-forum.com/u/w_a_x_man)\ **Post date:** [July 31, 2009, 7:02pm UTC](https://www.ruby-forum.com/t/slow-regular-expression-engine/173031/4 "2009-07-31T19:02:14Z")
On Fri, Jul 31, 2009 at 9:50 AM, w\_a\_x\_man[removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote: > Quoting the article: > > … 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. Seeing the two graphs side > by side prompts the question, “why doesn’t Perl use the > Thompson NFA approach?” It can, it should … So what? I’m sure Ruby core would be happy to consider a patch. Ben ---
**Author:** ![w\_a\_x\_man](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/w/e47774/32.png) [@w\_a\_x\_man](https://www.ruby-forum.com/u/w_a_x_man)\ **Post date:** [August 1, 2009, 7:49am UTC](https://www.ruby-forum.com/t/slow-regular-expression-engine/173031/5 "2009-08-01T07:49:35Z")
Ben B. wrote: > So what? I’m sure Ruby core would be happy to consider a patch. > Yes we do. And if you could write a time-efficient NFA engine with back > references implemented, please also send that to some scientific > journal, > because that should solve the P=NP problem. ---
**Author:** ![w\_a\_x\_man](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/w/e47774/32.png) [@w\_a\_x\_man](https://www.ruby-forum.com/u/w_a_x_man)\ **Post date:** [August 1, 2009, 8:40am UTC](https://www.ruby-forum.com/t/slow-regular-expression-engine/173031/6 "2009-08-01T08:40:31Z")
On Sat, Aug 1, 2009 at 7:49 AM, Urabe S.[removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote: You should prepare a mail template as inspired by this historic example --------------------- 8\< ----------------------- Dear reader we have received your proof of Fermat’s Last Theorem. We have to regret to inform you that there is an error in line ### --------------------- \<8 ---------------------- Cheers Robert ---
**Author:** ![w\_a\_x\_man](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/w/e47774/32.png) [@w\_a\_x\_man](https://www.ruby-forum.com/u/w_a_x_man)\ **Post date:** [August 1, 2009, 2:45pm UTC](https://www.ruby-forum.com/t/slow-regular-expression-engine/173031/7 "2009-08-01T14:45:46Z")
On 31.07.2009 18:49, w\_a\_x\_man wrote: > > > This Ruby code takes 27.5 seconds: > > > But: One might ask if that is a problem at all, considering that this > > > removed\_email\_address@domain.invalid > > Quoting the article: > > … 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. Seeing the two graphs side > by side prompts the question, “why doesn’t Perl use the > Thompson NFA approach?” It can, it should … I am not sure as to what exactly your point is. The awk you have been using might have used a DFA implementation (sed does so AFAIK). Nowadays most regular expression engines are NFA because of various reasons (see “Mastering Regular Expressions”). Usually NFA’s can be tricked into bad runtime performance with expressions like the one you wrote. I do not consider this a disadvantage because on the other hand you can optimize your expression when working with a NFA, for example by deliberately selecting order of sub expressions in the expression. And, the expression is really pathologic, i.e. you would not use something like that in practice. Btw, why don’t you declare the regular expression directly, i.e. regex = %r( o?o?o?o?o?o?o?o?o?o?o?o?o?o? o?o?o?o?o?o?o?o?o?o?o?o?o? ooooooooooooooooooooooooooooo )x ? Kind regards robert