c++ - Why does the performance of this non-matching pattern scale with the size of the search space?

Question

I have code like the following:

#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]..[x01-x0c]..)REGEX", flags);
   std::regex_search(begin, end, groups, re);
}

… and noticed that it performed suspiciously slowly.

Investigating, I plugged in different values for that buffer size, and found that the search gets slower as the buffer expands:

(small=100, large=35000, huge=100000; "unanchored" is with ^ omitted from the pattern)

The results are as I'd expect if I provide an input that actually matches the pattern:

std::regex is not in multiline mode by default (right?), so I'd have thought that anchor (^) would have prevented such shenanigans. Pattern not found at the start of the search string? Return no match, job done.

Seems to happen with both libc++ and libstdc++.

What am I missing about this? What's causing it?

Obvious workarounds include giving std::regex_search just a prefix of the buffer (a prefix large enough to encompass all possible matches but no more than necessary), or just examining the string in some other way. But I'm curious.

---

FWIW, with a near-equivalent JavaScript testcase, Safari 12.0 on OSX works as I'd expect, with only a very small variation between the three searches (which I'm attributing to random factors) and no obvious pattern:

---

For the avoidance of doubt, I retested with a regex as simple as ^what and got the same results. Might update the above examples later for coherence if I can work up the motivation. :)

Answer 1

It's simply because libstdc++ and libc++ do not implement such optimization.

The following is the main part of libstdc++'s implementation of 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;
  }

So it does traverse the whole range even if the regular expression contains ^.

So is libc++'s implementation.