https://gcc.gnu.org/bugzilla/show_bug.cgi?id=126337
Bug ID: 126337
Summary: Implement std::regex_constants::optimize
Product: gcc
Version: 17.0
Status: UNCONFIRMED
Keywords: missed-optimization
Severity: normal
Priority: P3
Component: libstdc++
Assignee: unassigned at gcc dot gnu.org
Reporter: redi at gcc dot gnu.org
Blocks: 102445
Target Milestone: ---
The standard says this flag means:
"that the regular expression engine should pay more attention to the speed with
which regular expressions are matched, and less to the speed with which regular
expression objects are constructed."
This is a hint by the user that we should do additional work on construction if
that will improve matching speed. This makes sense when a std::basic_regex is
used for many matches, e.g. parsing long log files where the same
std::basic_regex object is used thousands of times. We currently ignore the
hint.
We could use it for a breadth-first search to transform the NFA into a set of
DFAs and memoize them. On each input character the BFS search determines the
new set of active states for the next character. But that step is deterministic
and independent of where we are in the input string, it only depends on the
active states and the next input character. We can construct a cache that maps
(active states + input character) to the next set of states, and then look that
up instead of re-traversing the NFA again on each input character.
Because of ABI restrictions, we can't memoize the DFA in the basic_regex or its
_NFA. But we could have a global (or thread-local) cache of DFA objects that
are looked up by the NFA's address. The basic_regex destructor would remove
objects from the cache (and if the destructor symbol was compiled with an old
GCC runs then the cache entry is simply not removed until the thread exits).
std::regex_iterator could use the optimize flag, because we expect the regex to
be used for matching more than once, as each call to regex_iterator::operator++
does regex_search again.
Referenced Bugs:
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=102445
[Bug 102445] [meta-bug] std::regex issues
