diff options
author | ph10 <ph10@6239d852-aaf2-0410-a92c-79f79f948069> | 2014-10-20 16:48:14 +0000 |
---|---|---|
committer | ph10 <ph10@6239d852-aaf2-0410-a92c-79f79f948069> | 2014-10-20 16:48:14 +0000 |
commit | 566b670e83ae9562aa30b4db61c855596ff2011b (patch) | |
tree | 629bf0c39673f7451b26be4a5ee06939eda4105f /doc/html/pcre2perform.html | |
parent | 5e6b9560a546abb549aad65bab375dc074f1b14a (diff) | |
download | pcre2-566b670e83ae9562aa30b4db61c855596ff2011b.tar.gz |
More documentation
git-svn-id: svn://vcs.exim.org/pcre2/code/trunk@119 6239d852-aaf2-0410-a92c-79f79f948069
Diffstat (limited to 'doc/html/pcre2perform.html')
-rw-r--r-- | doc/html/pcre2perform.html | 196 |
1 files changed, 196 insertions, 0 deletions
diff --git a/doc/html/pcre2perform.html b/doc/html/pcre2perform.html new file mode 100644 index 0000000..0e182e7 --- /dev/null +++ b/doc/html/pcre2perform.html @@ -0,0 +1,196 @@ +<html> +<head> +<title>pcre2perform specification</title> +</head> +<body bgcolor="#FFFFFF" text="#00005A" link="#0066FF" alink="#3399FF" vlink="#2222BB"> +<h1>pcre2perform man page</h1> +<p> +Return to the <a href="index.html">PCRE2 index page</a>. +</p> +<p> +This page is part of the PCRE2 HTML documentation. It was generated +automatically from the original man page. If there is any nonsense in it, +please consult the man page, in case the conversion went wrong. +<br> +<br><b> +PCRE2 PERFORMANCE +</b><br> +<P> +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. +</P> +<br><b> +COMPILED PATTERN MEMORY USAGE +</b><br> +<P> +Patterns are compiled by PCRE2 into a reasonably efficient interpretive code, +so that most simple patterns do not use much memory. 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 +<pre> + (abc|def){2,4} +</pre> +is compiled as if it were +<pre> + (abc|def)(abc|def)((abc|def)(abc|def)?)? +</pre> +(Technical aside: It is done this way so that backtrack points within each of +the repetitions can be independently maintained.) +</P> +<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 +<pre> + ((ab){1,1000}c){1,3} +</pre> +uses 51K bytes 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 64K 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> +<P> +One way of reducing the memory usage for such patterns is to make use of +PCRE2's +<a href="pcre2pattern.html#subpatternsassubroutines">"subroutine"</a> +facility. Re-writing the above pattern as +<pre> + ((ab)(?2){0,999}c)(?1){0,2} +</pre> +reduces the memory requirements to 18K, and indeed it remains under 20K even +with the outer repetition increased to 100. However, this pattern is not +exactly equivalent, because the "subroutine" calls are treated as +<a href="pcre2pattern.html#atomicgroup">atomic groups</a> +into which there can be no backtracking if there is a subsequent matching +failure. Therefore, PCRE2 cannot do this kind of rewriting automatically. +Furthermore, there is a noticeable loss of speed when executing the modified +pattern. Nevertheless, if the atomic grouping is not a problem and the loss of +speed is acceptable, this kind of rewriting will allow you to process patterns +that PCRE2 cannot otherwise handle. +</P> +<br><b> +STACK USAGE AT RUN TIME +</b><br> +<P> +When <b>pcre2_match()</b> is used for matching, certain kinds of pattern can +cause it to use large amounts of the process stack. In some environments the +default process stack is quite small, and if it runs out the result is often +SIGSEGV. Rewriting your pattern can often help. The +<a href="pcre2stack.html"><b>pcre2stack</b></a> +documentation discusses this issue in detail. +</P> +<br><b> +PROCESSING TIME +</b><br> +<P> +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> +<P> +Using Unicode character properties (the \p, \P, and \X 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> +<P> +By default, the escape sequences \b, \d, \s, and \w, 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 \d, when matched with <b>pcre2_match()</b>; the performance loss is +less with a DFA matching function, and in both cases there is not much +difference for \b. +</P> +<P> +When a pattern begins with .* not in parentheses, or in parentheses that are +not 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. However, 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 +<pre> + .*second +</pre> +matches the subject "first\nand second" (where \n 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> +<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> +<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 +<pre> + ^(a+)* +</pre> +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> +<P> +An optimization catches some of the more simple cases such as +<pre> + (a+)*b +</pre> +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 +<pre> + (a+)*\d +</pre> +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> +<P> +In many cases, the solution to this kind of performance issue is to use an +atomic group or a possessive quantifier. +</P> +<br><b> +AUTHOR +</b><br> +<P> +Philip Hazel +<br> +University Computing Service +<br> +Cambridge CB2 3QH, England. +<br> +</P> +<br><b> +REVISION +</b><br> +<P> +Last updated: 20 October 2014 +<br> +Copyright © 1997-2014 University of Cambridge. +<br> +<p> +Return to the <a href="index.html">PCRE2 index page</a>. +</p> |