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