Re: Regex introduction?

On Mon, Nov 25, 2013 at 4:28 PM, Abramo Bagnara
<[email protected]>wrote:

> Il 25/11/2013 23:02, Michael Hendricks ha scritto:
> > On Mon, Nov 25, 2013 at 12:56 PM, Jan Wielemaker <[email protected]>
> wrote:
> >
> >> I'm seriously considering to add regular expression support based on the
> >> pcre (Perl Compatible Regular Expressions) library. This seems to be the
> >> library of choice for most modern languages and provides support for the
> >> two internal representations used in SWI-Prolog for Unicode text.
> >>
> >
> > You might consider RE2, if you haven't already.  It supports nearly
> > everything that PCRE does but has much better performance
> characteristics.
>
> Why you say that? AFAIK this is not true nowadays.


PCRE has many clever optimizations to avoid it, but exponential behavior is
still present.  Compare

   perl -Mre::engine::PCRE -e '("a" x 25)  =~ /(.*){1,100}[bc]/'

against an equivalent pattern match in Go:
http://play.golang.org/p/9uMv6dzPgd

PCRE takes about 10 seconds (with N=26 it takes twice as long).  RE2 takes
about 0.01 seconds regardless of N.

Russ Cox did some useful performance comparisons in 2010, separate from
exponential behavior.  They may not be valid with more recent PCRE:
http://swtch.com/~rsc/regexp/regexp3.html

-- 
Michael
-------------- next part --------------
HTML attachment scrubbed and removed