К>Недавно стековерфлоу лёг на простенькой функции, которая чистила строчку от концевых пробелов.
К>Мы же понимаем, как легко это делается регекспами: s/\s+$//
К>Беда подкралась внезапно: строка с 20тыс пробелов в середине.
А вот не нужно использовать регулярки там, где есть специализированные функции.
В любом современном языке есть функция для отрезания концевых пробелов, которая гарантированно работает быстрее, экономнее и главное корректно в любых ситуациях.

К>Движок регекспа запнулся и устроил квадратичный забег с откатами.
К>http://stackstatus.net/post/147710624694/outage-postmortem-july-20-2016
К>

К>"_____x__"
К> +++++X    - неудача, откат
К>  ++++X    - неудача, откат
К>   +++X    - неудача, откат
К>    ++X    - неудача, откат
К>     +X    - неудача, откат
К>      X    - сразу неудача, идём дальше
К>       +++ - удача, конец
К>

Простейший диалект языка регулярных выражений (РЕГ) эквивалентен детерминированному конечному автомату (ДКА).
И преобразовав РЕГ в ДКА можно проверить совпадение за линейное время.
Но, уже возможность группировки и получения значений сопоставленных групп ломает эту идилию.
Не говоря уже о ссылках на группы.

Поэтому большинство популярных реализаций использует реализацию через интерпретацию — типа расширенный НКА (недетерминированный конечный автомат).
Которая сильно более гибка (например реализации от MS, Lua, PCRE умеют описывать вложенные структуры), но улетает в экспоненту на некоторых типах регулярок и строк.
Что мы и видим на данном примере.

Есть интересный результат от 2000г — тегированный ДКА.
Описан здесь: http://laurikari.net/ville/spire2000-tnfa.pdf
Известные мне реализации на Haskell https://wiki.haskell.org/Regular_expressions#regex-tdfa и С http://laurikari.net/tre/about/
Как можно увидеть они пока что не дотягивают по плюшкам до стандартных реализаций.

Да, о реализации движков очень хорошо изложено в классической книжке «Регулярные выражения» Дж. Фридла, глава 4.
Там же описаны гибридные реализации. Например можно строить для регулярки ДКА (игнорируя некоторые навороты) и НКА. Далее ищем по строке с помощью ДКА, а имея совпадение прогоняем на нём НКА.
К сожалению, о ТДКА Фридл ни во втором, ни в 3-ем русском издании не упоминает.