CODEWITHSUNDEEP
regexperformanceexecution-time
user6416335
user6416335

Reputation:

Regex execution time analysis

Some of regular expression have exponential time of execution due to bad syntax and non-obvious details. Is there any common way to analyze and learn if some regular expression have linear or exponential execution time?

Upvotes: 6

Views: 1033

Answers (1)

Sobrique
Sobrique

Reputation: 53508

I tend to just use perl and switch on use re 'debug'; before doing a regex operation.

This prints the steps the regex is going through to process, and quickly gives an idea of efficiency.

There's no hard and fast rules - the big warning sign I look for is whether this regex will need to backtrack. See: Catastrophic Backtracking

This can happen more easily when you're using lookahead/lookbehind (but doesn't have to).

In the grand scheme of things though - it pays to remember that whilst regex is a programming language, it's starting point is as a power search-and-replace. And thus implementing complicated logic in it, means you're creating code that's hard to maintain and debug - and so you shouldn't.

One of the useful tricks in perl - it can run in much the same way as sed/grep/awk using command line.

So you can enable regex debugging, and then do 'sed style':

perl -pe 's/search/replace' somefile

But then you can add 'debug' regex:

perl -Mre=debug -pe 's/search/replace/' somefile

Which will debug it whilst you're going.

Upvotes: 4

Related Questions