Return to pcreperform.3 CVS log

Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / pcre / doc

pcre

    1: .TH PCREPERFORM 3
    2: .SH NAME
    3: PCRE - Perl-compatible regular expressions
    4: .SH "PCRE PERFORMANCE"
    5: .rs
    6: .sp
    7: Two aspects of performance are discussed below: memory usage and processing
    8: time. The way you express your pattern as a regular expression can affect both
    9: of them.
   10: .
   11: .SH "COMPILED PATTERN MEMORY USAGE"
   12: .rs
   13: .sp
   14: Patterns are compiled by PCRE into a reasonably efficient byte code, so that
   15: most simple patterns do not use much memory. However, there is one case where
   16: the memory usage of a compiled pattern can be unexpectedly large. If a
   17: parenthesized subpattern has a quantifier with a minimum greater than 1 and/or
   18: a limited maximum, the whole subpattern is repeated in the compiled code. For
   19: example, the pattern
   20: .sp
   21:   (abc|def){2,4}
   22: .sp
   23: is compiled as if it were
   24: .sp
   25:   (abc|def)(abc|def)((abc|def)(abc|def)?)?
   26: .sp
   27: (Technical aside: It is done this way so that backtrack points within each of
   28: the repetitions can be independently maintained.)
   29: .P
   30: For regular expressions whose quantifiers use only small numbers, this is not
   31: usually a problem. However, if the numbers are large, and particularly if such
   32: repetitions are nested, the memory usage can become an embarrassment. For
   33: example, the very simple pattern
   34: .sp
   35:   ((ab){1,1000}c){1,3}
   36: .sp
   37: uses 51K bytes when compiled. When PCRE is compiled with its default internal
   38: pointer size of two bytes, the size limit on a compiled pattern is 64K, and
   39: this is reached with the above pattern if the outer repetition is increased
   40: from 3 to 4. PCRE can be compiled to use larger internal pointers and thus
   41: handle larger compiled patterns, but it is better to try to rewrite your
   42: pattern to use less memory if you can.
   43: .P
   44: One way of reducing the memory usage for such patterns is to make use of PCRE's
   45: .\" HTML <a href="pcrepattern.html#subpatternsassubroutines">
   46: .\" </a>
   47: "subroutine"
   48: .\"
   49: facility. Re-writing the above pattern as
   50: .sp
   51:   ((ab)(?2){0,999}c)(?1){0,2}
   52: .sp
   53: reduces the memory requirements to 18K, and indeed it remains under 20K even
   54: with the outer repetition increased to 100. However, this pattern is not
   55: exactly equivalent, because the "subroutine" calls are treated as
   56: .\" HTML <a href="pcrepattern.html#atomicgroup">
   57: .\" </a>
   58: atomic groups
   59: .\"
   60: into which there can be no backtracking if there is a subsequent matching
   61: failure. Therefore, PCRE cannot do this kind of rewriting automatically.
   62: Furthermore, there is a noticeable loss of speed when executing the modified
   63: pattern. Nevertheless, if the atomic grouping is not a problem and the loss of
   64: speed is acceptable, this kind of rewriting will allow you to process patterns
   65: that PCRE cannot otherwise handle.
   66: .
   67: .
   68: .SH "STACK USAGE AT RUN TIME"
   69: .rs
   70: .sp
   71: When \fBpcre_exec()\fP is used for matching, certain kinds of pattern can cause
   72: it to use large amounts of the process stack. In some environments the default
   73: process stack is quite small, and if it runs out the result is often SIGSEGV.
   74: This issue is probably the most frequently raised problem with PCRE. Rewriting
   75: your pattern can often help. The
   76: .\" HREF
   77: \fBpcrestack\fP
   78: .\"
   79: documentation discusses this issue in detail.
   80: .
   81: .
   82: .SH "PROCESSING TIME"
   83: .rs
   84: .sp
   85: Certain items in regular expression patterns are processed more efficiently
   86: than others. It is more efficient to use a character class like [aeiou] than a
   87: set of single-character alternatives such as (a|e|i|o|u). In general, the
   88: simplest construction that provides the required behaviour is usually the most
   89: efficient. Jeffrey Friedl's book contains a lot of useful general discussion
   90: about optimizing regular expressions for efficient performance. This document
   91: contains a few observations about PCRE.
   92: .P
   93: Using Unicode character properties (the \ep, \eP, and \eX escapes) is slow,
   94: because PCRE has to scan a structure that contains data for over fifteen
   95: thousand characters whenever it needs a character's property. If you can find
   96: an alternative pattern that does not use character properties, it will probably
   97: be faster.
   98: .P
   99: By default, the escape sequences \eb, \ed, \es, and \ew, and the POSIX
  100: character classes such as [:alpha:] do not use Unicode properties, partly for
  101: backwards compatibility, and partly for performance reasons. However, you can
  102: set PCRE_UCP if you want Unicode character properties to be used. This can
  103: double the matching time for items such as \ed, when matched with
  104: \fBpcre_exec()\fP; the performance loss is less with \fBpcre_dfa_exec()\fP, and
  105: in both cases there is not much difference for \eb.
  106: .P
  107: When a pattern begins with .* not in parentheses, or in parentheses that are
  108: not the subject of a backreference, and the PCRE_DOTALL option is set, the
  109: pattern is implicitly anchored by PCRE, since it can match only at the start of
  110: a subject string. However, if PCRE_DOTALL is not set, PCRE cannot make this
  111: optimization, because the . metacharacter does not then match a newline, and if
  112: the subject string contains newlines, the pattern may match from the character
  113: immediately following one of them instead of from the very start. For example,
  114: the pattern
  115: .sp
  116:   .*second
  117: .sp
  118: matches the subject "first\enand second" (where \en stands for a newline
  119: character), with the match starting at the seventh character. In order to do
  120: this, PCRE has to retry the match starting after every newline in the subject.
  121: .P
  122: If you are using such a pattern with subject strings that do not contain
  123: newlines, the best performance is obtained by setting PCRE_DOTALL, or starting
  124: the pattern with ^.* or ^.*? to indicate explicit anchoring. That saves PCRE
  125: from having to scan along the subject looking for a newline to restart at.
  126: .P
  127: Beware of patterns that contain nested indefinite repeats. These can take a
  128: long time to run when applied to a string that does not match. Consider the
  129: pattern fragment
  130: .sp
  131:   ^(a+)*
  132: .sp
  133: This can match "aaaa" in 16 different ways, and this number increases very
  134: rapidly as the string gets longer. (The * repeat can match 0, 1, 2, 3, or 4
  135: times, and for each of those cases other than 0 or 4, the + repeats can match
  136: different numbers of times.) When the remainder of the pattern is such that the
  137: entire match is going to fail, PCRE has in principle to try every possible
  138: variation, and this can take an extremely long time, even for relatively short
  139: strings.
  140: .P
  141: An optimization catches some of the more simple cases such as
  142: .sp
  143:   (a+)*b
  144: .sp
  145: where a literal character follows. Before embarking on the standard matching
  146: procedure, PCRE checks that there is a "b" later in the subject string, and if
  147: there is not, it fails the match immediately. However, when there is no
  148: following literal this optimization cannot be used. You can see the difference
  149: by comparing the behaviour of
  150: .sp
  151:   (a+)*\ed
  152: .sp
  153: with the pattern above. The former gives a failure almost instantly when
  154: applied to a whole line of "a" characters, whereas the latter takes an
  155: appreciable time with strings longer than about 20 characters.
  156: .P
  157: In many cases, the solution to this kind of performance issue is to use an
  158: atomic group or a possessive quantifier.
  159: .
  160: .
  161: .SH AUTHOR
  162: .rs
  163: .sp
  164: .nf
  165: Philip Hazel
  166: University Computing Service
  167: Cambridge CB2 3QH, England.
  168: .fi
  169: .
  170: .
  171: .SH REVISION
  172: .rs
  173: .sp
  174: .nf
  175: Last updated: 16 May 2010
  176: Copyright (c) 1997-2010 University of Cambridge.
  177: .fi