`<regex>`: Nonlinear slowdown with increasing string length

[StephanTLavavej]

Here, this regex is searching for UUIDs optionally wrapped in braces with \{? and \}? (no attempt is made to ensure pairing). There are no UUIDs in the remaining string (2.5 million characters in the original user repro DevCom-10895059, internal VSO-2458266 / AB#2458266 ). The optional braces cause matching to nonlinearly slow down with increasing length of the non-matching string.

Repro with VS 2022 17.14 Preview 5 x64 and microsoft/STL main as of 8e9f4ee.

C:\Temp>type meow.cpp

#include <cassert>
#include <chrono>
#include <cstddef>
#include <iostream>
#include <regex>
using namespace std;
using namespace std::chrono;

int main() {
#ifdef AVOID_OUTER_BRACES
    const regex UuidRegEx{R"([0-9a-fA-F]{8}-[0-9a-fA-F]{4}-[0-9a-fA-F]{4}-[0-9a-fA-F]{4}-[0-9a-fA-F]{12})"};
#else
    const regex UuidRegEx{R"(\{?[0-9a-fA-F]{8}-[0-9a-fA-F]{4}-[0-9a-fA-F]{4}-[0-9a-fA-F]{4}-[0-9a-fA-F]{12}\}?)"};
#endif

    for (size_t n = 1'000; n < 3'000'000; n *= 2) {
        const string allContent(n, 'x');
        const auto start  = steady_clock::now();
        const bool result = regex_search(allContent, UuidRegEx);
        const auto finish = steady_clock::now();
        const auto ms     = duration_cast<milliseconds>(finish - start).count();
        assert(!result);
        cout << "n=" << n << "; ms=" << ms << "; speed n/ms=";
        if (ms == 0) {
            cout << "instant\n";
        } else {
            cout << n * 1.0 / ms << "\n";
        }
    }
}

C:\Temp>cl /EHsc /nologo /W4 /std:c++latest /MT /O2 meow.cpp && meow
meow.cpp
n=1000; ms=1; speed n/ms=1000
n=2000; ms=8; speed n/ms=250
n=4000; ms=28; speed n/ms=142.857
n=8000; ms=107; speed n/ms=74.7664
n=16000; ms=415; speed n/ms=38.5542
n=32000; ms=1629; speed n/ms=19.644
n=64000; ms=6543; speed n/ms=9.78145
n=128000; ms=25819; speed n/ms=4.95759
^C
C:\Temp>cl /EHsc /nologo /W4 /std:c++latest /MT /O2 /DAVOID_OUTER_BRACES meow.cpp && meow
meow.cpp
n=1000; ms=0; speed n/ms=instant
n=2000; ms=0; speed n/ms=instant
n=4000; ms=1; speed n/ms=4000
n=8000; ms=1; speed n/ms=8000
n=16000; ms=3; speed n/ms=5333.33
n=32000; ms=7; speed n/ms=4571.43
n=64000; ms=14; speed n/ms=4571.43
n=128000; ms=30; speed n/ms=4266.67
n=256000; ms=60; speed n/ms=4266.67
n=512000; ms=122; speed n/ms=4196.72
n=1024000; ms=244; speed n/ms=4196.72
n=2048000; ms=472; speed n/ms=4338.98

[muellerj2]

This is caused by _Matcher::_Skip, not by any kind of backtracking.

The ? quantifier is translated into _N_if nodes: The first branch tries to match the brace plus the rest, the second branch only tries to match the rest. So in this case, we get an NFA essentially like this (not 100 % accurate because the parser emits some unnecessary nodes):

                   -> _N_str ("{") - 
                  /                 \
                 /                   v
_N_begin -> _N_if -> _N_if --------> _N_endif -> _N_rep [...]

When searching, _Regex_search2 tries to avoid running the full regex engine starting from each character, looking for the first character that could conceivably be the start of a match by calling _Skip.

For _N_if, _Skip tries all possible branches; note the recursive calls.

        case _N_if:
            { // check for soonest string match
                _Node_if* _Node = static_cast<_Node_if*>(_Nx);

                for (; _First_arg != _Last && _Node; _Node = _Node->_Child) {
                    _Last = _Skip(_First_arg, _Last, _Node->_Next);
                }

                return _Last;
            }

The first branch tests the _N_str node:

        case _N_str:
            { // check for string match
                _Node_str<_Elem>* _Node = static_cast<_Node_str<_Elem>*>(_Nx);
                for (; _First_arg != _Last; ++_First_arg) { // look for starting match
                    _BidIt _Next = _First_arg;
                    if (_Compare(_First_arg, ++_Next, _Node->_Data._Str(), _Node->_Data._Str() + 1, _Traits, _Sflags)
                        != _First_arg) {
                        break;
                    }
                }
                return _First_arg;
            }

Essentially, this is a (terribly inefficient) find looking for '{' in the string. Here, there is no '{', so this will search for it until the end of the string.

In the other branch, _Skip encounters an _N_endif node and just gives up:

        case _N_endif:
        case _N_rep:
        case _N_end_rep:
        default:
            return _First_arg;

This means that we always return _First_arg from the evaluation of _N_if.

So all in all, _Skip just returns _First_arg, spending a linear amount of time to achieve nothing. So the matcher (and thus _Skip) will be run at each individual character. That means we have a total running time on the order of $$\mathcal O(n \cdot \texttt{\_Skip}) = \mathcal O(n^2)$$.

Countermeasures:

• The evaluation of _N_if should really do a breadth-first rather than a depth-first search. I think the most effective way to achieve that in the long term is to construct something equivalent to an _N_class node (or perhaps two) that matches all possible characters that could appear at the start of a match of a regular expression, and then make _Skip only evaluate this special node. This special node could either be computed at the end of parsing (to be stored in an extended version of the root node) or at the beginning of matching.
• The current implementation of _Skip can't easily be changed to a breadth-first search, so I think _Skip should just give up when it encounters an _N_if node with two or more branches. (It should keep going, though, when there is an _N_if node with a single branch -- unfortunately, the parser currently likes to generate such nodes.)
• The _N_str implementation should be translated into an actual call to find or find_if (depending on syntax option flags) or perhaps even be lowered to a call to search.
• _Skip should not just always give up when encountering an _N_endif (or _N_rep) node, but this requires some analysis when it is appropriate to keep going.

[muellerj2]

The evaluation of _N_if should really do a breadth-first rather than a depth-first search.

Another alternative is dynamic programming: We memoize the first possible match for each branch and only evaluate again when we move beyond this position. That means we need to retain some kind of map between nodes and positions. Recognizing if we moved beyond a memoized position is complicated by the fact that the iterators on the searched string might not be random access iterators.

[StephanTLavavej]

Thanks, I've updated the title and description.