c++ - 为什么这种不匹配模式的性能会随着搜索空间的大小而变化？

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并得到了相同的结果。如果我能激发动力，可能会稍后更新上述示例以保持连贯性。:)

标签： c++regex

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