--- /dev/null
+.TH PCRE2PERFORM 3 "25 April 2018" "PCRE2 10.32"
+.SH NAME
+PCRE2 - Perl-compatible regular expressions (revised API)
+.SH "PCRE2 PERFORMANCE"
+.rs
+.sp
+Two aspects of performance are discussed below: memory usage and processing
+time. The way you express your pattern as a regular expression can affect both
+of them.
+.
+.SH "COMPILED PATTERN MEMORY USAGE"
+.rs
+.sp
+Patterns are compiled by PCRE2 into a reasonably efficient interpretive code,
+so that most simple patterns do not use much memory for storing the compiled
+version. However, there is one case where the memory usage of a compiled
+pattern can be unexpectedly large. If a parenthesized subpattern has a
+quantifier with a minimum greater than 1 and/or a limited maximum, the whole
+subpattern is repeated in the compiled code. For example, the pattern
+.sp
+ (abc|def){2,4}
+.sp
+is compiled as if it were
+.sp
+ (abc|def)(abc|def)((abc|def)(abc|def)?)?
+.sp
+(Technical aside: It is done this way so that backtrack points within each of
+the repetitions can be independently maintained.)
+.P
+For regular expressions whose quantifiers use only small numbers, this is not
+usually a problem. However, if the numbers are large, and particularly if such
+repetitions are nested, the memory usage can become an embarrassment. For
+example, the very simple pattern
+.sp
+ ((ab){1,1000}c){1,3}
+.sp
+uses over 50KiB when compiled using the 8-bit library. When PCRE2 is
+compiled with its default internal pointer size of two bytes, the size limit on
+a compiled pattern is 65535 code units in the 8-bit and 16-bit libraries, and
+this is reached with the above pattern if the outer repetition is increased
+from 3 to 4. PCRE2 can be compiled to use larger internal pointers and thus
+handle larger compiled patterns, but it is better to try to rewrite your
+pattern to use less memory if you can.
+.P
+One way of reducing the memory usage for such patterns is to make use of
+PCRE2's
+.\" HTML <a href="pcre2pattern.html#subpatternsassubroutines">
+.\" </a>
+"subroutine"
+.\"
+facility. Re-writing the above pattern as
+.sp
+ ((ab)(?2){0,999}c)(?1){0,2}
+.sp
+reduces the memory requirements to around 16KiB, and indeed it remains under
+20KiB even with the outer repetition increased to 100. However, this kind of
+pattern is not always exactly equivalent, because any captures within
+subroutine calls are lost when the subroutine completes. If this is not a
+problem, this kind of rewriting will allow you to process patterns that PCRE2
+cannot otherwise handle. The matching performance of the two different versions
+of the pattern are roughly the same. (This applies from release 10.30 - things
+were different in earlier releases.)
+.
+.
+.SH "STACK AND HEAP USAGE AT RUN TIME"
+.rs
+.sp
+From release 10.30, the interpretive (non-JIT) version of \fBpcre2_match()\fP
+uses very little system stack at run time. In earlier releases recursive
+function calls could use a great deal of stack, and this could cause problems,
+but this usage has been eliminated. Backtracking positions are now explicitly
+remembered in memory frames controlled by the code. An initial 20KiB vector of
+frames is allocated on the system stack (enough for about 100 frames for small
+patterns), but if this is insufficient, heap memory is used. The amount of heap
+memory can be limited; if the limit is set to zero, only the initial stack
+vector is used. Rewriting patterns to be time-efficient, as described below,
+may also reduce the memory requirements.
+.P
+In contrast to \fBpcre2_match()\fP, \fBpcre2_dfa_match()\fP does use recursive
+function calls, but only for processing atomic groups, lookaround assertions,
+and recursion within the pattern. The original version of the code used to
+allocate quite large internal workspace vectors on the stack, which caused some
+problems for some patterns in environments with small stacks. From release
+10.32 the code for \fBpcre2_dfa_match()\fP has been re-factored to use heap
+memory when necessary for internal workspace when recursing, though recursive
+function calls are still used.
+.P
+The "match depth" parameter can be used to limit the depth of function
+recursion, and the "match heap" parameter to limit heap memory in
+\fBpcre2_dfa_match()\fP.
+.
+.
+.SH "PROCESSING TIME"
+.rs
+.sp
+Certain items in regular expression patterns are processed more efficiently
+than others. It is more efficient to use a character class like [aeiou] than a
+set of single-character alternatives such as (a|e|i|o|u). In general, the
+simplest construction that provides the required behaviour is usually the most
+efficient. Jeffrey Friedl's book contains a lot of useful general discussion
+about optimizing regular expressions for efficient performance. This document
+contains a few observations about PCRE2.
+.P
+Using Unicode character properties (the \ep, \eP, and \eX escapes) is slow,
+because PCRE2 has to use a multi-stage table lookup whenever it needs a
+character's property. If you can find an alternative pattern that does not use
+character properties, it will probably be faster.
+.P
+By default, the escape sequences \eb, \ed, \es, and \ew, and the POSIX
+character classes such as [:alpha:] do not use Unicode properties, partly for
+backwards compatibility, and partly for performance reasons. However, you can
+set the PCRE2_UCP option or start the pattern with (*UCP) if you want Unicode
+character properties to be used. This can double the matching time for items
+such as \ed, when matched with \fBpcre2_match()\fP; the performance loss is
+less with a DFA matching function, and in both cases there is not much
+difference for \eb.
+.P
+When a pattern begins with .* not in atomic parentheses, nor in parentheses
+that are the subject of a backreference, and the PCRE2_DOTALL option is set,
+the pattern is implicitly anchored by PCRE2, since it can match only at the
+start of a subject string. If the pattern has multiple top-level branches, they
+must all be anchorable. The optimization can be disabled by the
+PCRE2_NO_DOTSTAR_ANCHOR option, and is automatically disabled if the pattern
+contains (*PRUNE) or (*SKIP).
+.P
+If PCRE2_DOTALL is not set, PCRE2 cannot make this optimization, because the
+dot metacharacter does not then match a newline, and if the subject string
+contains newlines, the pattern may match from the character immediately
+following one of them instead of from the very start. For example, the pattern
+.sp
+ .*second
+.sp
+matches the subject "first\enand second" (where \en stands for a newline
+character), with the match starting at the seventh character. In order to do
+this, PCRE2 has to retry the match starting after every newline in the subject.
+.P
+If you are using such a pattern with subject strings that do not contain
+newlines, the best performance is obtained by setting PCRE2_DOTALL, or starting
+the pattern with ^.* or ^.*? to indicate explicit anchoring. That saves PCRE2
+from having to scan along the subject looking for a newline to restart at.
+.P
+Beware of patterns that contain nested indefinite repeats. These can take a
+long time to run when applied to a string that does not match. Consider the
+pattern fragment
+.sp
+ ^(a+)*
+.sp
+This can match "aaaa" in 16 different ways, and this number increases very
+rapidly as the string gets longer. (The * repeat can match 0, 1, 2, 3, or 4
+times, and for each of those cases other than 0 or 4, the + repeats can match
+different numbers of times.) When the remainder of the pattern is such that the
+entire match is going to fail, PCRE2 has in principle to try every possible
+variation, and this can take an extremely long time, even for relatively short
+strings.
+.P
+An optimization catches some of the more simple cases such as
+.sp
+ (a+)*b
+.sp
+where a literal character follows. Before embarking on the standard matching
+procedure, PCRE2 checks that there is a "b" later in the subject string, and if
+there is not, it fails the match immediately. However, when there is no
+following literal this optimization cannot be used. You can see the difference
+by comparing the behaviour of
+.sp
+ (a+)*\ed
+.sp
+with the pattern above. The former gives a failure almost instantly when
+applied to a whole line of "a" characters, whereas the latter takes an
+appreciable time with strings longer than about 20 characters.
+.P
+In many cases, the solution to this kind of performance issue is to use an
+atomic group or a possessive quantifier. This can often reduce memory
+requirements as well. As another example, consider this pattern:
+.sp
+ ([^<]|<(?!inet))+
+.sp
+It matches from wherever it starts until it encounters "<inet" or the end of
+the data, and is the kind of pattern that might be used when processing an XML
+file. Each iteration of the outer parentheses matches either one character that
+is not "<" or a "<" that is not followed by "inet". However, each time a
+parenthesis is processed, a backtracking position is passed, so this
+formulation uses a memory frame for each matched character. For a long string,
+a lot of memory is required. Consider now this rewritten pattern, which matches
+exactly the same strings:
+.sp
+ ([^<]++|<(?!inet))+
+.sp
+This runs much faster, because sequences of characters that do not contain "<"
+are "swallowed" in one item inside the parentheses, and a possessive quantifier
+is used to stop any backtracking into the runs of non-"<" characters. This
+version also uses a lot less memory because entry to a new set of parentheses
+happens only when a "<" character that is not followed by "inet" is encountered
+(and we assume this is relatively rare).
+.P
+This example shows that one way of optimizing performance when matching long
+subject strings is to write repeated parenthesized subpatterns to match more
+than one character whenever possible.
+.
+.
+.SS "SETTING RESOURCE LIMITS"
+.rs
+.sp
+You can set limits on the amount of processing that takes place when matching,
+and on the amount of heap memory that is used. The default values of the limits
+are very large, and unlikely ever to operate. They can be changed when PCRE2 is
+built, and they can also be set when \fBpcre2_match()\fP or
+\fBpcre2_dfa_match()\fP is called. For details of these interfaces, see the
+.\" HREF
+\fBpcre2build\fP
+.\"
+documentation and the section entitled
+.\" HTML <a href="pcre2api.html#matchcontext">
+.\" </a>
+"The match context"
+.\"
+in the
+.\" HREF
+\fBpcre2api\fP
+.\"
+documentation.
+.P
+The \fBpcre2test\fP test program has a modifier called "find_limits" which, if
+applied to a subject line, causes it to find the smallest limits that allow a
+pattern to match. This is done by repeatedly matching with different limits.
+.
+.
+.SH AUTHOR
+.rs
+.sp
+.nf
+Philip Hazel
+University Computing Service
+Cambridge, England.
+.fi
+.
+.
+.SH REVISION
+.rs
+.sp
+.nf
+Last updated: 25 April 2018
+Copyright (c) 1997-2018 University of Cambridge.
+.fi
projects / ossec-hids.git / blobdiff