← Back to context

Comment by lmkg

6 years ago

StackOverflow also had an outage a few years ago that was caused by exponential blow-up of a backtracking regular expression.

https://stackstatus.net/post/147710624694/outage-postmortem-...

2 comments

lmkg

Reply
isaacg  6 years ago

That blow up is quadratic, not exponential: "This is not classic catastrophic backtracking (talk on backtracking) (performance is O(n²), not exponential, in length), but it was enough."

  • perlgeek  6 years ago

    Some years ago I tried to create an exponential time regex in Perl, and only managed a quadratic time one after a bit of experimenting.

    But, as you said, quadratic is often already fatal on realistic data.