221 lines
8.1 KiB
HTML
221 lines
8.1 KiB
HTML
|
|
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
|
|
<HTML><HEAD><TITLE>Man page of PCREPERFORM</TITLE>
|
|
</HEAD><BODY>
|
|
<H1>PCREPERFORM</H1>
|
|
Section: C Library Functions (3)<BR>Updated: 09 January 2012<BR><A HREF="#index">Index</A>
|
|
<A HREF="/cgi-bin/man/man2html">Return to Main Contents</A><HR>
|
|
|
|
<A NAME="lbAB"> </A>
|
|
<H2>NAME</H2>
|
|
|
|
PCRE - Perl-compatible regular expressions
|
|
<A NAME="lbAC"> </A>
|
|
<H2>PCRE PERFORMANCE</H2>
|
|
|
|
|
|
<P>
|
|
Two aspects of performance are discussed below: memory usage and processing
|
|
time. The way you express your pattern as a regular expression can affect both
|
|
of them.
|
|
<A NAME="lbAD"> </A>
|
|
<H2>COMPILED PATTERN MEMORY USAGE</H2>
|
|
|
|
|
|
<P>
|
|
Patterns are compiled by PCRE into a reasonably efficient interpretive code, so
|
|
that most simple patterns do not use much memory. However, there is one case
|
|
where the memory usage of a compiled pattern can be unexpectedly large. If a
|
|
parenthesized subpattern has a quantifier with a minimum greater than 1 and/or
|
|
a limited maximum, the whole subpattern is repeated in the compiled code. For
|
|
example, the pattern
|
|
<P>
|
|
<BR> (abc|def){2,4}
|
|
<P>
|
|
is compiled as if it were
|
|
<P>
|
|
<BR> (abc|def)(abc|def)((abc|def)(abc|def)?)?
|
|
<P>
|
|
(Technical aside: It is done this way so that backtrack points within each of
|
|
the repetitions can be independently maintained.)
|
|
<P>
|
|
|
|
For regular expressions whose quantifiers use only small numbers, this is not
|
|
usually a problem. However, if the numbers are large, and particularly if such
|
|
repetitions are nested, the memory usage can become an embarrassment. For
|
|
example, the very simple pattern
|
|
<P>
|
|
<BR> ((ab){1,1000}c){1,3}
|
|
<P>
|
|
uses 51K bytes when compiled using the 8-bit library. When PCRE is compiled
|
|
with its default internal pointer size of two bytes, the size limit on a
|
|
compiled pattern is 64K data units, and this is reached with the above pattern
|
|
if the outer repetition is increased from 3 to 4. PCRE can be compiled to use
|
|
larger internal pointers and thus handle larger compiled patterns, but it is
|
|
better to try to rewrite your pattern to use less memory if you can.
|
|
<P>
|
|
|
|
One way of reducing the memory usage for such patterns is to make use of PCRE's
|
|
|
|
|
|
"subroutine"
|
|
|
|
facility. Re-writing the above pattern as
|
|
<P>
|
|
<BR> ((ab)(?2){0,999}c)(?1){0,2}
|
|
<P>
|
|
reduces the memory requirements to 18K, and indeed it remains under 20K even
|
|
with the outer repetition increased to 100. However, this pattern is not
|
|
exactly equivalent, because the "subroutine" calls are treated as
|
|
|
|
|
|
atomic groups
|
|
|
|
into which there can be no backtracking if there is a subsequent matching
|
|
failure. Therefore, PCRE cannot do this kind of rewriting automatically.
|
|
Furthermore, there is a noticeable loss of speed when executing the modified
|
|
pattern. Nevertheless, if the atomic grouping is not a problem and the loss of
|
|
speed is acceptable, this kind of rewriting will allow you to process patterns
|
|
that PCRE cannot otherwise handle.
|
|
<A NAME="lbAE"> </A>
|
|
<H2>STACK USAGE AT RUN TIME</H2>
|
|
|
|
|
|
<P>
|
|
When <B>pcre_exec()</B> or <B>pcre[16|32]_exec()</B> is used for matching, certain
|
|
kinds of pattern can cause it to use large amounts of the process stack. In
|
|
some environments the default process stack is quite small, and if it runs out
|
|
the result is often SIGSEGV. This issue is probably the most frequently raised
|
|
problem with PCRE. Rewriting your pattern can often help. The
|
|
|
|
<B>pcrestack</B>
|
|
|
|
documentation discusses this issue in detail.
|
|
<A NAME="lbAF"> </A>
|
|
<H2>PROCESSING TIME</H2>
|
|
|
|
|
|
<P>
|
|
Certain items in regular expression patterns are processed more efficiently
|
|
than others. It is more efficient to use a character class like [aeiou] than a
|
|
set of single-character alternatives such as (a|e|i|o|u). In general, the
|
|
simplest construction that provides the required behaviour is usually the most
|
|
efficient. Jeffrey Friedl's book contains a lot of useful general discussion
|
|
about optimizing regular expressions for efficient performance. This document
|
|
contains a few observations about PCRE.
|
|
<P>
|
|
|
|
Using Unicode character properties (the \p, \P, and \X escapes) is slow,
|
|
because PCRE has to use a multi-stage table lookup whenever it needs a
|
|
character's property. If you can find an alternative pattern that does not use
|
|
character properties, it will probably be faster.
|
|
<P>
|
|
|
|
By default, the escape sequences \b, \d, \s, and \w, and the POSIX
|
|
character classes such as [:alpha:] do not use Unicode properties, partly for
|
|
backwards compatibility, and partly for performance reasons. However, you can
|
|
set PCRE_UCP if you want Unicode character properties to be used. This can
|
|
double the matching time for items such as \d, when matched with
|
|
a traditional matching function; the performance loss is less with
|
|
a DFA matching function, and in both cases there is not much difference for
|
|
\b.
|
|
<P>
|
|
|
|
When a pattern begins with .* not in parentheses, or in parentheses that are
|
|
not the subject of a backreference, and the PCRE_DOTALL option is set, the
|
|
pattern is implicitly anchored by PCRE, since it can match only at the start of
|
|
a subject string. However, if PCRE_DOTALL is not set, PCRE cannot make this
|
|
optimization, because the . metacharacter does not then match a newline, and if
|
|
the subject string contains newlines, the pattern may match from the character
|
|
immediately following one of them instead of from the very start. For example,
|
|
the pattern
|
|
<P>
|
|
<BR> .*second
|
|
<P>
|
|
matches the subject "first\nand second" (where \n stands for a newline
|
|
character), with the match starting at the seventh character. In order to do
|
|
this, PCRE has to retry the match starting after every newline in the subject.
|
|
<P>
|
|
|
|
If you are using such a pattern with subject strings that do not contain
|
|
newlines, the best performance is obtained by setting PCRE_DOTALL, or starting
|
|
the pattern with ^.* or ^.*? to indicate explicit anchoring. That saves PCRE
|
|
from having to scan along the subject looking for a newline to restart at.
|
|
<P>
|
|
|
|
Beware of patterns that contain nested indefinite repeats. These can take a
|
|
long time to run when applied to a string that does not match. Consider the
|
|
pattern fragment
|
|
<P>
|
|
<BR> ^(a+)*
|
|
<P>
|
|
This can match "aaaa" in 16 different ways, and this number increases very
|
|
rapidly as the string gets longer. (The * repeat can match 0, 1, 2, 3, or 4
|
|
times, and for each of those cases other than 0 or 4, the + repeats can match
|
|
different numbers of times.) When the remainder of the pattern is such that the
|
|
entire match is going to fail, PCRE has in principle to try every possible
|
|
variation, and this can take an extremely long time, even for relatively short
|
|
strings.
|
|
<P>
|
|
|
|
An optimization catches some of the more simple cases such as
|
|
<P>
|
|
<BR> (a+)*b
|
|
<P>
|
|
where a literal character follows. Before embarking on the standard matching
|
|
procedure, PCRE checks that there is a "b" later in the subject string, and if
|
|
there is not, it fails the match immediately. However, when there is no
|
|
following literal this optimization cannot be used. You can see the difference
|
|
by comparing the behaviour of
|
|
<P>
|
|
<BR> (a+)*\d
|
|
<P>
|
|
with the pattern above. The former gives a failure almost instantly when
|
|
applied to a whole line of "a" characters, whereas the latter takes an
|
|
appreciable time with strings longer than about 20 characters.
|
|
<P>
|
|
|
|
In many cases, the solution to this kind of performance issue is to use an
|
|
atomic group or a possessive quantifier.
|
|
<A NAME="lbAG"> </A>
|
|
<H2>AUTHOR</H2>
|
|
|
|
|
|
<P>
|
|
<PRE>
|
|
Philip Hazel
|
|
University Computing Service
|
|
Cambridge CB2 3QH, England.
|
|
</PRE>
|
|
|
|
<A NAME="lbAH"> </A>
|
|
<H2>REVISION</H2>
|
|
|
|
|
|
<P>
|
|
<PRE>
|
|
Last updated: 25 August 2012
|
|
Copyright (c) 1997-2012 University of Cambridge.
|
|
</PRE>
|
|
|
|
<P>
|
|
|
|
<HR>
|
|
<A NAME="index"> </A><H2>Index</H2>
|
|
<DL>
|
|
<DT id="1"><A HREF="#lbAB">NAME</A><DD>
|
|
<DT id="2"><A HREF="#lbAC">PCRE PERFORMANCE</A><DD>
|
|
<DT id="3"><A HREF="#lbAD">COMPILED PATTERN MEMORY USAGE</A><DD>
|
|
<DT id="4"><A HREF="#lbAE">STACK USAGE AT RUN TIME</A><DD>
|
|
<DT id="5"><A HREF="#lbAF">PROCESSING TIME</A><DD>
|
|
<DT id="6"><A HREF="#lbAG">AUTHOR</A><DD>
|
|
<DT id="7"><A HREF="#lbAH">REVISION</A><DD>
|
|
</DL>
|
|
<HR>
|
|
This document was created by
|
|
<A HREF="/cgi-bin/man/man2html">man2html</A>,
|
|
using the manual pages.<BR>
|
|
Time: 00:05:52 GMT, March 31, 2021
|
|
</BODY>
|
|
</HTML>
|