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> 8Return to the <a href="index.html">PCRE2 index page</a>. 9</p> 10<p> 11This page is part of the PCRE2 HTML documentation. It was generated 12automatically from the original man page. If there is any nonsense in it, 13please 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 AND HEAP 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> 25Two aspects of performance are discussed below: memory usage and processing 26time. The way you express your pattern as a regular expression can affect both 27of them. 28</P> 29<br><a name="SEC2" href="#TOC1">COMPILED PATTERN MEMORY USAGE</a><br> 30<P> 31Patterns are compiled by PCRE2 into a reasonably efficient interpretive code, 32so that most simple patterns do not use much memory for storing the compiled 33version. However, there is one case where the memory usage of a compiled 34pattern can be unexpectedly large. If a parenthesized group has a quantifier 35with a minimum greater than 1 and/or a limited maximum, the whole group is 36repeated in the compiled code. For example, the pattern 37<pre> 38 (abc|def){2,4} 39</pre> 40is 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 45the repetitions can be independently maintained.) 46</P> 47<P> 48For regular expressions whose quantifiers use only small numbers, this is not 49usually a problem. However, if the numbers are large, and particularly if such 50repetitions are nested, the memory usage can become an embarrassment. For 51example, the very simple pattern 52<pre> 53 ((ab){1,1000}c){1,3} 54</pre> 55uses over 50KiB when compiled using the 8-bit library. When PCRE2 is 56compiled with its default internal pointer size of two bytes, the size limit on 57a compiled pattern is 65535 code units in the 8-bit and 16-bit libraries, and 58this is reached with the above pattern if the outer repetition is increased 59from 3 to 4. PCRE2 can be compiled to use larger internal pointers and thus 60handle larger compiled patterns, but it is better to try to rewrite your 61pattern to use less memory if you can. 62</P> 63<P> 64One way of reducing the memory usage for such patterns is to make use of 65PCRE2's 66<a href="pcre2pattern.html#subpatternsassubroutines">"subroutine"</a> 67facility. Re-writing the above pattern as 68<pre> 69 ((ab)(?2){0,999}c)(?1){0,2} 70</pre> 71reduces the memory requirements to around 16KiB, and indeed it remains under 7220KiB even with the outer repetition increased to 100. However, this kind of 73pattern is not always exactly equivalent, because any captures within 74subroutine calls are lost when the subroutine completes. If this is not a 75problem, this kind of rewriting will allow you to process patterns that PCRE2 76cannot otherwise handle. The matching performance of the two different versions 77of the pattern are roughly the same. (This applies from release 10.30 - things 78were different in earlier releases.) 79</P> 80<br><a name="SEC3" href="#TOC1">STACK AND HEAP USAGE AT RUN TIME</a><br> 81<P> 82From release 10.30, the interpretive (non-JIT) version of <b>pcre2_match()</b> 83uses very little system stack at run time. In earlier releases recursive 84function calls could use a great deal of stack, and this could cause problems, 85but this usage has been eliminated. Backtracking positions are now explicitly 86remembered in memory frames controlled by the code. 87</P> 88<P> 89The size of each frame depends on the size of pointer variables and the number 90of capturing parenthesized groups in the pattern being matched. On a 64-bit 91system the frame size for a pattern with no captures is 128 bytes. For each 92capturing group the size increases by 16 bytes. 93</P> 94<P> 95Until release 10.41, an initial 20KiB frames vector was allocated on the system 96stack, but this still caused some issues for multi-thread applications where 97each thread has a very small stack. From release 10.41 backtracking memory 98frames are always held in heap memory. An initial heap allocation is obtained 99the first time any match data block is passed to <b>pcre2_match()</b>. This is 100remembered with the match data block and re-used if that block is used for 101another match. It is freed when the match data block itself is freed. 102</P> 103<P> 104The size of the initial block is the larger of 20KiB or ten times the pattern's 105frame size, unless the heap limit is less than this, in which case the heap 106limit is used. If the initial block proves to be too small during matching, it 107is replaced by a larger block, subject to the heap limit. The heap limit is 108checked only when a new block is to be allocated. Reducing the heap limit 109between calls to <b>pcre2_match()</b> with the same match data block does not 110affect the saved block. 111</P> 112<P> 113In contrast to <b>pcre2_match()</b>, <b>pcre2_dfa_match()</b> does use recursive 114function calls, but only for processing atomic groups, lookaround assertions, 115and recursion within the pattern. The original version of the code used to 116allocate quite large internal workspace vectors on the stack, which caused some 117problems for some patterns in environments with small stacks. From release 11810.32 the code for <b>pcre2_dfa_match()</b> has been re-factored to use heap 119memory when necessary for internal workspace when recursing, though recursive 120function calls are still used. 121</P> 122<P> 123The "match depth" parameter can be used to limit the depth of function 124recursion, and the "match heap" parameter to limit heap memory in 125<b>pcre2_dfa_match()</b>. 126</P> 127<br><a name="SEC4" href="#TOC1">PROCESSING TIME</a><br> 128<P> 129Certain items in regular expression patterns are processed more efficiently 130than others. It is more efficient to use a character class like [aeiou] than a 131set of single-character alternatives such as (a|e|i|o|u). In general, the 132simplest construction that provides the required behaviour is usually the most 133efficient. Jeffrey Friedl's book contains a lot of useful general discussion 134about optimizing regular expressions for efficient performance. This document 135contains a few observations about PCRE2. 136</P> 137<P> 138Using Unicode character properties (the \p, \P, and \X escapes) is slow, 139because PCRE2 has to use a multi-stage table lookup whenever it needs a 140character's property. If you can find an alternative pattern that does not use 141character properties, it will probably be faster. 142</P> 143<P> 144By default, the escape sequences \b, \d, \s, and \w, and the POSIX 145character classes such as [:alpha:] do not use Unicode properties, partly for 146backwards compatibility, and partly for performance reasons. However, you can 147set the PCRE2_UCP option or start the pattern with (*UCP) if you want Unicode 148character properties to be used. This can double the matching time for items 149such as \d, when matched with <b>pcre2_match()</b>; the performance loss is 150less with a DFA matching function, and in both cases there is not much 151difference for \b. 152</P> 153<P> 154When a pattern begins with .* not in atomic parentheses, nor in parentheses 155that are the subject of a backreference, and the PCRE2_DOTALL option is set, 156the pattern is implicitly anchored by PCRE2, since it can match only at the 157start of a subject string. If the pattern has multiple top-level branches, they 158must all be anchorable. The optimization can be disabled by the 159PCRE2_NO_DOTSTAR_ANCHOR option, and is automatically disabled if the pattern 160contains (*PRUNE) or (*SKIP). 161</P> 162<P> 163If PCRE2_DOTALL is not set, PCRE2 cannot make this optimization, because the 164dot metacharacter does not then match a newline, and if the subject string 165contains newlines, the pattern may match from the character immediately 166following one of them instead of from the very start. For example, the pattern 167<pre> 168 .*second 169</pre> 170matches the subject "first\nand second" (where \n stands for a newline 171character), with the match starting at the seventh character. In order to do 172this, PCRE2 has to retry the match starting after every newline in the subject. 173</P> 174<P> 175If you are using such a pattern with subject strings that do not contain 176newlines, the best performance is obtained by setting PCRE2_DOTALL, or starting 177the pattern with ^.* or ^.*? to indicate explicit anchoring. That saves PCRE2 178from having to scan along the subject looking for a newline to restart at. 179</P> 180<P> 181Beware of patterns that contain nested indefinite repeats. These can take a 182long time to run when applied to a string that does not match. Consider the 183pattern fragment 184<pre> 185 ^(a+)* 186</pre> 187This can match "aaaa" in 16 different ways, and this number increases very 188rapidly as the string gets longer. (The * repeat can match 0, 1, 2, 3, or 4 189times, and for each of those cases other than 0 or 4, the + repeats can match 190different numbers of times.) When the remainder of the pattern is such that the 191entire match is going to fail, PCRE2 has in principle to try every possible 192variation, and this can take an extremely long time, even for relatively short 193strings. 194</P> 195<P> 196An optimization catches some of the more simple cases such as 197<pre> 198 (a+)*b 199</pre> 200where a literal character follows. Before embarking on the standard matching 201procedure, PCRE2 checks that there is a "b" later in the subject string, and if 202there is not, it fails the match immediately. However, when there is no 203following literal this optimization cannot be used. You can see the difference 204by comparing the behaviour of 205<pre> 206 (a+)*\d 207</pre> 208with the pattern above. The former gives a failure almost instantly when 209applied to a whole line of "a" characters, whereas the latter takes an 210appreciable time with strings longer than about 20 characters. 211</P> 212<P> 213In many cases, the solution to this kind of performance issue is to use an 214atomic group or a possessive quantifier. This can often reduce memory 215requirements as well. As another example, consider this pattern: 216<pre> 217 ([^<]|<(?!inet))+ 218</pre> 219It matches from wherever it starts until it encounters "<inet" or the end of 220the data, and is the kind of pattern that might be used when processing an XML 221file. Each iteration of the outer parentheses matches either one character that 222is not "<" or a "<" that is not followed by "inet". However, each time a 223parenthesis is processed, a backtracking position is passed, so this 224formulation uses a memory frame for each matched character. For a long string, 225a lot of memory is required. Consider now this rewritten pattern, which matches 226exactly the same strings: 227<pre> 228 ([^<]++|<(?!inet))+ 229</pre> 230This runs much faster, because sequences of characters that do not contain "<" 231are "swallowed" in one item inside the parentheses, and a possessive quantifier 232is used to stop any backtracking into the runs of non-"<" characters. This 233version also uses a lot less memory because entry to a new set of parentheses 234happens only when a "<" character that is not followed by "inet" is encountered 235(and we assume this is relatively rare). 236</P> 237<P> 238This example shows that one way of optimizing performance when matching long 239subject strings is to write repeated parenthesized subpatterns to match more 240than one character whenever possible. 241</P> 242<br><b> 243SETTING RESOURCE LIMITS 244</b><br> 245<P> 246You can set limits on the amount of processing that takes place when matching, 247and on the amount of heap memory that is used. The default values of the limits 248are very large, and unlikely ever to operate. They can be changed when PCRE2 is 249built, and they can also be set when <b>pcre2_match()</b> or 250<b>pcre2_dfa_match()</b> is called. For details of these interfaces, see the 251<a href="pcre2build.html"><b>pcre2build</b></a> 252documentation and the section entitled 253<a href="pcre2api.html#matchcontext">"The match context"</a> 254in the 255<a href="pcre2api.html"><b>pcre2api</b></a> 256documentation. 257</P> 258<P> 259The <b>pcre2test</b> test program has a modifier called "find_limits" which, if 260applied to a subject line, causes it to find the smallest limits that allow a 261pattern to match. This is done by repeatedly matching with different limits. 262</P> 263<br><a name="SEC5" href="#TOC1">AUTHOR</a><br> 264<P> 265Philip Hazel 266<br> 267Retired from University Computing Service 268<br> 269Cambridge, England. 270<br> 271</P> 272<br><a name="SEC6" href="#TOC1">REVISION</a><br> 273<P> 274Last updated: 27 July 2022 275<br> 276Copyright © 1997-2022 University of Cambridge. 277<br> 278<p> 279Return to the <a href="index.html">PCRE2 index page</a>. 280</p> 281