python: how to interrupt a regex match

Question

I iterate over the lines in a large number of downloaded text files and do a regex match on each line. Usually, the match takes less than a second. However, at times a match takes several minutes, sometimes the match does not finish at all and the code just hangs (waited an hour a couple of times, then gave up). Therefore, I need to introduce some kind of timeout and tell the regex match code in some way to stop after 10 seconds or so. I can live with the fact that I will lose the data the regex was supposed to return.

I tried the following (which of course is already 2 different, thread-based solutions shown in one code sample):

def timeout_handler():
    print 'timeout_handler called'

if __name__ == '__main__':
    timer_thread = Timer(8.0, timeout_handler)
    parse_thread = Thread(target=parse_data_files, args=(my_args))
    timer_thread.start()
    parse_thread.start()
    parse_thread.join(12.0)
    print 'do we ever get here ?'

but I do neither get the timeout_handler called nor the do we ever get here ? line in the output, the code is just stuck in parse_data_files.

Even worse, I can't even stop the program with CTRL-C, instead I need to look up the python process number and kill that process. Some research showed that the Python guys are aware of regex C code running away: http://bugs.python.org/issue846388

I did achieve some success using signals:

signal(SIGALRM, timeout_handler)
alarm(8)
data_sets = parse_data_files(config(), data_provider)
alarm(0)

this gets me the timeout_handler called line in the output - and I can still stop my script using CTRL-C. If I now modify the timeout_handler like this:

class TimeoutException(Exception): 
    pass 

def timeout_handler(signum, frame):
    raise TimeoutException()

and enclose the actual call to re.match(...) in a try ... except TimeoutException clause, the regex match actually does get interrupted. Unfortunately, this only works in my simple, single-threaded sandbox script I'm using to try out stuff. There is a few things wrong with this solution:

the signal triggers only once, if there is more than one problematic line, I'm stuck on the second one
the timer starts counting right there, not when the actual parsing starts
because of the GIL, I have to do all the signal setup in the main thread and signals are only received in the main thread; this clashes with the fact that multiple files are meant to be parsed simultaneously in separate threads - there is also only one global timeout exception raised and I don't see how to know in which thread I need to react to it
I've read several times now that threads and signals do not mix very well

I have also considered doing the regex match in a separate process, but before I get into that, I thought I'd better check here if anyone has come across this problem before and could give me some hints on how to solve it.

Update

the regex looks like this (well, one of them anyway, the problem occurs with other regexes, too; this is the simplest one):

'^(\d{5}), .+?, (\d{8}), (\d{4}), .+?, .+?,' + 37 * ' (.*?),' + ' (.*?)$'

sample data:

95756, "KURN ", 20110311, 2130, -34.00, 151.21, 260, 06.0, -9999.0, -9999.0, -9999.0, -9999.0, -9999.0, -9999, -9999, 07.0, -9999, -9999, -9999, -9999, -9999, -9999, -9999, -9999, -9999, -9999, -9999, -9999, -9999, -9999, -9999, -9999, -9999, -9999, -9999, -9999, -9999, -9999, -9999, -9999, -

As said, the regex usually performs ok - I can parse several hundreds of files with several hundreds of lines in less than a minute. That's when the files are complete, though - the code seems to hang with files that have incomplete lines, such as e.g.

