Catastrophic backtracking: When regular expressions explode

In October 2014, we held our annual meetup of the engineering and community teams. That week had lots of awesome, including great food inside and outside the office, serious meetings and not-so-serious meetings, karaoke and big Jenga, and … other things.

And then there were Tiny Talks™. A few weeks in advance, everybody was encouraged to submit one or more topics that they would like to give a short talk about, then we all voted on the suggestions, and the top nine talks were given at the meetup.

The talk I presented had the title “Catastrophic Backtracking ‒ When Regular Expressions Explode”. I explained what happens inside a regex engine when you're not careful in constructing your regular expressions, causing potentially exponential backtracking to happen for some inputs (leading to at best abysmal performance, and at worst an unresponsive server), and I gave some tipps on how to avoid this problem.

I received some very positive feedback on that talk, and so I thought it would be a good idea to share it outside the company. And since the original talks were not recorded, I sat down, re-did the talk in front of a camera, and uploaded it to Vimeo.

So, if you've always wanted to know more about runaway regular expressions, here it is:

– or head over to https://vimeo.com/balpha/catastrophic-backtracking to watch it in HD.

previous post: Android development: What I wish I had known earlier

next post: The making of StackEgg