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 memory usage can be unexpectedly large. When a parenthesized
19 subpattern has a quantifier with a minimum greater than 1 and/or a lim‐
20 ited maximum, the whole subpattern is repeated in the compiled code.
21 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 Certain items in regular expression patterns are processed more effi‐
65 ciently than others. It is more efficient to use a character class like
66 [aeiou] than a set of single-character alternatives such as
67 (a|e|i|o|u). In general, the simplest construction that provides the
68 required behaviour is usually the most efficient. Jeffrey Friedl's book
69 contains a lot of useful general discussion about optimizing regular
70 expressions for efficient performance. This document contains a few
71 observations about PCRE.
72 Using Unicode character properties (the \p, \P, and \X escapes) is
74 slow, because PCRE has to scan a structure that contains data for over
75 fifteen thousand characters whenever it needs a character's property.
76 If you can find an alternative pattern that does not use character
77 properties, it will probably be faster.
78 When a pattern begins with .* not in parentheses, or in parentheses
80 that are not the subject of a backreference, and the PCRE_DOTALL option
81 is set, the pattern is implicitly anchored by PCRE, since it can match
82 only at the start of a subject string. However, if PCRE_DOTALL is not
83 set, PCRE cannot make this optimization, because the . metacharacter
84 does not then match a newline, and if the subject string contains new‐
85 lines, the pattern may match from the character immediately following
86 one of them instead of from the very start. For example, the pattern
87 .*second
89 matches the subject "first\nand second" (where \n stands for a newline
91 character), with the match starting at the seventh character. In order
92 to do this, PCRE has to retry the match starting after every newline in
93 the subject.
94 If you are using such a pattern with subject strings that do not con‐
96 tain newlines, the best performance is obtained by setting PCRE_DOTALL,
97 or starting the pattern with ^.* or ^.*? to indicate explicit anchor‐
98 ing. That saves PCRE from having to scan along the subject looking for
99 a newline to restart at.
100 Beware of patterns that contain nested indefinite repeats. These can
102 take a long time to run when applied to a string that does not match.
103 Consider the pattern fragment
104 ^(a+)*
106 This can match "aaaa" in 16 different ways, and this number increases
108 very rapidly as the string gets longer. (The * repeat can match 0, 1,
109 2, 3, or 4 times, and for each of those cases other than 0 or 4, the +
110 repeats can match different numbers of times.) When the remainder of
111 the pattern is such that the entire match is going to fail, PCRE has in
112 principle to try every possible variation, and this can take an
113 extremely long time, even for relatively short strings.
114 An optimization catches some of the more simple cases such as
116 (a+)*b
118 where a literal character follows. Before embarking on the standard
120 matching procedure, PCRE checks that there is a "b" later in the sub‐
121 ject string, and if there is not, it fails the match immediately. How‐
122 ever, when there is no following literal this optimization cannot be
123 used. You can see the difference by comparing the behaviour of
124 (a+)*\d
126 with the pattern above. The former gives a failure almost instantly
128 when applied to a whole line of "a" characters, whereas the latter
129 takes an appreciable time with strings longer than about 20 characters.
130 In many cases, the solution to this kind of performance issue is to use
132 an atomic group or a possessive quantifier.
133
135 Philip Hazel
137 University Computing Service
138 Cambridge CB2 3QH, England.
139
141 Last updated: 06 March 2007
143 Copyright (c) 1997-2007 University of Cambridge.
144 PCREPERFORM(3)