[perl #15797] [PATCH] Regex speedup

# New Ticket Created by  Angel Faus 
# Please include the string:  [perl #15797]
# in the subject line of all future correspondence about this issue. 
# <URL: http://rt.perl.org/rt2/Ticket/Display.html?id=15797 >


Hi,

I've made a patch for the regex engine, designed with the single goal 
of seriously cheating for speed. :-)

This are the most important changes:

* There is no regex state PMC, so there is not cost of creating and 
destroying it. (all the state is stored in registers, or in a 
per-interpreter intstack) [this was suggested by Dan]

* Some regex ops have been combined in order to increase code density, 
or/and save some repeated computiations. In some cases, this even 
allows to avoid using using the stack in places that previously used 
it.

* Some minor tweaks in string.c, in order to inline the computation of 
string_index, when the string is a native one.

Some benchmarks (200.000 iterations, the loop inside parrot/perl):

parrot		perl
------------------
0.2012		0.2887		/^zza/
0.5089		0.6358		/ab*cd[cd]*/
0.6557		1.5460		/a(?:b|ac)*[cd]*/
1.7316		3.2161		/a(b|ac)*[cd]*/   (capturing)

This benchmark assumes a smart compiler on the parrot side, capable of 
detecting optimitzation oportuinities. I started with this regexes, 
and added optimitzations on the regex engine until they were faster 
than their perl cousins. So this is not a complete speed comparision. 

I think that the benchamarks are fair, but I could be wrong. The 
attached examples_regex.tar.gz includes all the files needed to 
reproduce them.

Anyway, this patch has brought me the personal conviction that parrot 
regexes can be as fast or faster than their perl equivalents, if we 
put a bit of effort on optimitzation.

The fast_re.patch file includes all the changes, and updates the tests 
to use the new opcodes. Documentation is not updated, though.

Best,

Angel Faus
afaus@corp.vlex.com


-- attachment  1 ------------------------------------------------------
url: http://rt.perl.org/rt2/attach/31934/26589/cc89a5/fast_re.patch

-- attachment  2 ------------------------------------------------------
url: http://rt.perl.org/rt2/attach/31934/26590/10e423/examples_regex.tar.gz

• [perl #15797] [PATCH] Regex speedup by Angel Faus
• Re: [perl #15797] [PATCH] Regex speedup by Dan Sugalski