Calculating Regular Expression Resource Consumption

Question

Regular expressions are quite resource-intensive compared to ordinary string operations. Moreover, their complexity is hidden behind a compact syntax - it’s almost impossible to estimate which of several possible options will be faster. The problem is complicated by various dialects (POSIX, Perl) and implementations (NFA, DFA) of regular expressions.

Is there a possibility / tool to calculate the number of operations that a regular expression will require to find the answer in a given string? Primarily interested in PCRE-regular expressions?

@Qwerty, time is directly proportional to the number of steps taken.
The number of steps, in turn, can be obtained using the debugger (@ wiktor-stribiżew, for example, has already given a link to this).
@ WiktorStribiżew I have seen more than once how two regular expressions are compared in the SO pages, and preference is given to the one that takes fewer steps, which is logical and correct.
The decision is made in any form: website, utility, algorithm.

VladD 183k sixteen 222 432 · Accepted Answer · 2016-06-29T20:05:35

The only reliable means of evaluating the performance of several regular expressions is to actually measure the search time and necessarily on different text samples, because different text samples will be processed at different times.

The number of steps that shows regex101 makes sense (my subjective opinion) only when building recursive regular expressions - in them it will allow more or less to evaluate the effectiveness of recursion.

Compare three regular expressions:

[az] - 33 steps https://regex101.com/r/vC5lG7/1
^[^az]*[az] - 4 steps https://regex101.com/r/vC5lG7/2
^[^az]*?[az] - 4 steps https://regex101.com/r/vC5lG7/3

Let's do a simple measurement of the execution time of these expressions:

 function test( $re, $text, $iters ) { $t1 = microtime( true ); for ( $i=0; $i<$iters; $i++ ) { $res = preg_match( $re, $text ); }; $t2 = microtime( true ); echo ($t2-$t1)."<br/>"; }; $re1 = "/[az]/"; $re2 = "/^[^az]*[az]/"; $re3 = "/^[^az]*?[az]/"; $text = " a"; $iters = 50000000; test( $re1, $text, $iters ); test( $re2, $text, $iters ); test( $re3, $text, $iters );

Result:

 9.5385589599609 9.1712720394135 9.6358540058136

The first regular expression is only 4% slower than the second, although the number of steps was 33 vs. 4.
The first regular expression is 1% faster than the third, although the number of steps was 33 vs. 4.

Draw your own conclusions.

PS

necessarily on different text patterns, because different text patterns will be processed at different times

Briefly explain.

Example
Given a large piece of text where the match will be at the end of the text. In such a text, greedy quantification will find it faster than the minimum, but if the match is at the beginning of a large text, then the minimum quantification will find it faster.

Community spirit ♦ one · Answer 2 · 2016-06-28T21:54:56

Is there a possibility / tool to calculate the number of operations that a regular expression will require to search for an answer in a given string?

Visit regex101.com .

Enter \d{4} in the regular expression window, and see:

The calculation took 13 steps, i.e. Number of operations for accessing the PCRE library callback function compiled with the PCRE_AUTO_CALLOUT parameter PCRE_AUTO_CALLOUT .

Here is what Lukas Tsheshnevsky writes :

PCRE_AUTO_CALLOUT flag supports PCRE_AUTO_CALLOUT flag. I'm 99.99% sure that's how regex101's debugger works. Each callout invocation registers as a step in the debugger.

To see a detailed picture of what happens when you find matches in a string using this regular expression, click regex debugger :

Regular Expression Performance and Step Count

This number does not directly indicate the rate of expression parsing by a particular library of regular expressions. You can simply compare several similar templates using the same text as an example and draw conclusions regarding their use.

For real performance testing of a regular expression, use a simple method:

1) Prepare a loop (100-200 thousand iterations), input lines, pattern
2) Count the time before the start of the match to the end
3) Calculate the average time spent on each iteration.

Goncharov Alexander Goncharov Alexander 4,636 9 36 · Answer 3 · 2016-06-29T23:57:07

It is better, it seems to me, to remember that regulars are a utility, and it exists not to search quickly, but to search with compact universal templates, without wasting time on developing analysis algorithms.

If this situation turns out that the speed of the regular work is critical - then at this moment it is necessary to change the approach to analyzing the text with a manual algorithm. The reason is easier to control performance + performance gain.

If you need to parse specialized formats - like HTML, you need to remember that for their parsing there are much more convenient libraries that allow you to make the parser more readable and faster.

And do you know that in regular languages, regular expressions are faster than the manual algorithm?
It is logical - performing a search for a regular search, this is compiled code.
Only from the cannon on the sparrows to beat why, why do you need to hammer nails with a screwdriver?
Tell me a practical example, where it is necessary to use regular text on a large text, yes it turns out so - what do they slow down?
1) It would be interesting to see the statistics of the use of translated and compiled languages.
There is a suspicion that most of the code is written in the broadcast languages, because it is php, js, python, which means that it is incorrect to do rerexing antirecommendation claiming that they are slow.
In addition to very large texts, there is another facet of the issue: small texts.
It is the processing of small texts that is most often used in programs.
And here regular expressions will significantly overtake the “clean” implementations in speed.
For example: overtake text.replace( /[^a-z0-9а-я]+/i, "" ) clean implementation in js.
At the same time compare the difference in the amount of code and its ease of understanding.

Community spirit ♦ one · Answer 4 · 2016-06-28T21:19:49

Regular expressions are quite resource-intensive compared to ordinary string operations.

And how much they are resource-intensive compared to disk operations, or queries to the database, or with the chasing of data on sockets ...

But let's imagine that:

We have a spherical horse in a vacuum
The questioner has not yet learned the word "profiler"

How can one evaluate the "effectiveness" of this or that approach? Obviously, from the definition of this very effectiveness. Classically it is considered that either memory or speed.

OK, how can I measure speed? Imagine, unexpectedly: note the time before, after, and calculate the difference! It is so banal that I will not give examples in order not to insult the interlocutors.

How to estimate the cost of memory? Here it is already more complicated, it all depends on the execution environment. Therefore - "the question requires clarification " :-)

PS

If you correctly understood the question, then there is not quite about the speed that you described in the response-comments (as it is not the answer), but about "Is there an opportunity / tool to calculate the number of operations that a regular expression will require to search for an answer in a given line? "
@edem Well, this is some kind of "academic" question then it turns out :) The number of operations is calculated in advance, by the regexp itself, and, taking into account the input data.
But what this means, in view of its implementation, and practical effectiveness is a completely different question :-)

Calculating Regular Expression Resource Consumption

4 answers 4

Regular Expression Performance and Step Count

More articles: