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

From: Sam Vilain <sam@vilain.net>
Date: Jun 14, 2007, 07:48 UTC
Message-ID: <4670F2BB.5060909@vilain.net>
In-Reply-To: <Pine.LNX.4.64.0706132317240.4059@racer.site>

Johannes Schindelin wrote:

Show 7 quoted lines

> 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.