Return to pcreperform.3 CVS log

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

Annotation of embedaddon/pcre/doc/pcreperform.3, revision 1.1.1.3

1.1.1.3 ! misho       1: .TH PCREPERFORM 3 "09 January 2012" "PCRE 8.30"
1.1       misho       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
1.1.1.2   misho      14: Patterns are compiled by PCRE into a reasonably efficient interpretive code, so
                     15: that most simple patterns do not use much memory. However, there is one case
                     16: where the memory usage of a compiled pattern can be unexpectedly large. If a
1.1       misho      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
1.1.1.2   misho      37: uses 51K bytes when compiled using the 8-bit library. When PCRE is compiled
                     38: with its default internal pointer size of two bytes, the size limit on a
                     39: compiled pattern is 64K data units, and this is reached with the above pattern
                     40: if the outer repetition is increased from 3 to 4. PCRE can be compiled to use
                     41: larger internal pointers and thus handle larger compiled patterns, but it is
                     42: better to try to rewrite your pattern to use less memory if you can.
1.1       misho      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
1.1.1.2   misho      71: When \fBpcre_exec()\fP or \fBpcre16_exec()\fP is used for matching, certain
                     72: kinds of pattern can cause it to use large amounts of the process stack. In
                     73: some environments the default process stack is quite small, and if it runs out
                     74: the result is often SIGSEGV. This issue is probably the most frequently raised
                     75: problem with PCRE. Rewriting your pattern can often help. The
1.1       misho      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
1.1.1.2   misho     104: a traditional matching function; the performance loss is less with
                    105: a DFA matching function, and in both cases there is not much difference for
                    106: \eb.
1.1       misho     107: .P
                    108: When a pattern begins with .* not in parentheses, or in parentheses that are
                    109: not the subject of a backreference, and the PCRE_DOTALL option is set, the
                    110: pattern is implicitly anchored by PCRE, since it can match only at the start of
                    111: a subject string. However, if PCRE_DOTALL is not set, PCRE cannot make this
                    112: optimization, because the . metacharacter does not then match a newline, and if
                    113: the subject string contains newlines, the pattern may match from the character
                    114: immediately following one of them instead of from the very start. For example,
                    115: the pattern
                    116: .sp
                    117:   .*second
                    118: .sp
                    119: matches the subject "first\enand second" (where \en stands for a newline
                    120: character), with the match starting at the seventh character. In order to do
                    121: this, PCRE has to retry the match starting after every newline in the subject.
                    122: .P
                    123: If you are using such a pattern with subject strings that do not contain
                    124: newlines, the best performance is obtained by setting PCRE_DOTALL, or starting
                    125: the pattern with ^.* or ^.*? to indicate explicit anchoring. That saves PCRE
                    126: from having to scan along the subject looking for a newline to restart at.
                    127: .P
                    128: Beware of patterns that contain nested indefinite repeats. These can take a
                    129: long time to run when applied to a string that does not match. Consider the
                    130: pattern fragment
                    131: .sp
                    132:   ^(a+)*
                    133: .sp
                    134: This can match "aaaa" in 16 different ways, and this number increases very
                    135: rapidly as the string gets longer. (The * repeat can match 0, 1, 2, 3, or 4
                    136: times, and for each of those cases other than 0 or 4, the + repeats can match
                    137: different numbers of times.) When the remainder of the pattern is such that the
                    138: entire match is going to fail, PCRE has in principle to try every possible
                    139: variation, and this can take an extremely long time, even for relatively short
                    140: strings.
                    141: .P
                    142: An optimization catches some of the more simple cases such as
                    143: .sp
                    144:   (a+)*b
                    145: .sp
                    146: where a literal character follows. Before embarking on the standard matching
                    147: procedure, PCRE checks that there is a "b" later in the subject string, and if
                    148: there is not, it fails the match immediately. However, when there is no
                    149: following literal this optimization cannot be used. You can see the difference
                    150: by comparing the behaviour of
                    151: .sp
                    152:   (a+)*\ed
                    153: .sp
                    154: with the pattern above. The former gives a failure almost instantly when
                    155: applied to a whole line of "a" characters, whereas the latter takes an
                    156: appreciable time with strings longer than about 20 characters.
                    157: .P
                    158: In many cases, the solution to this kind of performance issue is to use an
                    159: atomic group or a possessive quantifier.
                    160: .
                    161: .
                    162: .SH AUTHOR
                    163: .rs
                    164: .sp
                    165: .nf
                    166: Philip Hazel
                    167: University Computing Service
                    168: Cambridge CB2 3QH, England.
                    169: .fi
                    170: .
                    171: .
                    172: .SH REVISION
                    173: .rs
                    174: .sp
                    175: .nf
1.1.1.2   misho     176: Last updated: 09 January 2012
                    177: Copyright (c) 1997-2012 University of Cambridge.
1.1       misho     178: .fi