From: MenTaLguY <mental@...>
Date: 2007-04-13T02:47:34+09:00
Subject: Re: Slow ruby regexes

On Fri, 13 Apr 2007 02:25:15 +0900, "David Balmain" <dbalmain.ml@gmail.com> wrote:
> This would be true if the Thompson algorithm was caching the states as
> it went. If I recall correctly (it's been a while since I read the
> article) it doesn't cache the states and Russ Cox's code in the
> article definitely doesn't.

There is a section in his article entitled "Caching the NFA to build a DFA" with code doing exactly that.

> In fact I read somewhere that the Perl regex engine has started to use dynamic
> programming, obviously without great success.

It's mentioned in his article as well.

> In some instances it will take longer to compile the
> regex into a DFA then it will take to evaluate the simple NFA
> representation.

Namely, when most of the states in the NFA will not be visited for a particular input.  That is why the DFA construction is done lazily.

> By the way, I highly recommend people check out Ville Laurikari's
> regex engine TRE;
> 
>     http://laurikari.net/tre/
> 
> While the predictable worst-case performance is nice, the really cool
> thing that I like about this project is the approximate matching. This
> is something I'd really like to have in Ruby.

That's really cool.

-mental