re.search much slower then grep on some regular expressions

[Mark Wooding]

Sebastian "lunar" Wiesner <basti.wiesner at gmx.net> wrote:

> I just wanted to illustrate, that the speed of the given search is somehow
> related to the complexity of the engine.  
>
> Btw, other pcre implementation are as slow as Python or "grep -P".  I tried
> a sample C++-code using pcre++ (a wrapper around libpcre) and saw it
> running equally long.

So some other implementations are equally poor.  I note that Perl itself
handles this case very quickly, as does Edi Weitz's CL-PPCRE library.

Yes, Perl-compatible `regular expressions' are more complicated than
POSIX extended regular expressions; but that doesn't mean that you have
to implement them in a dumb way.  Indeed, it stands to reason that
expressions describing truly regular languages can be matched using the
same old algorithms that grep uses.

-- [mdw]