20

After long debugging I found why my application using python regexps is slow. Here is something I find surprising:

import datetime
import re

pattern = re.compile('(.*)sol(.*)')

lst = ["ciao mandi "*10000 + "sol " + "ciao mandi "*10000,
       "ciao mandi "*1000 + "sal " + "ciao mandi "*1000]
for s in lst:
    print "string len", len(s)
    start = datetime.datetime.now()
    re.findall(pattern,s)
    print "time spent", datetime.datetime.now() - start
    print

The output on my machine is:

string len 220004
time spent 0:00:00.002844

string len 22004
time spent 0:00:05.339580

The first test string is 220K long, matches, and the matching is quite fast. The second test string is 20K long, does not match and it takes 5 seconds to compute!

I knew this report http://swtch.com/~rsc/regexp/regexp1.html which says that regexp implementation in python, perl, ruby is somewhat non optimal... Is this the reason? I didn't thought it could happen with such a simple expression.

added My original task is to split a string trying different regex in turn. Something like:

for regex in ['(.*)sol(.*)', '\emph{([^{}])*)}(.*)', .... ]:
    lst = re.findall(regex, text) 
    if lst:
        assert len(lst) == 1
        assert len(lst[0]) == 2
        return lst[0]

This is to explain why I cannot use split. I solved my issue by replacing (.*)sol(.*) with (.*?)sol(.*) as suggested by Martijn.

Probably I should use match instead of findall... but I don't think this would have solved the issue since the regexp is going to match the entire input and hence findall should stop at first match.

Anyway my question was more about how easy is to fall in this problem for a regexp newbie... I think it is not so simple to understand that (.*?)sol(.*) is the solution (and for example (.*?)sol(.*?) is not).

Improve this question
6
  • 6
    No, the reason is not the implementation. The reason is that the two .* are too permissive and cause a catastrophic backtracking. What are you exactly trying to do? Commented Oct 6, 2014 at 10:33
  • 1
    @casimir, the catastrophic backtracking is the implementation problem. Read the article linked by Emanuele. Commented Oct 6, 2014 at 10:36
  • 2
    @alexis: No, the catastrophic backtracking in this case is due to the pattern conception. You will obtain more or less the same result with other NFA engines. Commented Oct 6, 2014 at 10:38
  • 1
    Read the article. "The other NFA engines" have the same implementation. A real FSA would not need any backtracking. Commented Oct 6, 2014 at 10:39
  • 1
    One more note: the problem is not caused by the double (.*). Searching for (.*)sol has exactly the same time profile. In fact (.*)sol is actually worse if the string contains sol and you search with findall(), since it triggers a failed backtracking search on the substring that follows sol. (The original RE will consume the entire string on success). Commented Oct 6, 2014 at 17:52

3 Answers 3

Reset to default
33

The Thompson NFA approach changes regular expressions from default greedy to default non-greedy. Normal regular expression engines can do the same; simply change .* to .*?. You should not use greedy expressions when non-greedy will do.

Someone already built an NFA regular expression parser for Python: https://github.com/xysun/regex

It indeed outperforms the default Python regular expression parser for the pathological cases. However, it under-performs on everything else:

This regex engine underperforms Python's re module on normal inputs (using Glenn Fowler's test suite -- see below)

Fixing the pathological case at the expense of the typical is probably a good reason not to use the NFA approach as a default engine, not when the pathological case can simply be avoided instead.

Another reason is that certain features (such as back references) are either very hard or impossible to implement using the NFA approach. Also see the response on the Python Ideas mailing list.

As such, your test can be made to perform much better if you made at least one of the patterns non-greedy to avoid the catastrophic backtracking:

pattern = re.compile('(.*?)sol(.*)')

or don't use a regex at all; you could use str.partition() to get the prefix and postfix instead:

before, sol, after = s.partition('sol')

e.g. not all text problems are regular-expression shaped, so put down that hammer and look at the rest of your toolbox!

In addition, you could perhaps look at the alternative re module, regex. This module implements some basic checks for pathological cases and avoids them deftly, without having to resort to a Thompson NFA implementation. Quoting an entry to a Python bug report tracking regex:

The internal engine no longer interprets a form of bytecode but instead follows a linked set of nodes, and it can work breadth-wise as well as depth-first, which makes it perform much better when faced with one of those 'pathological' regexes.

This engine can run your pathological case more than 100 thousand times faster:

