Why does this regular expression take a long time to run?

Asked Jan 26 '17 at 00:21

Active Jan 26 '17 at 00:42

Viewed 35 times

The following Python code takes a long time to complete (over 5 minutes on my MacBook Pro). Am I doing something to hurt the performance of my regex?

import re
test = re.compile(r'< *(?:\w+ *\*? *,? *)+>')
print test.findall('if ((XXXXXXXXXXXXXXXXXXXXXXXXXXX >= XXXXXXXXXXXXXXXXXXXXXXXXXXXXX) && (XXXXXXXXXXXXXXXXXXXXXXXXXXXXX.XXXXXXXXXXXXXXXXXXXXXXXXXXXXX < XXXXXXXXXXXXXXXXXXXXXXXXXXXXX + XXXXXXXXXXXXXXXXXXXXXXXXXXXXX)) {')

edited Jan 26 '17 at 00:42

martineau

119,623
25
170
301

asked Jan 26 '17 at 00:21

Khaelex

With `*` inside a group with `+`, I'd suspect [catastrophic backtracking](http://www.regular-expressions.info/catastrophic.html). – TigerhawkT3 Jan 26 '17 at 00:22
Standard [catastrophic backtracking](http://www.regular-expressions.info/catastrophic.html). There should be a canonical dupe, but it doesn't look like there is one. – user2357112 Jan 26 '17 at 00:23
@user2357112 - [This](http://stackoverflow.com/questions/22205972/python-regex-takes-so-long-in-some-cases) maybe? – TigerhawkT3 Jan 26 '17 at 00:27
@user2357112 - Or [this](http://stackoverflow.com/questions/25982466/why-does-this-take-so-long-to-match-is-it-a-bug) one seems more thorough. – TigerhawkT3 Jan 26 '17 at 00:28
Probably you just need `< *\w+(?: *\*? *,? *\w+)*>` – Wiktor Stribiżew Jan 26 '17 at 00:31
Thanks everyone! Catastrophic backtracking was the issue. – Khaelex Jan 26 '17 at 00:39

Why does this regular expression take a long time to run?

0 Answers0

Linked