Subject: Re: [PATCH] Interpret :/<pattern> as a regular expression

From: Sam Vilain <[email-masked]>
Date: Thu, 14 Jun 2007 19:48:11 +1200

Johannes Schindelin wrote:
> Actually, that's funny. Yesterday, I repeated my claim that pcre is 
> slow on IRC, and Sam Villain on IRC accused me of trolling. But as you can 
> see from my postings on this list ($gmane/41682), you can see that _I_ had 
> numbers to back up my claim.
>
> So no, I think pcre is just not worth it.
>   

A strange thing to conclude from your figures, which show pcre as the
fastest out of several libraries that you tested.

Your figures show exactly what I was saying on IRC - that a DFA
(external grep) vs NFA engine (most regex libraries) is inherently
faster. The paper I linked to, specially selected as I had previously
read a significant amount of the peer review the paper received,
explained this in detail. The one piece of feedback your numbers got
on-list also mentioned this.

However there is a further flaw in your study. All but one of the
performance tests use an external program, which on a given system may
or may not be faster because of pipeline performance characteristics.
You could improve the quality of the result by using the 'pcregrep'
program as a data point. It might also be worth trying a few more
complex patterns. I suggest reading the paper
(http://swtch.com/~rsc/regexp/regexp1.html) for some background before
repeating the experiment.

Apologies for not reviewing your numbers at the time; it sure is hard to
keep on top of this list. But very interesting that they seem to suggest
pcre would be the best choice from a performance perspective, even
though the figures are very preliminary. Perhaps it is worth pursuing
after all.

Sam.