Почему производительность этого несоответствующего шаблона масштабируется с размером пространства поиска?

Question

У меня есть код, подобный следующему:

#include <regex>

int main()
{
   char buf[35000] = {};
   auto begin = std::cbegin(buf), end = std::cend(buf);

   std::cmatch groups;
   std::regex::flag_type flags = std::regex_constants::ECMAScript;
   std::regex re(R"REGEX(^[\x02-\x7f]\0..[\x01-\x0c]\0..\0\0)REGEX", flags);
   std::regex_search(begin, end, groups, re);
}

& hellip; и заметил, что он работает подозрительно медленно.

Исследуя, я подключил различные значения для этого размера буфера и обнаружил, что поиск замедляется по мере расширения буфера :

(малая = 100, большая = 35000, огромная = 100000; "unanchored" - с ^ опущено из шаблона)

Результаты будут , как я ожидал бы , если я предоставлю ввод, который фактически соответствует шаблону:

std::regex по умолчанию не в многострочном режиме (верно?), Поэтому я бы подумал, что якорь (^) предотвратил бы такие махинации. Шаблон не найден в начале строки поиска? Вернуть не соответствует, работа выполнена.

Кажется, что происходит как с libc ++, так и с libstdc ++.

Что мне не хватает в этом? Что вызывает это?

Очевидные обходные пути включают предоставление std::regex_search только префикса буфера (префикса, достаточно большого, чтобы охватить все возможные совпадения, но не более, чем необходимо), или просто проверки строки каким-либо другим способом. Но мне любопытно.

---

FWIW, с почти эквивалентным тестовым сценарием JavaScript, Safari 12.0 на OSX работает так, как я ожидал , с очень небольшим отклонением между тремя поисками (что я приписываю случайным факторам) и нет очевидной картины:

---

Во избежание сомнений, я еще раз проверил регулярное выражение так же просто, как ^what и получили те же результаты . Могу обновить приведенные выше примеры позже для согласованности, если я смогу проработать мотивацию. :)

Answer 1

Сейчас я рассматриваю это как проблему качества реализации, которая затрагивает все три набора инструментов.

Поднятые ошибки:

• libstdc ++ ошибка 88947
  • Статус: подтверждено командой разработчиков
• libc ++ ошибка 40390
  • Статус: не подтвержден
• ошибка Visual Studio 432178
  • Статус: не подтвержден

Answer 2

Это просто потому, что libstdc ++ и libc ++ не реализуют такую ​​оптимизацию.

Ниже приведена основная часть реализации regex_search в libstdc ++:

template<typename _BiIter, typename _Alloc, typename _TraitsT,
     bool __dfs_mode>
  bool _Executor<_BiIter, _Alloc, _TraitsT, __dfs_mode>::
  _M_search()
  {
    if (_M_search_from_first())
      return true;
    if (_M_flags & regex_constants::match_continuous)
      return false;
    _M_flags |= regex_constants::match_prev_avail;
    while (_M_begin != _M_end)
    {
      ++_M_begin;
      if (_M_search_from_first())
        return true;
    }
    return false;
  }

Таким образом, он проходит весь диапазон, даже если регулярное выражение содержит ^.

Так же, как и реализация libc ++ .