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