From: Mathieu Bouchard <matju@...>
Date: 2006-07-22T13:03:28+09:00
Subject: Re: Regular-Expressions Problem/Bug

--8323328-133318843-1153540959=:30944
Content-Type: MULTIPART/MIXED; BOUNDARY="8323328-133318843-1153540959=:30944"

  This message is in MIME format.  The first part should be readable text,
  while the remaining parts are likely unreadable without MIME-aware tools.

--8323328-133318843-1153540959=:30944
Content-Type: TEXT/PLAIN; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: QUOTED-PRINTABLE

On Wed, 19 Jul 2006, Reto Schuettel wrote:

> After some experiments I could even simplify the problem:
> LENGTH =3D 20000
> text =3D "x" * LENGTH + "ABC" + "y" * 10
> re =3D /(.*)ABC[y]#/
> -> takes forever...

Here, forever takes 3657 ms.

With LENGTH=3D40000, it's 14551 ms. The ratio of those suggests that it's a=
=20
O(LENGTH^2) situation. Trying with more cases of LENGTH confirms this, for=
=20
sufficiently large LENGTHs.

This shouldn't happen, because (.*) should just match all of the string=20
and then retry with smaller strings until the rest of the regexp matches=20
on the rest of the string.

O(LENGTH^2) suggests that there might be O(LENGTH) steps of duration=20
O(LENGTH) each, which I could speculate to be string copying operations of=
=20
the $1 prematurely. What perplexes me is that (?:.*) is just as slow as=20
(.*) ... After that, I don't know what to say.

  _ _ __ ___ _____ ________ _____________ _____________________ ...
| Mathieu Bouchard - t=E9l:+1.514.383.3801 - http://artengine.ca/matju
| Freelance Digital Arts Engineer, Montr=E9al QC Canada
--8323328-133318843-1153540959=:30944--
--8323328-133318843-1153540959=:30944--