From: Robert Klemme <shortcutter@...>
Date: 2009-08-01T21:45:05+09:00
Subject: Re: Slow regular-expression engine

On 31.07.2009 18:49, w_a_x_man wrote:
> On Jul 31, 11:37 am, domini...@gmx.net wrote:
>> w_a_x_man <w_a_x_...@yahoo.com> writes:
>>> 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"
>>> Seehttp://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"
>>
>> --
>> Dominik Honnef
>> domini...@gmx.net
> 
> 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

-- 
remember.guy do |as, often| as.you_can - without end
http://blog.rubybestpractices.com/