`95142, "YMGD ", 20110311, 1700, -12.06, 134.23, 310, 05.0, 25.8, 23.7, 1004.7, 20.6, 0.0, -9999, -9999, 07.0, -9999, -9999, -9999, -9999, -9999, -9999, -9999, -9999, -9999, -9999, -9999, -9999, -9999, -9999, -9999, -9999, -9999, -9999, -9999, -9999

I do also get cases where the regex seems to return right away and reports a non-match.

Update 2

I have only quickly read through the catastrophic article, but as far as I can tell so far, that's not the cause - I do not nest any repetition operators.

I'm on Mac OSX, so I can't use RegexBuddy to analyze my regex. I tried RegExhibit (which apparently uses a Perl RegEx engine internally) - and that runs away, too.

Regex matching in Python happens inside the GIL, so a threaded solution won't help you: While the regex matching is running, no other thread will get to run. — Sven Marnach
– Sven Marnach, Commented Mar 14, 2011 at 11:42
Usually performance problems of this kind are due to catastrophic backtracking. You can very probably improve your regex to match (or fail) faster. Please post the regex you're using (and some sample data you're matching it against) so we can take a look at it. Solve the problem, not the symptom :) — Tim Pietzcker
– Tim Pietzcker, Commented Mar 14, 2011 at 12:08

Tim Pietzcker · Accepted Answer · 2011-03-14 14:25:53Z

8

You are running into catastrophic backtracking; not because of nested quantifiers but because your quantified characters also can match the separators, and since there are a lot of them, you'll get exponential time in certain cases.

Aside from the fact that it looks more like a job for a CSV parser, try the following:

r'^(\d{5}), [^,]+, (\d{8}), (\d{4}), [^,]+, [^,]+,' + 37 * r' ([^,]+),' + r' ([^,]+)$'

By explicitly disallowing the comma to match between separators, you'll speed up the regex enormously.

If commas may be present inside quoted strings, for example, then just exchange [^,]+ (in places where you'd expect this) with

(?:"[^"]*"|[^,]+)

To illustrate:

Using your regex against the first example, RegexBuddy reports a successful match after 793 steps of the regex engine. For the second (incomplete line) example, it reports a match failure after 1.000.000 steps of the regex engine (this is where RegexBuddy gives up; Python will keep on churning).

Using my regex, the successful match happens in 173 steps, the failure in 174.

edited Mar 14, 2011 at 14:25

answered Mar 14, 2011 at 14:10

Tim Pietzcker

337k59 gold badges520 silver badges572 bronze badges

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

1 Comment

ssc Over a year ago

magic. feel like i've been standing too close in front of the problem. thanks mate! :-)

nosklo · Accepted Answer · 2011-03-14 11:50:48Z

2

You can't do it with threads. Go ahead with your idea of doing the match in a separate process.

answered Mar 14, 2011 at 11:50

nosklo

224k58 gold badges300 silver badges299 bronze badges

3 Comments

lilydjwg Over a year ago

I find signal won't work as well: the matching just continues after signal handling....

lilydjwg Over a year ago

Oh no...Signals actually work in this case: exceptions from signal handlers will propagate to the matching process. See bugs.python.org/issue846388

brezniczky Over a year ago

I am coming by this area now. .NET has introduced a timeout on its regex. I think it would be desirable for Python to do the same? Free regex search is not at all uncommon, incl. in text editors. Also it can be easier to create problematic expressions in practice which aren't trivially computationally complex than one would think ... learn.microsoft.com/en-us/dotnet/api/…

shang · Accepted Answer · 2011-03-14 14:04:15Z

2

Instead of trying to solve the regexp hangup issue with timeouts, maybe it would be worthwhile to consider a completely different kind of approach. If your data really is just comma-separated values, you should get much better performance with the csv-module or just using line.split(",").

answered Mar 14, 2011 at 14:04

shang

24.9k3 gold badges61 silver badges87 bronze badges

2 Comments

ssc Over a year ago

yeah, it does seem like that. There is a whole can of worms of reasons though why changing the general approach would require a somewhat major effort, see stackoverflow.com/questions/5160405/… I looked into the CSV module very early in the project and it didn't really seems to give me anything useful that Python can't do out of the box. Looks like I might have to consider a file-type-specific, multistage approach (something I was hoping I could avoid...)

nosklo Over a year ago

huh, python comes with the csv module

Josh Smeaton · Accepted Answer · 2011-03-14 12:10:12Z

Threading in Python is a weird beast. The Global Interpreter Lock is essentially one big Lock around the interpreter, that means only one thread at a time gets to execute within the interpreter.

Thread scheduling is delegated to the OS. Python essentially signals the OS that another thread may take the lock after a certain number of 'instructions'. So if Python is busy due to a run-away regular expression, it never gets the chance to signal the OS that it may try to take the lock for another thread. Hence the reason for using signals; they are the only way to interrupt.

I'm with Nosklo, go ahead and use separate processes. Or, try to rewrite the regular expression so that it doesn't run away. See the problems associated with backtracking. This may or may not be the cause for the poor regex performance, and changing your regex may not be possible. But if this is the cause and it can be changed, you'll save yourself a whole lot of headache by avoiding multiple processes.

Collectives™ on Stack Overflow

python: how to interrupt a regex match

Update

Update 2

4 Answers 4

1 Comment

3 Comments

2 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

Update

Update 2

4 Answers 4

1 Comment

3 Comments

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related