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