From: Keith Gaughan <kmgaughan@...>
Date: 2006-07-28T02:35:49+09:00
Subject: Re: Slow regular expressions :(

On Fri, Jul 28, 2006 at 01:41:05AM +0900, Roman Hausner wrote:

> I am disappointed to learn that Ruby obviously implements yet another 
> regular expression library that does not avoid very slow matching 
> failures.
> 
> Just try this program:
> 
> str1 = "foo " * 70 + "foo ";
> str2 = "foo " * 70 + "fo ";
> 
> strings = str1, str2;
> 
> strings.each { |s|
>   print "Matching #{s}\n";
>   if(s =~ /^(\s*foo\s*)*$/)
>     print "YES!\n";
>   else
>     print "NO!\n";
>   end
> }

Ah, now while I'm not saying that Ruby's regex engine is slow--it
is--I think it's more likely here that you hit a pathological edge
case in how it works, specifically the '\s*' on each side of 'foo'.

When the code is changed to

    strings.each do |s|
      print "Matching #{s}\n"
      if s =~ /^(foo\s*)*$/
        print "Yes!\n"
      else
        print "No!\n"
      end
    end

The problem disappears and the Ruby and Perl versions of that code
benchmark similarly.

Patterns in the form (x*y*x*)* have a habit of acting pathologically and
there's almost always a better and clearer way of writing them, mainly
because they have a habit of causing a nasty amount of backtracking.
This applies to a good number of regex engines, and not just Ruby's.

> On my machine, the perl version takes 0.229 seconds. The ruby version 
> was still running after 519.662 seconds when I killed it.
> 
> Is this being taken care of for the next release?

My suspicion is that Ruby's regex package doesn't account for this
pathological case, where as Perl's--which, to be frank, is pretty much
the best regex engine out there bar none except for its support for
Unicode properties--does.

Not a clue as to whether it'll be taken care of, though. JARH.

K.

-- 
Keith Gaughan - kmgaughan@eircom.net - http://talideon.com/