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

... 并注意到它的运行速度慢得令人怀疑。

经过调查，我为该缓冲区大小插入了不同的值，并发现 the search gets slower as the buffer expands :

(small=100，large=35000，huge=100000；“未锚定”是模式中省略了 ^)

结果是as I'd expect如果我提供与模式实际匹配的输入:

std::regex 默认情况下不处于多行模式(对吗？)，所以我认为 anchor (^) 会阻止此类恶作剧。在搜索字符串的开头找不到模式？返回没有匹配项，工作完成。

似乎 libc++ 和 libstdc++ 都会发生。

我错过了什么？是什么原因造成的？

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

---

FWIW，具有接近等效的 JavaScript 测试用例，OSX 上的 Safari 12.0 works as I'd expect ，三个搜索之间只有非常小的差异(我将其归因于随机因素)并且没有明显的模式:

---

为避免疑义，我重新测试了一个像 ^what 和 got the same results 这样简单的正则表达式.如果我能激发动力，可能会在以后更新上述示例以保持连贯性。 :)

Answer 1

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

下面是main part 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++'s implementation也是如此.