[issue35915] re.search extreme slowness (looks like hang/livelock), searching for patterns containing .* in a large string

[Ben Spiller]

Ben Spiller <spiller.ben at gmail.com> added the comment:

Correction to original report - it doesn't hang indefinitely, it just takes a really long time. Specifically, looks like it's quadratic in the length of the input string. Increase the size of the input string to 1000*1000 and it's really really slow. 

I don't know for sure if it's possible to implement regexes in a way that avoids this pathological behaviour, but it's certainly quite risky that an otherwise working bit of code using a pattern containing .* can hang/livelock an application for an arbitrary  amount of time if passed a larger-than-expected (but actually not that big) input string.

----------
title: re.search livelock/hang, searching for patterns starting .* in a large string -> re.search extreme slowness (looks like hang/livelock), searching for patterns containing .* in a large string
type: crash -> performance

_______________________________________
Python tracker <report at bugs.python.org>
<https://bugs.python.org/issue35915>
_______________________________________