Regular expression : non capturing groups are faster ?

[candide]

Excerpt from the Regular Expression HOWTO
(http://docs.python.org/howto/regex.html#non-capturing-and-named-groups) :

 

[Devin Jeanpierre]

The second assertion sounds more likely. It seems very odd that Python and

Perl implementations are divergent on this point. Any opinion ?

The Python documentation oversimplifies. What it means to say is that
while one might expect capturing matches to do extra work proportional
to the capture, they do not. They don't do anything other than mark
down where to extract submatches, and the extra work done is pretty
much negligible. (That is, the work done for submatch extraction is a
polynomial (looks like quadratic) in the number of capturing groups
(which is very small almost always), with a small coefficient).

The Perl documentation is technically correct, but if the HOWTO said
it, it would give the wrong impression. You shouldn't care about
capturing vs noncapturing except with regards to how it interferes
with your group numbering scheme.

-- Devin

 

[Octavian Rasnita]

From: "candide" <[email protected]>
Subject: Regular expression : non capturing groups are faster ?


Excerpt from the Regular Expression HOWTO
(http://docs.python.org/howto/regex.html#non-capturing-and-named-groups) :


-----------------------------------------------
It should be mentioned that there’s no performance difference in
searching between capturing and non-capturing groups; neither form is
any faster than the other.
-----------------------------------------------


Now from the Perl Regular Expression tutorial
(http://perldoc.perl.org/perlretut.html#Non-capturing-groupings) :


-----------------------------------------------
Because there is no extraction, non-capturing groupings are faster than
capturing groupings.
-----------------------------------------------


The second assertion sounds more likely. It seems very odd that Python
and Perl implementations are divergent on this point. Any opinion ?


--
**
At least in Perl's case, it is true. I tested and using (?:...) is much faster than ().

Of course, it takes a few seconds for dozen million matches...

Octavian

 

[candide]

Le 03/01/2012 12:56, Devin Jeanpierre a écrit :

The Python documentation oversimplifies.

You meant Perl Documentation, didn't you ?


It's a commun opinion that non-capturing groups have a price (minor),
for instance Jan Goyvaerts, a well known regular expression guru,
refering to Python code, tells :


non-capturing groups (...) offer (slightly) better performance as the
regex engine doesn't have to keep track of the text matched by
non-capturing groups.


[link is there :
http://stackoverflow.com/questions/...xpressions-non-capturing-group-is-not-working]



It seems Javascript performs better respect to non-capturing groups :
http://jsperf.com/regex-capture-vs-non-capture

The same for java : http://eyalsch.wordpress.com/2009/05/21/regex/
(no benchmarks).

For my part, Python tests didn't show any kind of significative penality.

 

[Devin Jeanpierre]

You meant Perl Documentation, didn't you ?

I guess that works too. I did mean Python, though -- its intent is to
say "you shouldn't worry about this", but in the process it says "this
does not exist" (a lie).

"slightly better performance" would be accurate, as said by Goyvaerts/

-- Devin

Le 03/01/2012 12:56, Devin Jeanpierre a écrit :

The Python documentation oversimplifies.

You meant Perl Documentation, didn't you ?


It's a commun opinion that non-capturing groups have a price (minor), for
instance Jan Goyvaerts, a well known regular expression guru, refering to
Python code, tells :


non-capturing groups (...)  offer (slightly) better performance as the regex
engine doesn't have to keep track of the text matched by non-capturing
groups.


[link is there :
http://stackoverflow.com/questions/...xpressions-non-capturing-group-is-not-working]



It seems Javascript performs better respect to non-capturing groups :
http://jsperf.com/regex-capture-vs-non-capture

The same for java : http://eyalsch.wordpress.com/2009/05/21/regex/
(no benchmarks).

For my part, Python tests didn't show any kind of significative penality.

 

[Octavian Rasnita]

From: "Devin Jeanpierre" <[email protected]>
Subject: Re: Regular expression : non capturing groups are faster ?

I guess that works too. I did mean Python, though -- its intent is to
say "you shouldn't worry about this", but in the process it says "this
does not exist" (a lie).

**
However, the Perl documentation doesn't lie.

I tested 10 million matches on my computer using capturing groups and it took ~ 6 seconds, but only ~ 2 seconds with non-capturing params.

So yes, it is very fast anyway, but ~ 3 times faster with non-capturing params, so there is a difference.

Octavian

 

[Devin Jeanpierre]

I tested 10 million matches on my computer using capturing groups and it took ~ 6 seconds, but only ~ 2 seconds with non-capturing params.

Are you talking about Python or Perl? I can't reproduce this in
Python. Best I can do is a 3:4 ratio between running times. ('(a)*
versus '(?:a)*)

Also, wouldn't say "very fast". Compare those two groups with 'a*'.
I'm not sure what's going on there.

-- Devin