为什么这种不匹配模式的性能会随着搜索空间的大小而缩放？

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);
}

......并注意到它的表现非常缓慢.

调查,我为该缓冲区大小插入了不同的值,并发现随着缓冲区扩展,搜索速度变慢:

(小= 100,大= 35000,巨大= 100000;"未锚定"是^从模式中省略)

如果我提供实际匹配模式的输入,结果就像我期望的那样:

std::regex默认情况下不是多线模式(对吗？),所以我认为锚(^)会阻止这样的恶作剧.在搜索字符串的开头找不到模式？返回不匹配,完成工作.

似乎与libc ++和libstdc ++一起发生.

我对此缺少什么？是什么造成的？

明显的解决方法包括std::regex_search只给出缓冲区的前缀(一个足够大的前缀来包含所有可能的匹配但不超过必要),或者只是以其他方式检查字符串.但我很好奇.

---

FWIW,具有接近等效的JavaScript测试用例,OSX上的Safari 12.0 正如我所期望的那样工作,三次搜索之间只有非常小的变化(我将其归因于随机因素)并且没有明显的模式:

---

为了避免疑问,我重新测试了一个简单的正则表达式^what并得到了相同的结果.如果我能够提高动力,可以稍后更新上面的例子以保持连贯性.:)

Answer 1

只是因为libstdc++和libc++没有实现这样的优化。

以下是libstdc++实现的主要部分regex_search：

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++的实现也是如此。