>>> import re, regex
>>> import timeit
>>> p_re = re.compile('(.*)sol(.*)')
>>> p_regex = regex.compile('(.*)sol(.*)')
>>> s = "ciao mandi "*1000 + "sal " + "ciao mandi "*1000
>>> timeit.timeit("p.findall(s)", 'from __main__ import s, p_re as p', number=1)
2.4578459990007104
>>> timeit.timeit("p.findall(s)", 'from __main__ import s, p_regex as p', number=100000)
1.955532732012216

Note the numbers; I limited the re test to 1 run and it took 2.46 seconds, while the regex test runs 100k times in under 2 seconds.

Improve this answer
Sign up to request clarification or add additional context in comments.

9 Comments

In my use case I want to split some text in two pieces, but the splitting is achieved by many different regexps (which I concatenate with |) some of them more complicated than this (but not so slow...). So it would be nice to keep this matching in a regexp.
@EmanuelePaolini: for splitting you'd use re.split(), and then you'd not need to use .* at all for the part before and after the sol text.
What's wrong with the upcoming regex module? That's fast and way faster on most pathological ones. For this example it's more than fast enough. Anyway, I downvoted because I think drawing performance conclusions from comparing a heavily optimized C implementation with a hastily-made pure-Python implementation is about the worst benchmarking I've seen anyone do, ever.
@Veedrac: I had not payed attention to the specifics of that implementation.
@MartijnPieters Yet you drew conclusions from it.
|
8

I think this has nothing to do with catastrophic backtracking (or at least my own understanding of it).

The problem is caused by the first (.*) in (.*)sol(.*), and the fact that the regex is not anchored anywhere.

re.findall(), after failing at index 0, would retry at index 1, 2, etc. until the end of the string.

badbadbadbad...bad
^                   Attempt to match (.*)sol(.*) from index 0. Fail
 ^                  Attempt to match (.*)sol(.*) from index 1. Fail
  ^                 Attempt to match (.*)sol(.*) from index 2. Fail (and so on)

It effectively has quadratic complexity O(n2) where n is the length of the string.

The problem can be resolved by anchoring your pattern, so it fails right away at positions that your pattern has no chance to match. (.*)sol(.*) will search for sol within a line of text (delimited by line terminator), so if it can't find a match at the start of the line, it won't find any for the rest of the line.

Therefore, you can use:

^(.*)sol(.*)

with re.MULTILINE option.

Running this test code (modified from yours):

import datetime
import re

pattern = re.compile('^(.*)sol(.*)', re.MULTILINE)

lst = ["ciao mandi "*10000 + "sol " + "ciao mandi "*10000,
       "ciao mandi "*10000 + "sal " + "ciao mandi "*10000]
for s in lst:
    print "string len", len(s)
    start = datetime.datetime.now()
    re.findall(pattern,s)
    print "time spent", datetime.datetime.now() - start
    print

(Note that both passing and failing are 220004 characters)

Gives the following result:

string len 220004
time spent 0:00:00.002000

string len 220004
time spent 0:00:00.005000

This demonstrates clearly that both cases now have the same order of magnitude.

Improve this answer

4 Comments

This is interesting... in fact the point is that re.search is slow while re.match is fast. However I tried to make the same search with awk (but I'm not 100% sure I used an equivalent pattern) and seems that for awk a search and a match take the same time. Maybe the point is that with NFA approach I can implement a search in linear time where a repeated match would require quadratic time.
@EmanuelePaolini: awk doesn't use backtracking engine. That's why it is fast.
Is this not what pathological backtracking is?
@Veedrac: This is more of the behavior at the top level (where the engine advance to the next index after all possibilities at the current index have been exhausted). Well technically, you can define it to be "catastrophic backtracking", but it is different from the case (a*)*, where the problem happens due to the engine allowing aa expansion. The solution for the 2 cases are different also. But I agree that in the end, any inefficiencies are due to excessive backtracking.
0 
^(?=(.*?sol))\1(.*)$

You can try this.This reduces backtracking and fails faster.Try your string here.

http://regex101.com/r/hQ1rP0/22

Improve this answer

8 Comments

What makes you think that it fails faster and backtracks less?
So you're capturing and immediately backreferencing the captured group, and claiming it fails faster with the additional capture; What gives? Well, this does take longer to succeed, and doesn't really fail faster.
@Unihedron well i check at regexhero.net ...in failure in a small string it was 132% faster and when success it was 50 % faster.I guess that is a significant improvement
@Jerry it takes less number of steps as well
@vks You were already told in your own question that the number of steps is not the final factor for speed. The only that is making this slightly faster than the OP's regex are the anchors. Use anchors on the OP's regex and that one is much slower than OP's current regex.
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.